Fibonacci, the fast way!
Tags: algorithms
Published: 2021-06-26 09:50:01

## Introduction
If you have some dignity, you should know what Fibonacci numbers are. But if you don't know, the Fibonacci sequence is defined as follows:

{% katex inline %}
F_1 = F_2 = 1
{% endkatex %}
{% katex inline %}
F_n = F_{n-1} + F_{n-2}
{% endkatex %}

So the first 6 Fibonacci numbers are: 1, 1, 2, 3, 5, 8.

We would like to write an algorithm that finds the n'th Fibonacci number.

## Simple & Inefficient
One of the most famous solutions to this problem is obviously recursive.
```python
def fib(n):
  if n == 1 or n == 2:
    return 1
  return fib(n-1) + fib(n-2)
```
A quick calculation proves that the time complexity is {% katex inline %}O(2^n){% endkatex %}, which is the worst of our nightmares.

## Simple & Efficient
Another well known solution is to use a simple for loop.
```python
def fib(n):
  a = b = 1
  for i in range(n-1):
    c = a + b
    a = b
    b = c
  return a
```
This is a great solution since it is relatively simple and efficient, as it run in {% katex inline %}O(n){% endkatex %}.

**But**, can we do better?
Yes we can!

## The Brilliancy
This one is for the algo-holics and thanks to its simplicity and efficiency, I consider it to be a brilliant solution.

We are going to find the n'th Fibonacci number in {% katex inline %}O(log(n)){% endkatex %}!

### Efficient Power Algorithm
For starters, let's see how we can calculate {% katex inline %}x^n{% endkatex %} in an efficient time complexity of {% katex inline %}O(log(n)){% endkatex %}.
This algorithm is based on the fact that:
If {% katex inline %}n{% endkatex %} is {% katex inline %}even{% endkatex %}:  {% katex inline %}x^n = x^{n/2} * x^{n/2}{% endkatex %}
If {% katex inline %}n{% endkatex %} is {% katex inline %}odd{% endkatex %}: {% katex inline %}x^n = x^{(n-1)/2} * x^{(n-1)/2} * x{% endkatex %}
```python
def pow(x, n):
  if n == 0:
    return 1
  if n % 2 == 0:
    return pow(x, n/2) ** 2
  else:
    return x * pow(x, (n-1)/2) ** 2
```
The cost of {% katex inline %}pow(x, n){% endkatex %} is {% katex inline %}O(1){% endkatex %} + {% katex inline %}pow(x, n/2){% endkatex %}. A simple calculation shows that the time complexity of this algorithm is {% katex inline %}O(log(n)){% endkatex %}.

This is great! But how is this helpful? What does it have to do with regards to Fibonacci numbers? Well, you are about to find out!

### Efficient Fibonacci
Let's take a look at the following equation, which is correct for every {% katex inline %}n > 2{% endkatex %}:

{% katex %}
\bigg( {F_{n} \atop F_{n-1}} \bigg) = \bigg( {1 \atop 1} {1 \atop 0} \bigg)\bigg( {F_{n-1} \atop F_{n-2}} \bigg)
{% endkatex %}

Just for make sure, let's calculate this matrix multiplication:

{% katex %}
\bigg( {1 \atop 1} {1 \atop 0} \bigg)\bigg( {F_{n-1} \atop F_{n-2}} \bigg) = \bigg( {F_{n-1} + F_{n-2} \atop F_{n-1}} \bigg) = \bigg( {F_{n} \atop F_{n-1}} \bigg)
{% endkatex %}

Since this is right for every {% katex inline %}n > 2{% endkatex %}, we can claim that:

{% katex %}
\bigg( {F_{n-1} \atop F_{n-2}} \bigg) = \bigg( {1 \atop 1} {1 \atop 0} \bigg)\bigg( {F_{n-2} \atop F_{n-3}} \bigg)
{% endkatex %}

{% katex %}
\bigg( {F_{n-2} \atop F_{n-3}} \bigg) = \bigg( {1 \atop 1} {1 \atop 0} \bigg)\bigg( {F_{n-3} \atop F_{n-4}} \bigg)
{% endkatex %}

{% katex %}
\vdots
{% endkatex %}

{% katex %}
\bigg( {F_{3} \atop F_{2}} \bigg) = \bigg( {1 \atop 1} {1 \atop 0} \bigg)\bigg( {F_{2} \atop F_{1}} \bigg) = \bigg( {1 \atop 1} {1 \atop 0} \bigg)\bigg( {1 \atop 1} \bigg) = \bigg( {2 \atop 1} \bigg)
{% endkatex %}

And now, let's put it all together:

{% katex %}
\bigg( {F_{n} \atop F_{n-1}} \bigg) = \bigg( {1 \atop 1} {1 \atop 0} \bigg)\bigg( {F_{n-1} \atop F_{n-2}} \bigg)
{% endkatex %}
{% katex %}
\bigg( {F_{n} \atop F_{n-1}} \bigg) = \bigg( {1 \atop 1} {1 \atop 0} \bigg)\bigg( {1 \atop 1} {1 \atop 0} \bigg)\bigg( {F_{n-2} \atop F_{n-3}} \bigg)
{% endkatex %}
{% katex %}
\bigg( {F_{n} \atop F_{n-1}} \bigg) = \bigg( {1 \atop 1} {1 \atop 0} \bigg)\bigg( {1 \atop 1} {1 \atop 0} \bigg)\bigg( {1 \atop 1} {1 \atop 0} \bigg)\bigg( {F_{n-3} \atop F_{n-4}} \bigg)
{% endkatex %}

{% katex %}
\vdots
{% endkatex %}

{% katex %}
\bigg( {F_{n} \atop F_{n-1}} \bigg) = {\bigg( {1 \atop 1} {1 \atop 0} \bigg)}^{n-2}\bigg( {F_{2} \atop F_{1}} \bigg)
{% endkatex %}
{% katex %}
\bigg( {F_{n} \atop F_{n-1}} \bigg) = {\bigg( {1 \atop 1} {1 \atop 0} \bigg)}^{n-2}\bigg( {1 \atop 1} \bigg)
{% endkatex %}

So now, we see that if we want to know the n'th Fibonacci number (and the one before), all we have to do is some matrix multiplication! More specifically, we need to raise a matrix to the power of {% katex inline %}n-2{% endkatex %}. But we already know how to calculate {% katex inline %}pow(x, n){% endkatex %} in {% katex inline %}O(log(n)){% endkatex %}. This is amazingggg! Note that every matrix multiplication is {% katex inline %}O(1){% endkatex %}.

So, suppose we adjust our power algorithm to work with matrix multiplication instead of regular multiplication, we can calculate {% katex inline %}{\big( {1 \atop 1} {1 \atop 0} \big)}^{n-2}{% endkatex %} in {% katex inline %}O(log(n)){% endkatex %}, then multiply it by {% katex inline %}\big( {1 \atop 1} \big){% endkatex %} and **voilà**! We calculated both {% katex inline %}F_n{% endkatex %} and {% katex inline %}F_{n-1}{% endkatex %} in {% katex inline %}O(log(n)){% endkatex %}!

Take a minute, let that sink in 😌.

### Bonus
So, after you took a minute to chill out your ecstasy, think about it: Is Fibonacci special? Or this method going to work for all recursive equations like Fibonacci?

Well, while Fibonacci IS special, this method is going to work for all equations similar to Fibonacci. For example, let's define the Zigi sequence as follow:

{% katex inline %}
Z_1 = 7
{% endkatex %}
{% katex inline %}
Z_2 = -4
{% endkatex %}
{% katex inline %}
Z_n = 2*Z_{n-1} - 3*Z_{n-2}
{% endkatex %}

The secret is simple: Just find the correct matrix, and the magic will come. Here, we can see that:

{% katex %}
\bigg( {Z_{n} \atop Z_{n-1}} \bigg) = \bigg( {2 \atop 1} {-3 \atop 0} \bigg)\bigg( {Z_{n-1} \atop Z_{n-2}} \bigg)
{% endkatex %}

{% katex %}
\vdots
{% endkatex %}

{% katex %}
\bigg( {Z_{n} \atop Z_{n-1}} \bigg) = {\bigg( {2 \atop 1} {-3 \atop 0} \bigg)}^{n-2}\bigg( {7 \atop -4} \bigg)
{% endkatex %}

And, as you see, the n'th Zigi's number can be computed in {% katex inline %}O(log(n)){% endkatex %}.

![200](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/a2y1zv11fzqb0suug7xf.gif)

Thank you for your time ❤️!