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 : - Fast Doubling method to find nth Fibonacci number | HackerEarth

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.

9 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.

1 Like

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 @anon55659401 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 ( @anon55659401 ) 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!

1 Like

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 @anon55659401 look into this

this is very nice :slight_smile:

1 Like