1
$\begingroup$

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?

$\endgroup$
4
  • $\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 Filmus Dec 10 '20 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 Filmus Dec 10 '20 at 15:17
  • $\begingroup$ I haven't done the calculation myself. $\endgroup$ – Yuval Filmus Dec 10 '20 at 15:53
  • $\begingroup$ Ok thank you very much $\endgroup$ – Jmk Dec 10 '20 at 16:04
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.