Very true. I was executing the large Int-based examples on a 64 bit machine.

You can of course flip over to Integer on either 32 or 64 bit machines and alleviate the problem with undetected overflow. Of course that doesn't help with negative initial inputs
;)

I do agree It is still probably a good idea to either filter the negative case like you do here, or, since it is well defined, extend the scope of the memo table to the full Int range by explicitly memoizing negative vales as well.

-Edward Kmett

On Fri, Jul 9, 2010 at 11:51 AM, Mike Dillon <mike@embody.org> wrote:
begin Edward Kmett quotation:
> The result is considerably faster:
>
>     *Main> fastest_f 12380192300
>     67652175206
>
>     *Main> fastest_f 12793129379123
>     120695231674999

I just thought I'd point out that running with these particular values
on a machine with a 32 bit Int will cause your machine to go deep into
swap... Anything constant greater that maxBound is being wrapped back to
the negative side, causing havoc to ensue. I changed the open version of
"f" to look like this to exclude negative values:

       f :: (Int -> Int) -> Int -> Int
       f mf 0             = 0
       f mf n | n < 0     = error $ "Invalid n value: " ++ show n
       f mf n | otherwise = max n $ mf (div n 2) +
                                                                mf (div n 3) +
                                                                mf (div n 4)

-md