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)