ani1998ket's blog

By ani1998ket, history, 7 weeks ago, In English

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

 
 
 
 
  • Vote: I like it
  • +59
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it +62 Vote: I do not like it

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*} $$$