Fibonacci Sequence Algorithm

Elliott Saslow
Jun 22, 2018 · 3 min read

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:

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

Future Vision

A publication centered around high quality storytelling

Elliott Saslow

Written by

Future Vision

A publication centered around high quality storytelling

More From Medium

More from Future Vision

More from Future Vision

The oilparty is over

More from Future Vision

More from Future Vision

The Principles of REST

More from Future Vision

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade