[Haskell-cafe] Re: speeding up fibonacci with memoizing
Dan Weston
westondan at imageworks.com
Mon Nov 5 22:44:01 EST 2007
Throwing in a trace statement in fibaux tells me that fibaux i a b c is
not being memoized. If I do map fib [7..9], fibaux counts down to 0
afresh for each of 7, 8, and 9. Ideally, in map fib [0..n], fib (i-2)
and fib (i-1) should be memoized and fib i would be evaluated in
constant time. This is what happens if the loop is unrolled explicitly.
marnes wrote:
> fib :: Integer -> Integer
> fib n = fibaux n 0 1 1
> where
> fibaux :: Integer -> Integer -> Integer -> Integer -> Integer
> fibaux i a b c | i==0 = a
> | i/=0 = fibaux (i-1) b c (b+c)
>
>
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
More information about the Haskell-Cafe
mailing list