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

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}$$

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$