Fibonacci is most widely known for his famous sequence of numbers:
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:
if n == 0: return 0
if n == 1: return 1
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.
#Take care of the zero case
if n == 0:
#otherwise use a list to calculate the correct number
f = np.zeros(n+1)
f = 0
f = 1
for i in range(2,n+1):
f[i] = f[i-1] + f[i-2]
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:
Matrix = np.matrix([[0,1],[1,1]])
vec = np.array([,])
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