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