There are some nice formulae for the Fibonacci numbers that relate f_m
to values f_n where n is around m/2. This leads to a tolerably fast
recursive algorithm.
Here's a complete implementation:
fib 0 = 0
fib 1 = 1
fib 2 = 1
fib m | even m = let n = m `div` 2 in fib n*(fib (n-1)+fib (n+1))
| otherwise = let n = (m-1) `div` 2 in fib n^2+fib (n+1)^2
Combine that with the NaturalTree structure here:
http://www.haskell.org/haskellwiki/Memoization and it seems to run
faster than Mathematica's built in Fibonacci function taking about 3
seconds to compute fib (10^7) on my PC.
--
Dan
On 11/7/07, Henning Thielemann
On Tue, 6 Nov 2007 ajb@spamcop.net wrote:
However, this is still an O(log n) algorithm, because that's the complexity of raising-to-the-power-of. And it's slower than the simpler integer-only algorithms.
You mean computing the matrix power of
/1 1\ \0 1/
? _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe