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:

In [1]:
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.

In [2]:
%timeit fib(10000)
100 loops, best of 3: 7.39 ms per loop

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.

In [23]:
def fib_generator(n):
    previous, current = 0, 1
    yield current
    i = 1
    while i < n:
        previous, current = current, previous + current
        yield current
        i += 1
In [24]:
%timeit list(fib_generator(10000))
100 loops, best of 3: 5.88 ms per loop

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:

In [5]:
import numpy as np
In [106]:
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:]
In [107]:
%timeit fib_numpy(10000)
100 loops, best of 3: 5.86 ms per loop
/home/cs1sjm/.conda/envs/numba/lib/python3.4/site-packages/ipykernel/__main__.py:5: RuntimeWarning: overflow encountered in double_scalars

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!

In [8]:
from numba import jit
In [88]:
@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
In [89]:
%timeit fib_numba(10000)
The slowest run took 2075.80 times longer than the fastest. This could mean that an intermediate result is being cached 
10000 loops, best of 3: 45 µs per loop

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:

In [14]:
%load_ext Cython
In [108]:
%%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:]
In [109]:
%timeit fib_cython(10000)
100 loops, best of 3: 2.28 ms per loop
/home/cs1sjm/.conda/envs/numba/lib/python3.4/site-packages/ipykernel/__main__.py:257: RuntimeWarning: overflow encountered in double_scalars

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

Comments

Contents © 2016 Stuart Mumford Creative Commons License - Powered by Nikola