# Difference between revisions of "The Fibonacci sequence"

RossPaterson (talk | contribs) ("fairly fast version" is actually linear in n) |
RossPaterson (talk | contribs) m (Another fast fib assumes that the sequence starts with 1) |
||

Line 78: | Line 78: | ||

=== Another fast fib === |
=== Another fast fib === |
||

+ | (Assumes that the sequence starts with 1.) |
||

<haskell> |
<haskell> |
||

fib = fst . fib2 |
fib = fst . fib2 |

## Revision as of 10:28, 19 August 2008

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

## Contents

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

### 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
```

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

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