Question

Is there a faster way to compute the $\mathbf{n}$th Fibonacci number than by fib2 (page 4)? One idea involves matrices.

We start by writing the equations ${\mathbf{F}}_1={\mathbf{F}}_1$ and ${\mathbf{F}}_2={\mathbf{F}}_0+{\mathbf{F}}_1$ in matrix notation:

role="math" localid="1659767046297" $\mathbf{\left(}\begin{array}{c}{\mathbf{F}}_{\mathbf{1}}\\ {\mathbf{F}}_{\mathbf{2}}\end{array}\mathbf{\right)}\mathbf{=}\mathbf{\left(}\begin{array}{cc}\mathbf{0}& \mathbf{1}\\ \mathbf{1}& \mathbf{1}\end{array}\mathbf{\right)}\mathbf{.}\mathbf{\left(}\begin{array}{c}{\mathbf{F}}_{\mathbf{0}}\\ {\mathbf{F}}_{\mathbf{1}}\end{array}\mathbf{\right)}$.

Similarly,

$\left(\begin{array}{c}{\mathbf{F}}_{\mathbf{2}}\\ {\mathbf{F}}_{\mathbf{3}}\end{array}\right)\mathbf{=}\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right)\mathbf{.}\left(\begin{array}{c}{F}_1\\ F_2\end{array}\right)\mathbf{=}{\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right)}^{\mathbf{2}}\mathbf{.}\left(\begin{array}{c}{F}_0\\ F_1\end{array}\right)$

And in general

$\left(\begin{array}{c}{F}_n\\ F_{n+1}\end{array}\right)\mathbf{=}{\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right)}^{\mathbf{n}}\mathbf{.}\left(\begin{array}{c}{F}_0\\ F_1\end{array}\right)$

So, in order to compute ${\mathit{F}}_{\mathbf{n}}$, it suffices to raise this $\mathbf{2}\times \mathbf{2}$ matrix, call it $\mathit{X}$, to the $\mathit{n}$th power.

a. Show that two $\mathbf{2}\mathbf{\times }\mathbf{2}$matrices can be multiplied using $\mathbf{4}$additions and $\mathbf{8}$multiplications.

But how many matrix multiplications does it take to compute ${\mathit{X}}_{\mathbf{n}}$?

b. Show that $\mathbf{O}(\mathbf{log}\mathbf{n})$ matrix multiplications suffice for computing ${\mathbf{X}}_{\mathbf{n}}$. (Hint: Think about computing ${\mathbf{X}}_8$.)

Thus, the number of arithmetic operations needed by our matrix-based algorithm, call it fib3, is just $\mathbf{O}(\mathbf{log}\mathbf{n})$, as compared to $\mathbf{O}\left(\mathbf{n}\right)$for fib2. Have we broken another exponential barrier? The catch is that our new algorithm involves multiplication, not just addition; and multiplications of large numbers are slower than additions. We have already seen that, when the complexity of arithmetic operations is taken into account, the running time offib2becomes $\mathbf{O}\left(\mathbf{n}\right)$.

c. Show that all intermediate results of fib3 are $\mathbf{O}\left(\mathbf{n}\right)$ bits long.

d. Let $\mathbf{M}\left(\mathbf{n}\right)$be the running time of an algorithm for multiplying $\mathit{n}$-bit numbers, and assume that $\mathbf{M}\left(\mathbf{n}\right)=\mathbf{O}\left({\mathbf{n}}^2\right)$ (the school method for multiplication, recalled in Chapter 1, achieves this). Prove that the running time of fib3 is $\mathbf{O}(\mathbf{M}\left(\mathbf{n}\right)\mathbf{log}\mathbf{n})$.

e. Can you prove that the running time of fib3 is $\mathbf{O}\left(\mathbf{M}\left(\mathbf{n}\right)\right)$? Assume $\mathbf{M}\left(\mathbf{n}\right)=\mathbf{\Theta }\left(\mathbf{na}\right)$for some $\mathbf{1}\le \mathbf{a}\le \mathbf{2}$. (Hint: The lengths of the numbers being multiplied get doubled with every squaring.)

In conclusion, whether fib3 is faster than fib2 depends on whether we can multiply n-bit integers faster than$\mathbf{O}\mathbf{\left(}{\mathbf{n}}^{\mathbf{2}}\mathbf{\right)}$ . Do you think this is possible? (The answer is in Chapter 2.) Finally, there is a formula for the Fibonacci numbers:

