Fibonacci Sequence Algorithm

Goals

Go through Recursive definition, show how to implement algorithm in python and see how long different approaches take. As well, I will show how to use matrices to calculate the Fib Seq. Lets dive right in!

Fibonacci is most widely known for his famous sequence of numbers:

0,1,1,2,3,4,8,13,21,34,55,...

Formally the algorithm for the Fibonacci Sequence is defined by a recursive definition:

Recursive Definition of Fib Sequence

Using this we can go ahead and implement the recursive definition into python:

import numpy as np
# Algorithm:
def fib_recursive(n):
    if n == 0: return 0
    if n == 1: return 1
    else: return(fib_recursive(n-1)+fib_recursive(n-2))

Now whenever we have an algorithm, it is always important to make sure that we ask the following questions about it:

• Is it correct? Yes
• How much time does it take?
• Can we do better? Yes

Now without getting into the nitty gritty details here, this algorithm very greedy and takes a lot of computer steps to complete. So lets try another way of doing this using lists that will speed things up and make it easier to calculate.

def fib_poly(n):
    
    #Take care of the zero case
    if n == 0:
        return 0
    
    #otherwise use a list to calculate the correct number
    else:
        f = np.zeros(n+1)
        f[0] = 0
        f[1] = 1
        for i in range(2,n+1):
            f[i] = f[i-1] + f[i-2]
        return f[n]

Ok, Now lets take a look at how each of these perform in terms of time. Below, I timed each function and the results are printed below:

Wow! Look at the time difference there! It is pretty impressive how much faster the poly is than the recursive!

Below is a graph of the difference in time it takes for both of the algorithms:

Wow! Thats incredible how much longer the recursive algorithm takes compared to the Polynomial…. But is there an even Faster way to do this? Lets find out:

It is possible to write the formula in terms of matricies. We start with the equations f1 = f1 and f2 = f0 + f1:

def fib_matrix(n):
    Matrix = np.matrix([[0,1],[1,1]])
    vec = np.array([[0],[1]])
    return np.matmul(Matrix**n,vec)

This is really cool because it shows how the matrix algorithm perform in almost constant time while the polynomial algorithm continues to grow. Please let me know if you are interested in more information!

For help with Python, Unix or anything Computer Science, book a time with me on EXL skills