# The Fibonacci sequence

### From HaskellWiki

RossPaterson (Talk | contribs) (some tidying to clarify connections) |
RossPaterson (Talk | contribs) ("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 | + | 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. | ||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

=== 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.

## Contents |

## 1 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.

## 2 Linear operation implementations

### 2.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)

### 2.2 Using the infinite list of Fibonacci numbers

One can compute the first *n* Fibonacci numbers with *O(n)* additions.

fib n = fibs!!n

#### 2.2.1 Canonical zipWith implementation

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

#### 2.2.2 With scanl

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

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

#### 2.2.3 With unfoldr

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

#### 2.2.4 With iterate

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

## 3 Logarithmic operation implementations

### 3.1 Using 2x2 matrices

The argument ofso 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 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 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.3 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

## 4 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.

### 4.1 Using Binet's formula

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

## 5 See also

- Naive parallel, multicore version
- Fibonacci primes in parallel
- Discussion at haskell cafe
- Some other nice solutions
- In Project Euler, some of the problems involve Fibonacci numbers. There are some solutions in Haskell (
**Spoiler Warning:**Do not look at solutions to Project Euler problems until you have solved the problems on your own.):