[Haskell-cafe] Fibonacci numbers generator in Haskell

[ajb at spamcop.net]

G'day all.

Quoting Vladimir Portnykh <vportnykh at hotmail.com>:

> 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