# The Fibonacci sequence

### From HaskellWiki

CaleGibbard (Talk | contribs) |
m (→Using 2x2 matrices: formatting) |
||

Line 91: | Line 91: | ||

=== Using 2x2 matrices === | === Using 2x2 matrices === | ||

− | The argument of <hask>iterate</hask> above is a [http://en.wikipedia.org/wiki/Linear_map linear transformation], | + | 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. |

− | 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]], | For example, using the [[Prelude_extensions#Matrices|simple matrix implementation]] in [[Prelude extensions]], | ||

<haskell> | <haskell> |

## Revision as of 15:32, 19 September 2011

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 (+) 1 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)

#### 2.2.5 With state

import Control.Monad.State {- -- haskell translational of python algo def fib(n): a, b = 0, 1 for _ in xrange(n): a, b = b, a + b return a print fib(1000) -} fib :: Integer -> Integer fib n = flip evalState (0,1) $ do forM (xrange n) $ \_ -> do (a,b) <- get put (b,a+b) (a,b) <- get return a xrange n = [0..(n-1)]

## 3 Logarithmic operation implementations

### 3.1 Using 2x2 matrices

The argument of*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

(Assumes that the sequence starts with 1.)

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 Generalization of Fibonacci numbers

The numbers of the traditional Fibonacci sequence are formed by summing its two preceding numbers, with starting values 0 and 1. Variations of the sequence can be obtained by using different starting values and summing a different number of predecessors.

### 5.1 Fibonacci *n*-Step Numbers

The sequence of Fibonacci *n*-step numbers are formed by summing *n* predecessors, using (*n*-1) zeros and a single 1 as starting values:

Note that the summation in the current definition has a time complexity of *O(n)*, assuming we memoize previously computed numbers of the sequence. We can do better than. Observe that in the following Tribonacci sequence, we compute the number 81 by summing up 13, 24 and 44:

The number 149 is computed in a similar way, but can also be computed as follows:

And hence, an equivalent definition of the Fibonacci *n*-step numbers sequence is:

*(Notice the extra case that is needed)*

Transforming this directly into Haskell gives us:

nfibs n = replicate (n-1) 0 ++ 1 : 1 : zipWith (\b a -> 2*b-a) (drop n (nfibs n)) (nfibs n)

nfibs n = let r = replicate (n-1) 0 ++ 1 : 1 : zipWith ((-).(2*)) (drop n r) r in r

## 6 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.):