Fibonacci, the fast way!

Liad Zigdon — Sat, 26 Jun 2021 09:50:01 +0000

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:

$F_1 = F_2 = 1$
$F_n = F_{n-1} + F_{n-2}$

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.

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 $O(2^n)$ , which is the worst of our nightmares.

Simple & Efficient

Another well known solution is to use a simple for loop.

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 $O (n)$ .

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 $O (l o g (n))$ !

Efficient Power Algorithm

For starters, let's see how we can calculate $x^n$ in an efficient time complexity of $O (l o g (n))$ .
This algorithm is based on the fact that:
If $n$ is $e v e n$ : $x^n = x^{n/2} * x^{n/2}$
If $n$ is $o dd$ : $x^n = x^{(n-1)/2} * x^{(n-1)/2} * x$

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 $p o w (x, n)$ is $O (1)$ + $p o w (x, n /2)$ . A simple calculation shows that the time complexity of this algorithm is $O (l o g (n))$ .

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 $n > 2$ :

\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)

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

\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)

Since this is right for every $n > 2$ , we can claim that:

\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)

\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)

\vdots

\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)

And now, let's put it all together:

\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)

\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)

\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)

\vdots

\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)

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

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 $n - 2$ . But we already know how to calculate $p o w (x, n)$ in $O (l o g (n))$ . This is amazingggg! Note that every matrix multiplication is $O (1)$ .

So, suppose we adjust our power algorithm to work with matrix multiplication instead of regular multiplication, we can calculate $(1110)n−2{\big( {1 \atop 1} {1 \atop 0} \big)}^{n-2}$ in $O (l o g (n))$ , then multiply it by $(11)\big( {1 \atop 1} \big)$ and voilà! We calculated both $F_n$ and $F_{n-1}$ in $O (l o g (n))$ !

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:

$Z_1 = 7$
$Z_2 = -4$
$Z_n = 2*Z_{n-1} - 3*Z_{n-2}$

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

\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)

\vdots

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

And, as you see, the n'th Zigi's number can be computed in $O (l o g (n))$ .

Thank you for your time ❤️!

DEV Community: Liad Zigdon