Fibonacci Implementation in python
In this post, we’re going to take a look at how to implement the fibonacci sequence in python.
The fibonacci sequence is the series of numbers you get by adding the 2 previous numbers in the sequence i.e.
Starting with 1, 1, the next numbers in the sequence are:
$\text{3. }\hspace{10mm}1 + 1 = 2$
$\text{4. }\hspace{10mm} 2 + 1 = 3$
$\text{5. }\hspace{10mm} 2 + 3 = 5$
$\text{6. }\hspace{10mm} 5 + 3 = 8$
and so on…
We’ll be writing a function that returns the $n^{th}$ fibonacci number.
The first approach is a recursive approach.
def fib_recursive(n):
if n == 1 or n == 2:
return 1
return fib_recursive(n-1) + fib_recursive(n-2)
%time fib_recursive(40)
However, as you can see, this takes an incredibly long amount of time for such a simple calculation.
This is because this implementation is $O(2^n)$ in time, so the time grows exponentially with higher n.
We’ll try another implementation, in which 2 variables store the first 2 fibonacci numbers and then they alternate between themselves for the next fibonacci number until reaching n.
def fibonacci(n):
j = k = 1
if n == 1 or n == 2:
return 1
for i in range(n-2):
if i % 2 == 0:
j += k
else:
k += j
return max(j, k)
%time fibonacci(40)
This implementation is a lot faster as each result is effectively cached when working on the next number in the sequence.
So can we speed up the recursive implementation of fibonacci through caching? Let’s give this a go:
def caching(func):
cache = {}
def cache_func(n):
if n in cache:
return cache[n]
else:
cache[n] = func(n)
return cache[n]
return cache_func
@caching
def fib_recursive(n):
if n == 1 or n == 2:
return 1
return fib_recursive(n-1)+fib_recursive(n-2)
%time fib_recursive(40)
Much better, with caching of intermediate values, the time taken is of the same magnitude.
This all turns out to be moot, because I found out while writing this that there is a formula for calculating the $n^{th}$ fibonacci number, which is:
$F_n = \dfrac{(1 + \sqrt{5})^n – (1 – \sqrt{5})^n}{2^n \sqrt{5}}$
So we can implement this easily
def fib_equation(n):
a = (1 + (5 ** 0.5)) ** n
b = (1 - (5 ** 0.5)) ** n
c = (2 ** n) * (5 ** 0.5)
# round to remove float errors
return round((a - b) / c)
%time fib_equation(40)