Deriving the fast doubling Fibonacci algorithm without matrices ( O(logN) ) - Codeforces

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.

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$$$.

Leave a Comment