The Fibonacci sequence…

The Fibonacci sequence is one of the most well known mathematical sequences and is the most basic example of recurrence relations. Each number in the sequence consists of the sum of the previous two numbers and the starting two numbers are \(0\) and \(1\). It goes something like this:

\(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 \text{ and so on forever…}\)

We will go through a few different approaches for the optimal solution:

1. Using simple recursion
2. Using cache with recursion
3. Using Binet’s formula

Using simple recursion

This is a very simple and easy way to return the nth Fibonacci number in Python:

def recursiveFib(n):
    if n == 1 or n == 2:
        return 1

    return recursiveFib(n - 1) + recursiveFib(n - 2)

It uses recursion to repeatedly call itself multiple times calculating the previous number and using it to work out the next. But that is also its downside, as the function extremely inefficient and resource intensive, this is because at every stage it calculates the previous two numbers, and the previous two numbers of those number etc. Soon you reach a point where it takes too long to calculate the next number – for example on my computer it took me 1.61 seconds to calculate the 35th number. This will obviously be extremely slow, and basically impossible, to calculate higher values.

Using cache with recursion

Since we constantly calculate the previous two numbers, we can harness the power of caching to store the number, so we do not need to calculate them anymore. The built-in functools module allows us to use a least recently used cache; a type of cache which organises the items in order of use. This can speed up the process by a huge amount.

# procedura ricorsiva con cache
@lru_cache()
def recursiveFibCached(n):
    if n == 1 or n == 2:
        return 1

    return recursiveFibCached(n - 1) + recursiveFibCached (n - 2)

Firstly, we need to import the lru_cache decorator from the functools module and place it before our function. We can supply a maxsize value to tell the cache how many items to store, but by default it is 128 and that works perfectly fine.

Using Binet’s formula

Binet’s formula is a formula which can be used to calculate the nth term of the Fibonacci sequence, which is exactly what we want to do, and is named after it was derived by the french mathematician Jacques Philippe Marie Binet. The formula is shown below:

\(F_n = \frac{\phi^n-(-\phi)^{-n}}{\sqrt{5}}\)

where:

\(\phi = \frac{1+\sqrt{5}}{2}\)

We can convert thing formula into Python and start using it straight away:

def formulaFib(n):
    root_5 = 5 ** 0.5
    phi = ((1 + root_5) / 2)

    a = ((phi ** n) - ((-phi) ** (-n))) / root_5

    return round(a)

Note for the Python implementation we need to return the rounded version of the number we calculate, this is because when we calculate a large number Python will return to us a number where there can be 20+ trailing 9’s after the decimal place.

This is all well and good since now we do not have any loops and can instantly compute the answer, right? Well, there is a small catch to this method. If we try to calculate anything above the 1475th number, we will run into an error; OverflowError: (34, 'Numerical result out of range'). This is due to the way floats are implemented in Python and they can only have a certain maximum value, which we exceed using this method.

However, a fix to this is very easy to implement. We can use a built-in module called decimal to create a decimal object with a much higher precision and size to use in our equation:

import decimal

def formulaFibWithDecimal(n):
    decimal.getcontext().prec = 10000

    root_5 = decimal.Decimal(5).sqrt()
    phi = ((1 + root_5) / 2)

    a = ((phi ** n) - ((-phi) ** (-n))) / root_5

    return round(a)

In this new function we set the precision value to 10’000 digits long and we convert our root 5 value into a decimal object value and use that in our equation. This allows us to easily calculate the 10’000th number in the sequence in an astonishing 41.9 seconds, a huge improvement over all our previous methods.