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
