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
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