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

1 Answer 1

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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