[Haskell-cafe] Memoization in Haskell?

[Edward Kmett]

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 at 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20100709/730d31c1/attachment.html