[Haskell-cafe] Re: speeding up fibonacci with memoizing

[Don Stewart]

If people write any new variants, please add them to:

    http://haskell.org/haskellwiki/The_Fibonacci_sequence

:)

westondan:
> 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
> >
> >
> 
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe