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 iThe $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.
Efficient algorithm to compute the $n$th Fibonacci number
algorithms;time complexity;recurrence relation
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.