role="math" localid="1659768125292" ${\mathit{F}}_{\mathbf{n}}\mathbf{=}\frac{\mathbf{1}}{\sqrt{\mathbf{5}}}{\mathbf{\left(}\frac{\mathbf{1}\mathbf{+}\sqrt{\mathbf{5}}}{\mathbf{2}}\mathbf{\right)}}^{\mathbf{n}}\mathbf{-}\frac{\mathbf{1}}{\sqrt{\mathbf{5}}}{\mathbf{\left(}\frac{\mathbf{1}\mathbf{-}\sqrt{\mathbf{5}}}{\mathbf{2}}\mathbf{\right)}}^{\mathbf{n}}\mathbf{.}$

So, it would appear that we only need to raise a couple of numbers to the nth power in order to compute${\mathbf{F}}_{\mathbf{n}}$ . The problem is that these numbers are irrational, and computing them to sufficient accuracy is nontrivial. In fact, our matrix method fib3 can be seen as a roundabout way of raising these irrational numbers to the $\mathbf{n}$th power. If you know your linear algebra, you should see why. (Hint: What are the eigenvalues of the matrix $\mathbf{X}$?)

Short answer

1. Number of multiplications is required to compute “${\mathrm{X}}^{\mathrm{n}}$ ”
2. The “$\log \mathrm{n}$” are squares and most of “$\log \mathrm{n}$” are multiplications by “$\mathrm{X}$”.
3. The multiplication operation does not change the size of intermediate result.
4. It shows that the algorithm runs in the time$\mathbf{O}(\mathbf{M}\left(\mathbf{n}\right)\mathbf{log}\mathbf{n})$.
5. Proved the running time of the algorithm.

Step-by-step solution

Required Number of multiplications.

a).

Consider the two $2\times 2$matrices as “$\mathrm{X}$” and “$\mathrm{Y}$”.

The multiplication of two matrices “ $\mathrm{X}$” and “$\mathrm{Y}$” can be written as follows:

$\mathrm{XY}=\left[\begin{array}{cc}{\mathrm{x}}_{11}& {\mathrm{x}}_{12}\\ {\mathrm{x}}_{21}& {\mathrm{x}}_{22}\end{array}\right]\left[\begin{array}{cc}{\mathrm{y}}_{11}& {\mathrm{y}}_{12}\\ {\mathrm{y}}_{21}& {\mathrm{y}}_{22}\end{array}\right]$

When multiplying the above two matrices, the following will be resulted:

$\mathrm{XY}=\left[\begin{array}{cc}{\mathrm{x}}_{11}{\mathrm{y}}_{11}+{\mathrm{x}}_{12}{\mathrm{y}}_{21}& {\mathrm{x}}_{11}{\mathrm{y}}_{12}+{\mathrm{x}}_{12}{\mathrm{y}}_{22}\\ {\mathrm{x}}_{21}{\mathrm{y}}_{11}+{\mathrm{x}}_{22}{\mathrm{y}}_{21}& {\mathrm{x}}_{21}{\mathrm{y}}_{12}+{\mathrm{x}}_{22}{\mathrm{y}}_{22}\end{array}\right]$

In the above matrix, the multiplication of two matrix matrices has been performed by using $4$additions and $8$ multiplications.

Hence, it is proved.

Therefore, Number of multiplications is required to compute “ ${\mathrm{X}}^{\mathrm{n}}$”:

Solution of part (b)

b).

Initially, consider the instance where “$n=2^k$” for some positive integers “$\mathrm{k}$”.

For “${\mathrm{X}}^{\mathrm{n}}$” can be written as “${\mathrm{X}}^{2^{\mathrm{k}}}$”.

To compute ${\mathrm{X}}^{2^{\mathrm{k}}}$, recursively compute “$\mathrm{Y}={\mathrm{X}}^{2^{\mathrm{k}+1}}$”.

After the recursive computation, square the “$Y$” value.

${\mathrm{Y}}^2={\mathrm{X}}^{2^{\mathrm{k}}}$

The repeated square of “$\mathrm{X}$” can be written as “ ${\mathrm{X}}^2,{\mathrm{X}}^4,\mathrm{...},{\mathrm{X}}^{2^{\mathrm{k}}}={\mathrm{X}}^{\mathrm{n}}$”.

Double the exponent of “$\mathrm{X}$” for each square of “$\mathrm{X}$”.

