[Haskell-cafe] speeding up fibonacci with memoizing

Mikael Johansson mikael at johanssons.org
Mon Feb 19 02:47:39 EST 2007


On Sun, 18 Feb 2007, Yitzchak Gale wrote:
> Besides memoizing, you might want to use the fact
> that:
>
> fib (2*k) == (fib (k+1))^2 - (fib (k-1))^2
> fib (2*k-1) == (fib k)^2 + (fib (k-1))^2
>

Or, you know, go straight to the closed form for the fibonacci numbers! :)

-- 
Mikael Johansson                 | To see the world in a grain of sand
mikael at johanssons.org            |  And heaven in a wild flower
http://www.mikael.johanssons.org | To hold infinity in the palm of your hand
                                  |  And eternity for an hour


More information about the Haskell-Cafe mailing list