exploring fibonacci

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …,117669030460994

The Fibonacci sequence starts with ${0}$ and ${1}$, and each proceeding term is the sum of the previous two terms. The first ten terms of the sequence are: ${0,1,1,2,3,5,8,13,21,34}$. In general, we can represent the sequence with the following recurrence, where ${F_n}$ is the ${n}$-th term:

Now let’s say you wanted to find ${F_n}$ using code (python, as that’s what everyone knows now). The most direct translation from math to code would be:

def fib(n):
    if n <= 1:
        return 1
    return fib(n - 1) + fib(n - 2)

However, you’ll come to find that this method is very slow, as its time complexity is exponential. One quick way to improve it and reduce the time complexity to linear time would be to use memoization. Luckily, as Python does, there exists a built-in for this.

from functools import lru_cache

@lru_cache
def fib(n):
    if n <= 1:
        return 1
    return fib(n - 1) + fib(n - 2)

Cool, but what if I told you we could go even faster? There exists a closed-form expression for Fibonacci’s Sequence, named Binet’s formula, which is as follows:

This effectively reduces finding the ${n}$-th term to a calculation of exponentiation, which can be done in logarithmic time. Note that Python’s built-in pow function uses this technique. Thus we have:

from math import sqrt

def fib(n):
    a = pow((1 + sqrt(5)) / 2, n)
    b = pow((1 - sqrt(5)) / 2, n)
    return (a - b) / sqrt(5)

But this method introduces a new problem, that of floating point imprecision. We can see that if we try to find fib(4):

>>> fib(4)
3.0000000000000004

And we can’t just cast to int either. For example, while the real ${100}$th Fibonacci number is ${354224848179261915075}$, our python code outputs the following:

>>> int(fib(100))
354224848179263111168

This is quite wrong. We should work within the realm of integers whenever possible for the sake of accuracy. For this, we can look towards yet another closed form of the sequence, using matrices:

Now to convert this to code. Let’s first write a matrix class for ease of readability later on. We’ll override the multiplication and power operators.

class Mat2:
    def __init__(self, a, b, c, d):
        self.m = [a, b, c, d]

    def __mul__(self, other):
        return Mat2(
            self.m[0] * other.m[0]
                + self.m[1] * other.m[2],
            self.m[0] * other.m[1]
                + self.m[1] * other.m[3],
            self.m[2] * other.m[0]
                + self.m[3] * other.m[2],
            self.m[2] * other.m[1]
                + self.m[3] * other.m[3]
        )

    def __pow__(self, n):
        if n == 0:
            # identity matrix
            return Mat2(1, 0, 0, 1)
        if n % 2 == 0:
            return pow(self * self, n // 2)
        return self * pow(self, n - 1)

Now we can write the new Fibonacci function:

def fib(n):
    mat = Mat2(1, 1, 1, 0)
    result = pow(mat, n)
    return result.m[1]

Now, our Fibonacci function works as expected, even with large numbers:

>>> fib(100)
354224848179261915075
>>> fib(69)
117669030460994

This goes to show that even with a simple sequence such as Fibonacci’s sequence, there exists an expansive world of theory behind it for optimization. So, the next time you bump into something that looks simple, don’t be fooled – there’s probably a lot more going on under the hood. Keep digging, and who knows what awesome stuff you’ll find?