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

Правка en1, от 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.

Теги #algorithms, fibonacci numbers, #number theory, fibonaaci


  Rev. Язык Кто Когда Δ Комментарий
en1 Английский ani1998ket 2021-08-05 18:09:23 716 Initial revision (published)