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.

In [1]:
def fib_recursive(n):
    if n == 1 or n == 2:
        return 1
    return fib_recursive(n-1) + fib_recursive(n-2)
In [2]:
%time fib_recursive(40)
CPU times: user 35.9 s, sys: 367 ms, total: 36.2 s
Wall time: 37.4 s
Out[2]:
102334155

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.

In [3]:
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)
In [4]:
%time fibonacci(40)
CPU times: user 19 µs, sys: 0 ns, total: 19 µs
Wall time: 25 µs
Out[4]:
102334155

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:

In [5]:
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)
In [6]:
%time fib_recursive(40)
CPU times: user 68 µs, sys: 19 µs, total: 87 µs
Wall time: 92 µs
Out[6]:
102334155

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

In [7]:
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)
In [8]:
%time fib_equation(40)
CPU times: user 15 µs, sys: 1e+03 ns, total: 16 µs
Wall time: 21 µs
Out[8]:
102334155.0