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
F1​=F2​=1

Fn=Fn−1+Fn−2
F_n = F_{n-1} + F_{n-2}
Fn​=Fn−1…



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
F1=F2=1



Fn=Fn−1+Fn−2
F_n = F_{n-1} + F_{n-2}
Fn=Fn1+Fn2

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(2n)O(2^n)O(2n)

, 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)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))O(log(n))

!



Efficient Power Algorithm

For starters, let’s see how we can calculate

xnx^nxn

in an efficient time complexity of

O(log(n))O(log(n))O(log(n))

.
This algorithm is based on the fact that:
If

nnn

is

eveneveneven

:

xn=xn/2∗xn/2x^n = x^{n/2} * x^{n/2}xn=xn/2xn/2


If

nnn

is

oddoddodd

:

xn=xn/2∗xn/2∗xx^n = x^{n/2} * x^{n/2} * xxn=xn/2xn/2x

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

pow(x,n)pow(x, n)pow(x,n)

is

O(1)O(1)O(1)

+

pow(x,n/2)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))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 > 2n>2

:

(FnFn−1)=(1110)(Fn−1Fn−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)
(Fn1Fn)=(1101)(Fn2Fn1)

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

(1110)(Fn−1Fn−2)=(Fn−1+Fn−2Fn−1)=(FnFn−1)
\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)
(1101)(Fn2Fn1)=(Fn1Fn1+Fn2)=(Fn1Fn)

Since this is right for every

n>2n > 2n>2

, we can claim that:

(Fn−1Fn−2)=(1110)(Fn−2Fn−3)
\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)
(Fn2Fn1)=(1101)(Fn3Fn2)
(Fn−2Fn−3)=(1110)(Fn−3Fn−4)
\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)
(Fn3Fn2)=(1101)(Fn4Fn3)

\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)
(F2F3)=(1101)(F1F2)=(1101)(11)=(12)

And now, let’s put it all together:

(FnFn−1)=(1110)(Fn−1Fn−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)
(Fn1Fn)=(1101)(Fn2Fn1)

(FnFn−1)=(1110)(1110)(Fn−2Fn−3)
\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)
(Fn1Fn)=(1101)(1101)(Fn3Fn2)

(FnFn−1)=(1110)(1110)(1110)(Fn−3Fn−4)
\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)
(Fn1Fn)=(1101)(1101)(1101)(Fn4Fn3)

\vdots
(FnFn−1)=(1110)n−2(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)
(Fn1Fn)=(1101)n2(F1F2)

(FnFn−1)=(1110)n−2(11)
\bigg( {F_{n} \atop F_{n-1}} \bigg) = {\bigg( {1 \atop 1} {1 \atop 0} \bigg)}^{n-2}\bigg( {1 \atop 1} \bigg)
(Fn1Fn)=(1101)n2(11)

So now, we see that if we want to know the nth 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−2n-2n2

. But we already know how to calculate

pow(x,n)pow(x, n)pow(x,n)

in

O(log(n))O(log(n))O(log(n))

. This is amazingggg! Note that every matrix multiplication is

O(1)O(1)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}(1101)n2

in

O(log(n))O(log(n))O(log(n))

, then multiply it by

(11)\big( {1 \atop 1} \big)(11)

and voilà! We calculated both

FnF_nFn

and

Fn−1F_{n-1}Fn1

in

O(log(n))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
Z1=7



Z2=−4
Z_2 = -4
Z2=4



Zn=2∗Zn−1−3∗Zn−2
Z_n = 2*Z_{n-1} – 3*Z_{n-2}
Zn=2Zn13Zn2

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

(ZnZn−1)=(21−30)(Zn−1Zn−2)
\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)
(Zn1Zn)=(1203)(Zn2Zn1)

\vdots
(ZnZn−1)=(21−30)n−2(7−4)
\bigg( {Z_{n} \atop Z_{n-1}} \bigg) = {\bigg( {2 \atop 1} {-3 \atop 0} \bigg)}^{n-2}\bigg( {7 \atop -4} \bigg)
(Zn1Zn)=(1203)n2(47)

And, as you see, the n’th Zigi’s number can be computed in

O(log(n))O(log(n))O(log(n))

.

200

Thank you for your time ❤️!


Print Share Comment Cite Upload Translate
APA
Liad Zigdon | Sciencx (2024-03-29T05:31:05+00:00) » Fibonacci, the fast way!. Retrieved from https://www.scien.cx/2021/06/26/fibonacci-the-fast-way/.
MLA
" » Fibonacci, the fast way!." Liad Zigdon | Sciencx - Saturday June 26, 2021, https://www.scien.cx/2021/06/26/fibonacci-the-fast-way/
HARVARD
Liad Zigdon | Sciencx Saturday June 26, 2021 » Fibonacci, the fast way!., viewed 2024-03-29T05:31:05+00:00,<https://www.scien.cx/2021/06/26/fibonacci-the-fast-way/>
VANCOUVER
Liad Zigdon | Sciencx - » Fibonacci, the fast way!. [Internet]. [Accessed 2024-03-29T05:31:05+00:00]. Available from: https://www.scien.cx/2021/06/26/fibonacci-the-fast-way/
CHICAGO
" » Fibonacci, the fast way!." Liad Zigdon | Sciencx - Accessed 2024-03-29T05:31:05+00:00. https://www.scien.cx/2021/06/26/fibonacci-the-fast-way/
IEEE
" » Fibonacci, the fast way!." Liad Zigdon | Sciencx [Online]. Available: https://www.scien.cx/2021/06/26/fibonacci-the-fast-way/. [Accessed: 2024-03-29T05:31:05+00:00]
rf:citation
» Fibonacci, the fast way! | Liad Zigdon | Sciencx | https://www.scien.cx/2021/06/26/fibonacci-the-fast-way/ | 2024-03-29T05:31:05+00:00
https://github.com/addpipe/simple-recorderjs-demo