[Solved]: Efficient algorithm to compute the $n$th Fibonacci number

Problem Detail: 

The $n$th Fibonacci number can be computed in linear time using the following recurrence:

def fib(n):     i, j = 1, 1     for k in {1...n-1}:         i, j = j, i+j     return i 

The $n$th Fibonacci number can also be computed as $\left[\varphi^n / \sqrt{5}\right]$. However, this has problems with rounding issues for even relatively small $n$. There are probably ways around this but I'd rather not do that.

Is there an efficient (logarithmic in the value $n$ or better) algorithm to compute the $n$th Fibonacci number that does not rely on floating point arithmetic? Assume that integer operations ($+$, $-$, $\times$, $/$) can be performed in constant time.

Asked By : augurar

Answered By : Yuval Filmus

You can use matrix powering and the identity $$ \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix}. $$ In your model of computation this is an $O(\log n)$ algorithm if you use repeated squaring to implement the powering.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37571