On 2/18/07, Yitzchak Gale <[EMAIL PROTECTED]> 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.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Reply via email to