G'day all.
Quoting Vladimir Portnykh
I wrote my own Fibonacci numbers generator:
fib :: Int -> [Int] fib 0 = [0,0] fib 1 = [1,0] fib n = [sum prevFib, head prevFib] where a = fib (n - 1)
To get the k-th number you do the following:
result = head (fib k)
[...]
Can we do better?
Sure we can. We can use a more efficient algorithm: fib :: Integer -> Integer fib k | k < 0 = error "fib" | otherwise = fst (fib' k) fib' :: Integer -> (Integer,Integer) fib' 0 = (0,1) fib' k | k `mod` 2 == 0 = let (a,b) = fib' (k `div` 2 - 1) c = a + b c2 = c*c in (c2 - a*a, c2 + b*b) | otherwise = let (a,b) = fib' ((k-1) `div` 2) c = a+b a2 = a*a in (b*b + a2, c*c - a2) Cheers, Andrew Bromage