While playing around with the Fibonacci series. I found a way to compute nth Fibonacci number in Log(N) complexity.
In the excitement, I searched on the net if the algorithm has been derived before. I found out that the algorithm is called as Fast Doubling algorithm. I looked into its derivation and all of them followed the same method using matrix exponentiation.
My method is simpler and intuitive and could be used for self derivation.
I wrote a medium blog regarding this. Thought it would be helpful for someone.
Here is a combinatorial derivation if anyone's interested.
The $$$n$$$-th Fibonacci number is the number of ways to break up a stick of length $$$n - 1$$$ into pieces with lengths 1 and 2.
Let's calculate $$$F(2n + 1)$$$. If we are to break a stick of length $$$2n$$$ into pieces with lengths 1 and 2, then there are two possible cases: either there is a cut at position $$$n$$$ or there isn't; in the second case there must be cuts at positions $$$n - 1$$$ and $$$n + 1$$$.
Now let's calculate $$$F(2n)$$$. Again, we are breaking a stick of length $$$2n - 1$$$ and there are two cases: either there is a cut at position $$$n$$$; or there isn't, and there are cuts at positions $$$n - 1$$$ and $$$n + 1$$$.
In short, we get
Thats awesome :D