91影视

a).

Consider the two $2脳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}}$鈥�:

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}脳{\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}$鈥�.

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.

d).

Note: Assume that 鈥� $\mathrm{M}\left(\mathrm{n}\right)={\mathrm{n}}^{\mathrm{c}}$鈥� for some 鈥� $\mathrm{c}鈮�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})$.

e).

Note: Assume that 鈥�$M\left(n\right)=n^c$鈥� for some 鈥�$c鈮�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)鈮�{\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}}\underset{\mathrm{i}=1}{\overset{\mathrm{鈭�}}{鈭�}}\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 鈥渇ib3鈥� is 鈥�$\mathrm{O}\left(\mathrm{M}\right(\mathrm{n}\left)\right)$ 鈥�.