# The Fibonacci Sequence

This post compares a few implementations of calculating the first 10,000 numbers in the Fibbonacci sequence.

The Fibbonacci sequence is defined such that the next number in the sequence is the sum of the previous two:

i.e.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377

This is some prep work I did to test numba on the HPC cluster at Sheffield University. I am hoping to get more fancy stuff running using numba on the cluster.

First off we start with a nice simple and short Python implementation:

```
def fib(n):
fib = [0, 1]
while len(fib) < n+1:
fib.append(fib[-2] + fib[-1])
return fib[1:]
```

This implementation creates a list with the first two elements in (some consider the first 0 as part of the sequence) and then loops until the length of the output list is the correct length (+1 because of the 0) adding the next element in as the sum of the previous two.

```
%timeit fib(10000)
```

This implementation is respectable, but not exactly fast.

Next up we are going to use a little bit of more modern Python magic to see if we can make a pure Python implementation. This uses an interator which stores it's state when 'yield' is called, upon the next time the iterator is called it will resume from where it left off.

```
def fib_generator(n):
previous, current = 0, 1
yield current
i = 1
while i < n:
previous, current = current, previous + current
yield current
i += 1
```

```
%timeit list(fib_generator(10000))
```

This is a litte quicker, which is nice.

Next up we are going to try and use numpy. In this example we define an array the length of the desired sequence and then fill it up in a for loop:

```
import numpy as np
```

```
def fib_numpy(n):
fib = np.zeros(n)
fib[1] = 1
for i in range(2, n):
fib[i] = fib[i-2] + fib[i-1]
return fib[1:]
```

```
%timeit fib_numpy(10000)
```

This does not give us much, if anything over the generator example.

Now we are going to use numba which is a just in time compilation library for Python, which makes things SUPER speedy!

```
from numba import jit
```

```
@jit
def loop(fib):
for i in range(len(fib)):
fib[i] = fib[i-2] + fib[i-1]
return fib
def fib_numba(n):
fib = np.zeros(n)
fib = loop(fib)
return fib
```

```
%timeit fib_numba(10000)
```

This makes a MASSIVE difference! In fact probably too much of a difference, something fishy is probably going on here.

Finally we shall use the Cython package for completeness:

```
%load_ext Cython
```

```
%%cython
import numpy as np
cimport numpy as np
def fib_cython(int n):
cdef np.ndarray fib = np.zeros(n)
cdef int i
fib[1] = 1
for i in range(2, n):
fib[i] = fib[i-2] + fib[i-1]
return fib[1:]
```

```
%timeit fib_cython(10000)
```

This isn't a bad speed up and there are more optimisations you can do with cython.

## Comments