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