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 <[EMAIL PROTECTED]> wrote:
>
> On Tue, 6 Nov 2007 [EMAIL PROTECTED] 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
>
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
