Personal tools

The Fibonacci sequence

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(organization, uniformity, plus a matrix implementation)
(tweak for generality)
Line 33: Line 33:
 
<haskell>
 
<haskell>
 
fibs = unfoldr (\(f1,f2) -> Just (f1,(f2,f1+f2))) (0,1)
 
fibs = unfoldr (\(f1,f2) -> Just (f1,(f2,f1+f2))) (0,1)
  +
</haskell>
  +
  +
=== With iterate ===
  +
  +
<haskell>
  +
fibs = map fst $ iterate (\(f1,f2) -> (f2,f1+f2)) (0,1)
 
</haskell>
 
</haskell>
   
Line 39: Line 45:
 
=== Using 2x2 matrices ===
 
=== Using 2x2 matrices ===
   
Using [[Prelude_extensions#Matrices|simple matrices]],
+
The argument of <hask>iterate</hask> above is a [http://en.wikipedia.org/wiki/Linear_map linear transformation],
  +
so we can represent it as matrix and compute the ''n''th power of this matrix with ''O(log n)'' multiplications and additions.
  +
For example, using the [[Prelude_extensions#Matrices|simple matrix implementation]] in [[Prelude extensions]],
 
<haskell>
 
<haskell>
fib n = head (apply (Matrix [[1,1], [1,0]] ^ n) [0,1])
+
fib n = head (apply (Matrix [[0,1], [1,1]] ^ n) [0,1])
 
</haskell>
 
</haskell>
  +
This technique works for any linear recurrence.
   
 
=== A fairly fast version, using some identities ===
 
=== A fairly fast version, using some identities ===

Revision as of 08:39, 10 May 2007

Implementing the Fibonacci sequence is considered the "Hello, world!" of Haskell programming. This page collects Haskell implementations of the sequence.

Contents

1 Naive definition

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

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

2.1 Canonical zipWith implementation

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

2.2 With scanl

fibs = fix ((0:) . scanl (+) 1)

2.3 With unfoldr

fibs = unfoldr (\(f1,f2) -> Just (f1,(f2,f1+f2))) (0,1)

2.4 With iterate

fibs = map fst $ iterate (\(f1,f2) -> (f2,f1+f2)) (0,1)

3 Log-time implementations

3.1 Using 2x2 matrices

The argument of
iterate
above is a linear transformation,

so we can represent it as matrix and compute the nth power of this matrix with O(log n) multiplications and additions. For example, using the simple matrix implementation in Prelude extensions,

fib n = head (apply (Matrix [[0,1], [1,1]] ^ n) [0,1])

This technique works for any linear recurrence.

3.2 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)

3.3 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

3.4 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))

4 See also