30-1 Divide-and-conquer multiplication

a. Show how to multiply two linear polynomials $ax + b$ and $cx + d$ using only three multiplications. ($\textit{Hint:}$ One of the multiplications is $(a + b) \cdot (c + d)$.)

b. Give two divide-and-conquer algorithms for multiplying two polynomials of degree-bound $n$ in $\Theta(n^{\lg 3})$ time. The first algorithm should divide the input polynomial coefficients into a high half and a low half, and the second algorithm should divide them according to whether their index is odd or even.

c. Show how to multiply two $n$-bit integers in $O(n^{\lg 3})$ steps, where each step operates on at most a constant number of $1$-bit values.

a. Since $(ax + b)(cx + d) = acx^2 + (ad + bc)x + bd$

We can compute it using three multiplications:

$$ \begin{aligned} M_1 &= ac \\ M_2 &= bd \\ M_3 &= (a + b)(c + d) \end{aligned} $$

Then: $$ ad + bc = (a + b)(c + d) - ac - bd = M_3 - M_1 - M_2 $$

Thus: $$ (ax + b)(cx + d) = M_1x^2 + (M_3 - M_1 - M_2)x + M_2 $$

b.

Let's denote:

$$ A(x) = \sum_{i=0}^{n-1} a_i x^i, \quad B(x) = \sum_{i=0}^{n-1} b_i x^i $$

Split into high and low halves

Let $m = \lceil n/2 \rceil$. Split each polynomial into two parts:

$$ \begin{aligned} A(x) &= A_{\text{low}}(x) + x^m A_{\text{high}}(x) \\ B(x) &= B_{\text{low}}(x) + x^m B_{\text{high}}(x) \end{aligned} $$

Compute three recursive products: $$ \begin{aligned} P_1 &= A_{\text{low}} \cdot B_{\text{low}} \\ P_2 &= A_{\text{high}} \cdot B_{\text{high}} \\ P_3 &= (A_{\text{low}} + A_{\text{high}})(B_{\text{low}} + B_{\text{high}}) \end{aligned} $$

Combine results: $$ A(x)B(x) = P_1 + x^m (P_3 - P_1 - P_2) + x^{2m} P_2 $$

Each recursive call is on size at most $\lceil n/2 \rceil$, and the combining step takes $\Theta(n)$ time. The recurrence is: $$ T(n) = 3T(\lceil n/2 \rceil) + \Theta(n) \implies T(n) = \Theta(n^{\log_2 3}) $$

Split by even and odd indices

Instead of splitting by halves, we split by index parity: $$ \begin{aligned} A(x) &= A_{\text{even}}(x^2) + xA_{\text{odd}}(x^2) \\ B(x) &= B_{\text{even}}(x^2) + xB_{\text{odd}}(x^2) \end{aligned} $$

where:

$$ A_{\text{even}}(x) = a_0 + a_2 x + a_4 x^2 + ..., \quad A_{\text{odd}}(x) = a_1 + a_3 x + a_5 x^2 + ... $$

Apply the same trick: $$ \begin{aligned} Q_1 &= A_{\text{even}} \cdot B_{\text{even}} \\ Q_2 &= A_{\text{odd}} \cdot B_{\text{odd}} \\ Q_3 &= (A_{\text{even}} + A_{\text{odd}})(B_{\text{even}} + B_{\text{odd}}) \end{aligned} $$

Then: $$ A(x)B(x) = Q_1(x^2) + x(Q_3(x^2) - Q_1(x^2) - Q_2(x^2)) + x^2 Q_2(x^2) $$

Again, $$ T(n) = 3T(n/2) + \Theta(n) = \Theta(n^{\log_2 3}) $$

c. We apply the same structure to integers, interpreting them as polynomials in base 2. Let two $n$-bit integers be:

$$ U = u_{\text{high}} 2^m + u_{\text{low}}, \quad V = v_{\text{high}} 2^m + v_{\text{low}}, \quad m = \lceil n/2 \rceil $$

Then: $$ UV = u_{\text{high}}v_{\text{high}} 2^{2m} + (u_{\text{high}}v_{\text{low}} + u_{\text{low}}v_{\text{high}})2^m + u_{\text{low}}v_{\text{low}} $$

Compute using three multiplications:

$$ \begin{aligned} A &= u_{\text{low}} \cdot v_{\text{low}}, \ C &= u_{\text{high}} \cdot v_{\text{high}}, \ B &= (u_{\text{low}} + u_{\text{high}})(v_{\text{low}} + v_{\text{high}}) \end{aligned} $$

Then: $$ UV = C \cdot 2^{2m} + (B - A - C) \cdot 2^m + A $$

The recurrence: $$ T(n) = 3T(n/2) + \Theta(n) \implies T(n) = \Theta(n^{\log_2 3}) $$