DEV Community

Cover image for Fibonacci, the fast way!
Liad Zigdon
Liad Zigdon

Posted on • Updated on

Fibonacci, the fast way!

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:

F1=F2=1 F_1 = F_2 = 1
Fn=Fn1+Fn2 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)
Enter fullscreen mode Exit fullscreen mode

A quick calculation proves that the time complexity is O(2n)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
Enter fullscreen mode Exit fullscreen mode

This is a great solution since it is relatively simple and efficient, as it run in O(n)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(log(n))O(log(n)) !

Efficient Power Algorithm

For starters, let's see how we can calculate xnx^n in an efficient time complexity of O(log(n))O(log(n)) .
This algorithm is based on the fact that:
If nn is eveneven : xn=xn/2xn/2x^n = x^{n/2} * x^{n/2}
If nn is oddodd : xn=x(n1)/2x(n1)/2xx^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
Enter fullscreen mode Exit fullscreen mode

The cost of pow(x,n)pow(x, n) is O(1)O(1) + pow(x,n/2)pow(x, n/2) . A simple calculation shows that the time complexity of this algorithm is O(log(n))O(log(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>2n > 2 :

(FnFn1)=(1110)(Fn1Fn2) \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:

(1110)(Fn1Fn2)=(Fn1+Fn2Fn1)=(FnFn1) \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>2n > 2 , we can claim that:

(Fn1Fn2)=(1110)(Fn2Fn3) \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)
(Fn2Fn3)=(1110)(Fn3Fn4) \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
(F3F2)=(1110)(F2F1)=(1110)(11)=(21) \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:

(FnFn1)=(1110)(Fn1Fn2) \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)

(FnFn1)=(1110)(1110)(Fn2Fn3) \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)

(FnFn1)=(1110)(1110)(1110)(Fn3Fn4) \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
(FnFn1)=(1110)n2(F2F1) \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)

(FnFn1)=(1110)n2(11) \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 n2n-2 . But we already know how to calculate pow(x,n)pow(x, n) in O(log(n))O(log(n)) . This is amazingggg! Note that every matrix multiplication is O(1)O(1) .

So, suppose we adjust our power algorithm to work with matrix multiplication instead of regular multiplication, we can calculate (1110)n2{\big( {1 \atop 1} {1 \atop 0} \big)}^{n-2} in O(log(n))O(log(n)) , then multiply it by (11)\big( {1 \atop 1} \big) and voilà! We calculated both FnF_n and Fn1F_{n-1} in O(log(n))O(log(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:

Z1=7 Z_1 = 7
Z2=4 Z_2 = -4
Zn=2Zn13Zn2 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:

(ZnZn1)=(2130)(Zn1Zn2) \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
(ZnZn1)=(2130)n2(74) \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(log(n))O(log(n)) .

200

Thank you for your time ❤️!

Top comments (2)

Collapse
 
alecbsherman profile image
Alec

Brilliant. I'm sending this to my grandfather and father who are both mathematicians. I expect they will talk about it at family gatherings for months...

Collapse
 
zigliad profile image
Liad Zigdon

That’s cool man! Glad to hear 😊