To produce “${\mathrm{X}}^{\mathrm{n}}$”, it takes $\mathrm{k}=\mathrm{logn}$ matrix multiplications.

The above method can be written as the following recursion:

${\mathrm{X}}_{\mathrm{n}}=\left\{\begin{array}{l}\begin{array}{c}{\left({\mathrm{X}}^{(\mathrm{n}/2)}\right)}^2\\ \mathrm{X}\times {\left({\mathrm{X}}^{(\mathrm{n}/2)}\right)}^2\end{array}\begin{array}{c}\mathrm{if}\text{niseven}\\ \mathrm{if}\text{nisodd}\end{array}\\ \end{array}\right.$

This algorithm involves “$\mathrm{O}\left(\log \mathrm{n}\right)$ ” matrix multiplications.

The “ $\log \mathrm{n}$” are squares and most of “ $\log \mathrm{n}$” are multiplications by “ $\mathrm{X}$”.

Solution of part (c)

c).

In the matrix, the entries are the addition of the products of entries in the given matrix.

While performing addition operation, the number of bits in the entries are unchanged (at maximum one bit).

When performing multiplication operation, number of bits of the operands are added.

Thus, whenever square the matrix “$\mathrm{X}$”, the number of bits of its entries are doubled.

When referring the part (b), the matrix has been squared for “$\mathrm{X}\log \mathrm{n}$” times.

Thus, all intermediate results should be of length less than equal to “$2^{\mathrm{logn}}=\mathrm{O}\left(\mathrm{n}\right)$”.

The multiplication operation does not change the size of intermediate result.

Solution of part (d)

d).

Note: Assume that “ $\mathrm{M}\left(\mathrm{n}\right)={\mathrm{n}}^{\mathrm{c}}$” for some “ $\mathrm{c}\ge 1$”.

In this algorithm, “$\mathrm{O}\left(\log \mathrm{n}\right)$” matrix multiplications are performed; each multiplication performed in the matrix consists a constant number of arithmetic operations.

Each arithmetic operation performed in this algorithm contains size of $\mathrm{O}\left(\mathrm{n}\right)$.

Thus it takes at most time $\mathrm{O}\left(\mathrm{M}\right(\mathrm{n}\left)\right)$; because $\mathrm{M}\left(\mathrm{n}\right)={\mathrm{n}}^{\mathrm{c}}$.

It shows that the algorithm runs in the time$\mathbf{O}(\mathbf{M}\left(\mathbf{n}\right)\mathbf{log}\mathbf{n})$.

Solution of part (e)

e).

Note: Assume that “$M\left(n\right)=n^c$” for some “$c\ge 1$ ”.

Consider that the running time of the algorithm on input size of “$n$” is “$\mathrm{T}\left(\mathrm{n}\right)$”.

At the first level of recursion, execute the algorithm for input size “$n/2$”; it takes “$\mathrm{T}(\mathrm{n}/2)$” time to execute.

To get the final answer, square the results:

The last operation takes time “$\mathrm{M}(\mathrm{n}/2)$” and the result of the operation has bit size “$\mathrm{O}(\mathrm{n}/2)$”.

This result, “ $\mathrm{T}\left(\mathrm{n}\right)=\mathrm{T}(\mathrm{n}/2)+\mathrm{M}(\mathrm{n}/2)$”; while expanding the recursion, and applying geometric series results the following:

$\mathrm{T}\left(\mathrm{n}\right)=\mathrm{M}\left(\frac{\mathrm{n}}{2}\right)+\mathrm{M}\left(\frac{\mathrm{n}}{4}\right)+\mathrm{....}+\mathrm{M}\left(1\right)\le {\left(\frac{\mathrm{n}}{2}\right)}^{\mathrm{c}}+{\left(\frac{\mathrm{n}}{4}\right)}^{\mathrm{c}}+\mathrm{....}+{\left(\frac{\mathrm{n}}{8}\right)}^{\mathrm{c}}$

$={\mathrm{n}}^{\mathrm{c}}\sum _{\mathrm{i}=1}^{\mathrm{\infty }}\frac{1}{2^{\mathrm{ic}}}$

$=O\left(n^c\right)$

$=\mathrm{O}\left(\mathrm{M}\right(\mathrm{n}\left)\right)$

Therefore, the running time of algorithm “fib3” is “$\mathrm{O}\left(\mathrm{M}\right(\mathrm{n}\left)\right)$ ”.