# Bit complexity of $n$-th Fibonacci number using matrix multiplication

I want to find the bit complexity of finding the $$n$$-th Fibonacci number using the matrix multiplication method. I know that it has complexity $$O(\log n)$$ if we assume that the standard operations have complexity $$O(1)$$, but if we now consider their true complexity, for example $$O(n)$$ for addition, I don't know how to calculate its true complexity. Can anyone help?

• Two integers of length $n$ can be multiplied using $\Theta(n\log n)$ bit operations, and this is probably optimal (up to constant factors). Dec 10, 2020 at 15:17
• You know the size of the numbers involved in the computation (they are all Fibonacci numbers...), so you can do the math. Dec 10, 2020 at 15:17
• I haven't done the calculation myself. Dec 10, 2020 at 15:53
• Ok thank you very much
– Jmk
Dec 10, 2020 at 16:04

Let us recall that $$F_n = \begin{pmatrix} 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix}.$$ We compute the $$n$$-th Fibonacci number using the method of repeated squaring, applied to the $$2\times 2$$ matrix. The matrices encountered during this process are all of the form $$A_m = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^m = \begin{pmatrix} F_{m+1} & F_m \\ F_m & F_{m-1} \end{pmatrix}.$$ Repeated squaring runs in $$\ell \approx \log n$$ steps. In the $$t$$-th step, we square a matrix $$A_m$$ with $$m = \Theta(2^t)$$, and possibly multiply it by the base matrix. Since the entries of $$A_m$$ are $$\Theta(m)$$ bits long, squaring takes $$\Theta(m\log m) = \Theta(2^tt)$$ bit operations, and this is the dominant operation in the $$t$$-th step. The overall bit complexity is thus proportional to $$\sum_{t=1}^{\ell} 2^tt = \Theta(2^\ell \ell) = \Theta(n\log n).$$