### ani1998ket's blog

By ani1998ket, history, 7 weeks ago, 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.

https://medium.com/@ani1998ket/deriving-the-fast-fibonacci-identities-without-matrices-o-log-n-4cd9ce69d9d4  Comments (2)
 » 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$. There are $F(n + 1)^2$ ways the first case could happen — number of ways to cut up the left sub-stick times the number of ways to cut up the right sub-stick. Both sub-sticks have length $n$, so there are $F(n + 1)$ ways to cut up either. There are $F(n)^2$ ways the second case could happen for the same reason: the left and right sub-sticks both have length $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 the first case, there are $F(n + 1)$ ways to cut up the left stick (of length $n$) and $F(n)$ ways to cut up the right stick (of length $n - 1$). A total of $F(n + 1) F(n)$ ways. In the second case, there are $F(n)$ ways to cut up the left stick (of length $n - 1$) and $F(n - 1) = F(n + 1) - F(n)$ ways to cut up the right stick (of length $n - 2$). In short, we get \begin{align*} F(2n + 1) &= F(n + 1)^2 + F(n)^2 \\ F(2n) &= F(n + 1) F(n) + F(n) (F(n + 1) - F(n)) = 2 F(n + 1) F(n) - F(n)^2 \end{align*}
•  » » Thats awesome :D