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

Question

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?

Answer 1

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). $$