The Fibonacci sequence
Revision as of 23:02, 9 May 2007 by RossPaterson (talk | contribs) (organization, uniformity, plus a matrix implementation)
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
Implementing the Fibonacci sequence is considered the "Hello, world!" of Haskell programming. This page collects Haskell implementations of the sequence.
Naive definition
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
Linear-time implementations
One can compute the first n Fibonacci numbers with O(n) additions.
If fibs
is the infinite list of Fibonacci numbers, one can define
fib n = fibs!!n
Canonical zipWith implementation
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
With scanl
fibs = fix ((0:) . scanl (+) 1)
With unfoldr
fibs = unfoldr (\(f1,f2) -> Just (f1,(f2,f1+f2))) (0,1)
Log-time implementations
Using 2x2 matrices
Using simple matrices,
fib n = head (apply (Matrix [[1,1], [1,0]] ^ n) [0,1])
A fairly fast version, using some identities
fib 0 = 0
fib 1 = 1
fib n | even n = f1 * (f1 + 2 * f2)
| n `mod` 4 == 1 = (2 * f1 + f2) * (2 * f1 - f2) + 2
| otherwise = (2 * f1 + f2) * (2 * f1 - f2) - 2
where k = n `div` 2
f1 = fib k
f2 = fib (k-1)
Another fast fib
fib = fst . fib2
-- | Return (fib n, fib (n + 1))
fib2 0 = (1, 1)
fib2 1 = (1, 2)
fib2 n
| even n = (a*a + b*b, c*c - a*a)
| otherwise = (c*c - a*a, b*b + c*c)
where (a,b) = fib2 (n `div` 2 - 1)
c = a + b
Fastest Fib in the West
This was contributed by wli (It assumes that the sequence starts with 1.)
import Data.List
fib1 n = snd . foldl fib' (1, 0) . map (toEnum . fromIntegral) $ unfoldl divs n
where
unfoldl f x = case f x of
Nothing -> []
Just (u, v) -> unfoldl f v ++ [u]
divs 0 = Nothing
divs k = Just (uncurry (flip (,)) (k `divMod` 2))
fib' (f, g) p
| p = (f*(f+2*g), f^2 + g^2)
| otherwise = (f^2+g^2, g*(2*f-g))