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
@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)
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ā¦
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ā¦!