ani1998ket's blog

By ani1998ket, history, 3 months 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

Read more »

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