Hi

I just wanted everyone to know that there exists log(n) solution using matrix multiplication for Fibonacci.

How does it work?

Create a matrix like this and take nth power:

So using the log n optimization for calculating power, we get log(n) solution.

For more info - http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/ (look at method 4 & 5)