Fastest known way to computing the $n$-th Fibonacci number?

Question

Using the recursive formula and a bit of memory, you can compute this number in linear time.

But there is also the direct formula. Unfortunately, it used irrational numbers, so first need to fix an adequate ring in which you do the computations (like the rationals and $\sqrt5$). Then you need to compute and subtract the powers of the irrational numbers. So it is not obvious how many steps you really need.

Or is there an even faster way?

Answer 1

There are several approaches that take $O(\log n)$ arithmetic operations. (Although the cost of doing operations on numbers the size of $F_n$ shouldn't be neglected either: the Fibonacci numbers grow exponentially, so $F_n$ takes $O(n)$ bits to store. But this cost will be roughly the same for any method you use.)

Probably the simplest one to explain is to write the Fibonacci recurrence relation as the matrix product $$\begin{bmatrix}F_{n} \\ F_{n-1}\end{bmatrix} = \begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}\begin{bmatrix}F_{n-1} \\ F_{n-2}\end{bmatrix}$$ from which we get $$\begin{bmatrix}F_n \\ F_{n-1}\end{bmatrix} = \begin{bmatrix}1 & 1 \\ 1 & 0\end{bmatrix}^{n-1}\begin{bmatrix}1 \\ 0\end{bmatrix}.$$ To compute $A^{n-1}$ quickly for a matrix $A$, we can use iterated squaring: the recurrence $$A^k = \begin{cases}(A^{k/2})^2 & \text{$k$ even, } \\ A \cdot A^{k-1} & \text{$k$ odd. }\end{cases}$$

Answer 2

The formula $$F_{2n+1}=F_{n+1}^2+F_n^2\\F_{2n}=F_n(2F_{n+1}-F_n)$$ is also $\log(n) $ this identity follows by using the matrix Misha wrote and writing $A^{2n}=A^nA^n$