Efficient algorithm to compute the $n$th Fibonacci number
You can use matrix powering and the identity
$$
\begin{bmatrix} 1 &amp; 1 \\ 1 &amp; 0 \end{bmatrix}^n = \begin{bmatrix} F_{n+1} &amp; F_n \\ F_n &amp; 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.