Fastest way to calculate Fibonacci number

I was studying linear algebra by Gilbert Strang and i found this formula for computing Fibonacci number fibo

here is my code:

i am taking the floor value of final answer
this program is running till input=10^3 after that it is overflowed and also i am getting slight deviation in value from correct value after n>80 , may be it is because of arithmetic operation
this solution is much faster than dynamic programming one ,so i am sharing in a hope to learn some way of improving this solution from you guys and please let me know if their is a better solution

1 Like

That formula is never used in competitive programming as it gives incorrect values for bigger ‘n’ like say, (n>100).

This is the fastest way to calculate the nth fibonacci number : - https://www.hackerearth.com/practice/notes/fast-doubling-method-to-find-nth-fibonacci-number/

Time Complexity:- O(logN) .

5 Likes

Karan Bhaai…? Tumhe pata hai kii ye do formulas ( Fast doubling waale ) kaha se prakat hue…?

1 Like

I think using matrix exponentiation to to calculate N'th fibonacci number in O(LogN) is pretty nice and applicable to most cases.

7 Likes

In fact this technique can be used to find T(n) = aT(n-1)+bT(n-2)+cT(n-3)+…+kT(0) for generic recurrence.

kisi ko pata ho ye kaha se aaya yaa yaad karne kaa koi tareeka pata ho to bata do bhaai log… ratta nhii lagaaya jaaega… :tired_face:

1 Like

@ritesh1340
Lets start with the understanding that Fn = Fn-1 + Fn-2
Consider this beautiful matrix

|1 1|
|1 0|

Lets multiply it with a matrix and see what we get. Here x, y, z are three consecutive fibonacci numbers such that z > y > z.

|z y| |1 1|
|y x| |1 0|

The resulting matrix is
|z+y z+0|
| x+y y+0|

Here z+y is the newest addition to the series! Note that, x+y = z. We have basically created a new matrix but with the same quality of three consecutive fibonaccis.

Considering first three fibs are 0,1,1 - we just need to multiply following matrix as many times as needed with itself to get our result:

|11|
|10|

Square it and we get 4th fib. Cube it and we get 5th fib.

Now suppose you want me to find out the fib number 36. How much effort will I take?

Matrix square will give me 4th fib.
The above matrix square gives power of 4 -> 6th fib.
The above matrix square will give power of 8 -> 10th fib.
Square of above will give power of 16 -> 18th fib
Square of above will give power of 32 -> 34th fib.
Multiply above with what we got in step number 2 i.e. power of 34 -> 36th fib.

This happens in just 6 steps!
The compexity is visibly O(logn)

Hope it helps!

2 Likes

No…I m still confused plz explain little bit more or any other good video link.

I know the answer but I am busy with something…

Is this the way of talking in a discuss forum?

Not taking any sides, but I am very displeased by how such random comments cause a lot of spam in some threads. Please maintain professionalism.

5 Likes

So sorry @vijju123 ,:pensive:

1 Like

it is the simplest way to calculate the fibonacci no
a,b=0,1
print(a,b,end=" “)
for i in range(50):
c=a+b
a,b=b,c
if(c<=50):
print(c,end=” ")

1 Like

Hello… I appreciate your effort my friend ; but I think we both are not on the same page… or maybe I was not able to understand something in your explanation…

Actually I understand every single detail about the matrix exponentiation trick… from where it comes ; to its correctness and time complexity of O(log N).

What I don’t know is the method which @karangreat234 mentioned… ( The fast doubling one… ) That from where does those two formulas come from…

I have seen that formula earlier also ; but I forget it each time bcos I don’t know form where it comes ( That’s why they are hard to remember for me ) …

And in my previous comment also ; I replied him ( @karangreat234 ) for that formula only… If you know how do they come ; please share…Thanks…

Ok bro… no problem :+1: ; but whenever you get time ; please re-visit this ; I am eager to know from where they come… Thanks…!

If you know how do they come ; please share…Thanks…

Hi! Here I am using the same matrix exponentiation to derive the fast doubling formula. The explanation is fairly straightforward. Let me know if something needs further explanation!

Woooo…! Pleased to see how much efforts forum members put in to help others… Was opening the discuss page for past few days just for something like this… It really helped ; Thanks…! :slight_smile:

1 Like

http://cp-algorithms.com/ It all comes from here @ritesh1340

1 Like

long int n;
scanf("%d",&n);
double d;
d=(0.4472)*pow(1.6180,n-1);
printf("%0.lf",d);

This will work

No it does not work fail for large values @karangreat234 look into this

this is very nice :slight_smile:

1 Like