[Haskell-cafe] speeding up fibonacci with memoizing

[Felipe Almeida Lessa]

On 2/18/07, Yitzchak Gale <gale at sefer.org> 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

Nice one:
$ time ./a.out another_fib 200000
Using 'another_fib' to calculate fib of 200000
 -> 15085683557988938992[...]52246259408175853125

real    0m1.177s
user    0m1.051s
sys     0m0.017s


Implementation details:
-----------------------------------------
another_fibs = 0 : 1 : 1 : map f [3..]
    where
      square x = x * x
      sqfib = square . another_fib
      f n | even n = sqfib (k+1) - sqfib (k-1) where k = n `div` 2
      f n          = sqfib k + sqfib (k-1) where k = (n + 1) `div` 2
another_fib = (!!) another_fibs
-----------------------------------------

Conclusion: it's often better to improve the algorithm than the
implementation =).

-- 
Felipe.