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

Revision en1, by ani1998ket, 2021-08-05 18:09:23

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.

Tags #algorithms, fibonacci numbers, #number theory, fibonaaci


  Rev. Lang. By When Δ Comment
en1 English ani1998ket 2021-08-05 18:09:23 716 Initial revision (published)