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?
-
$\begingroup$ Two integers of length $n$ can be multiplied using $\Theta(n\log n)$ bit operations, and this is probably optimal (up to constant factors). $\endgroup$– Yuval FilmusDec 10, 2020 at 15:17
-
$\begingroup$ You know the size of the numbers involved in the computation (they are all Fibonacci numbers...), so you can do the math. $\endgroup$– Yuval FilmusDec 10, 2020 at 15:17
-
$\begingroup$ I haven't done the calculation myself. $\endgroup$– Yuval FilmusDec 10, 2020 at 15:53
-
$\begingroup$ Ok thank you very much $\endgroup$– JmkDec 10, 2020 at 16:04
1 Answer
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). $$