Difference between revisions of "The Fibonacci sequence"

From HaskellWiki
Jump to: navigation, search
(some tidying to clarify connections)
("fairly fast version" is actually linear in n)
Line 9: Line 9:
 
fib n = fib (n-1) + fib (n-2)
 
fib n = fib (n-1) + fib (n-2)
 
</haskell>
 
</haskell>
This implementation takes time ''O(fib n)''.
+
This implementation requires ''O(fib n)'' additions.
   
 
== Linear operation implementations ==
 
== Linear operation implementations ==
  +
 
=== A fairly fast version, using some identities ===
  +
 
<haskell>
 
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)
 
</haskell>
  +
  +
=== Using the infinite list of Fibonacci numbers ===
   
 
One can compute the first ''n'' Fibonacci numbers with ''O(n)'' additions.
 
One can compute the first ''n'' Fibonacci numbers with ''O(n)'' additions.
Line 19: Line 34:
 
</haskell>
 
</haskell>
   
=== Canonical zipWith implementation ===
+
==== Canonical zipWith implementation ====
   
 
<haskell>
 
<haskell>
Line 25: Line 40:
 
</haskell>
 
</haskell>
   
=== With scanl ===
+
==== With scanl ====
   
 
<haskell>
 
<haskell>
Line 37: Line 52:
 
</haskell>
 
</haskell>
   
=== With unfoldr ===
+
==== With unfoldr ====
   
 
<haskell>
 
<haskell>
Line 43: Line 58:
 
</haskell>
 
</haskell>
   
=== With iterate ===
+
==== With iterate ====
   
 
<haskell>
 
<haskell>
Line 60: Line 75:
 
</haskell>
 
</haskell>
 
This technique works for any linear recurrence.
 
This technique works for any linear recurrence.
 
=== A fairly fast version, using some identities ===
 
 
<haskell>
 
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)
 
</haskell>
 
   
 
=== Another fast fib ===
 
=== Another fast fib ===

Revision as of 10:25, 19 August 2008

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

Naive definition

The standard definition can be expressed directly:

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

This implementation requires O(fib n) additions.

Linear operation implementations

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)

Using the infinite list of Fibonacci numbers

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 = scanl (+) 0 (1:fibs)
fibs = 0 : scanl (+) 0 fibs

The recursion can be replaced with fix:

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

With unfoldr

fibs = unfoldr (\(a,b) -> Just (a,(b,a+b))) (0,1)

With iterate

fibs = map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)

Logarithmic operation implementations

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.

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

An even faster version, given later by wli on the IRC channel.

import Data.List
import Data.Bits

fib :: Int -> Integer
fib n = snd . foldl' fib' (1, 0) $ dropWhile not $
            [testBit n k | k <- let s = bitSize n in [s-1,s-2..0]]
    where
        fib' (f, g) p
            | p         = (f*(f+2*g), ss)
            | otherwise = (ss, g*(2*f-g))
            where ss = f*f+g*g

Constant-time implementations

The Fibonacci numbers can be computed in constant time using Binet's formula. However, that only works well within the range of floating-point numbers available on your platform. Implementing Binet's formula in such a way that it computes exact results for all integers generally doesn't result in a terribly efficient implementation when compared to the programs above which use a logarithmic number of operations (and work in linear time).

Beyond that, you can use unlimited-precision floating-point numbers, but the result will probably not be any better than the log-time implementations above.

Using Binet's formula

fib n = round $ phi ** fromIntegral n / sq5
  where
    sq5 = sqrt 5 :: Double
    phi = (1 + sq5) / 2

See also