[Haskell-cafe] Fibbonachi numbers algorithm work TOO slow.

[Dan Piponi]

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 <lemming at henning-thielemann.de> wrote:
>
> On Tue, 6 Nov 2007 ajb at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>