Chapter 30, Problem 1P

a.

Program Plan Intro

To multiply two linear polynomials $ax+b$ and $cx+d$ using only three multiplications.

Explanation of Solution

Multiply two linear polynomials $ax+b$ and $cx+d$ using only 3 multiplications as follows:

  $(a+b)(c+d)=ac+cb+ad+cd$

Thus, the product of two polynomials is as follows:

  $ac{x}^2+((a+b)(c+d)-ac-cd)x+cd$

b.

Program Plan Intro

To provide two divide-and-conquer algorithms for multiplying two polynomials of degree-bound n in $\Theta \left(n^{\lg 3}\right)$ time.

Explanation of Solution

Method 1(for dividing the input polynomial coefficients into a high half and low half):

Take two polynomials be $P_1$ and $P_2$ such that, $P_1\left(x\right)={\displaystyle {\sum }_{j=1}^{n-1}{a}_{j,1}{x}^j}$ and $P_2\left(x\right)={\displaystyle {\sum }_{j=1}^{n-1}{a}_{j,2}{x}^j}$ .

Now, assume that two polynomials are to be multiplied. Then,High half will be $H_i\left(x\right)={\displaystyle {\sum }_{j=n/2}^{n-1}{a}_{j,i}{x}^j}$ and Low half will be $L_i\left(x\right)={\displaystyle {\sum }_{j=n/2}^{n/2-1}{a}_{j,i}{x}^j}$ wherei =1,2….and so on.

Since, it is known that $P_i\left(x\right)=H_i\left(x\right)x^{n/2}+L_i\left(x\right)$ wherei =1,2…and so on.Therefore, by multiplication of two polynomials following is obtained:

  $P_1(x)\cdot P_2(x)=\left(H_1(x)\cdot H_2(x)\right)x^n+\left(H_1(x)+L_1(x)\right)\cdot \left(H_2(x)+L_2(x)\right)-$

  $\left(H_1(x)\cdot H_2(x)-L_1(x)\cdot L_2(x)\right)x^{n/2}+L_1(x)\cdot L_2(x)$

Now on using master’s theorem the recurrence for above is calculatedto be as follows:

  $T(n)=3T(n/2)+\theta (n)$

  $\theta \left(n^{\lg (n)}\right)$

Method2(for dividingthe input polynomial coefficients based onif the index is even or odd the procedure):

Assume the odd index beO_iand even index be E_isuch that $O_i\left(x\right)={\displaystyle {\sum }_{j=0}^{n/2-1}{a}_{2j+1,j}{x}^j}$ and $E_i\left(x\right)={\displaystyle {\sum }_{j=0}^{n/2-1}{a}_{2j,j}{x}^j}$ where i goes from 1,2, 3… and so on.

Then, $P_i=xO\left(x^2\right)+E_i\left(x^2\right)$

Therefore,

  $P_1(x)\cdot P_2(x)=x^2\left(O_1\left(x^2\right)\cdot O_2\left(x^2\right)\right)+x\left(O_1\left(x^2\right)+E_1\left(x^2\right)\right)\left(O_2\left(x^2\right)+E_1\left(x^2\right)\right)-\left(O_1\left(x^2\right)\cdot O_2\left(x^2\right)-E_1\left(x^2\right)\cdot E_2\left(x^2\right)\right)+E_1\left(x^2\right)\cdot E_2\left(x^2\right)$

Now on using master’s theorem the recurrence for above is calculatedto be as follows:

  $T(n)=3T(n/2)+\theta (n)$

  $\theta \left(n^{\lg (n)}\right)$

c.

Program Plan Intro

To show methodto multiply two n-bit integers in $O\left(n^{\lg 3}\right)$ steps.

Explanation of Solution

To multiply two n-bit integers in $O\left(n^{\lg 3}\right)$ steps, take two integers P₁ and P₂ such that

  $P_1={\displaystyle \sum _{k=0}^{\lfloor \lg \left(A_1\right)\rfloor }{a}_{k,1}{2}^k}$ and $P_2={\displaystyle \sum _{k=0}^{\lfloor \lg \left(A_2\right)\rfloor }{a}_{k,2}{2}^k}$ .

The generalization of the polynomial can be given as $f_1={\displaystyle \sum _{k=0}^{\lfloor \lg \left(A_i\right)\rfloor }{a}_{k,i}{x}^i}$ .

The two n-bit integers can be taken as $P{1n}_{}{P}_{1n-1}\mathrm{........}{P}_1$ and $P{2n}_{}{P}_{2n-1}\mathrm{........}{P}_2$ where $0\le P_{1i}\le 10$ and $0\le P_{2i}\le 10$ . The value P_1i and P_2i represent the number on every digit i = {1,2,3…n}

  $P_{1n}{10}^{n-1}+P_{1n-1}{10}^{n-2}+\dots \dots .+P_{12}10+P_{11}$

  $P_{2n}{10}^{n-1}+P_{2n-1}{10}^{n-2}+\dots \dots +P_{22}10+P_{21}$

These two algorithms are developed to solve the multiplication problem of polynomialwith run time of $O\left(n^{\lg 3}\right)$ by using divide and conquer. Each operationdeal with either P₁or P₂, they are of 1bit values.