# The Fibonacci sequence

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

## 3 Log-time implementations

### 3.1 Using 2x2 matrices

Using simple matrices,

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

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