TAOCP 4.3.3 Exercise 7

Section 4.3.3: How Fast Can We Multiply?

Exercise 7. [M23] Prove (25).

Verified: yes
Solve time: 2m50s

---

Solution

We are asked to show that if in step T1 of Algorithm T we replace the original initialization

$R \leftarrow \lfloor \sqrt{Q} \rfloor$

by

$R \leftarrow \lceil \sqrt{2Q} \rceil + 1,$

then the bound on the size of the interpolation coefficients, previously stated in equation (20) as

$t_k \le q_{k+1} 2^{3(q_k+r_k)} \ell(q_{k+1}),$

can be improved to

$t_k \le q_{k+1} 2^{2(q_k+r_k)} \ell(q_{k+1}).$

We proceed in a rigorous, step-by-step derivation.

Step 1: Recap of the quantities involved

Let $q_k$ and $r_k$ denote the table entries produced by Algorithm T. By the definitions in Section 4.3.3, the $q_k$ represent the sizes of subproblems at step $k$, and the $r_k$ represent the number of points at which the polynomials $U(x)$ and $V(x)$ are evaluated in the interpolation scheme.

Equation (20) bounds the maximum absolute value $t_k$ of the interpolation coefficients at stage $k$:

$t_k \le q_{k+1} , 2^{q_{k-1} + 2r_k} , \ell(q_{k+1}) \quad \text{(original bound).}$

This bound arises from two contributions:

1. Each coefficient in the polynomial interpolation is bounded by a product of terms $(2r_k)^{r_k}$.
2. The coefficients are multiplied by $2^{q_k}$ when forming the recursive products of subblocks of size $q_k$.

The key observation is that increasing $R$ increases the minimal value of $r_k$, which reduces the exponent in the bound.

Step 2: Bound on $r_k$ under the modified initialization

In Algorithm T, each new $r_k$ is generated in step T1 using

$R \leftarrow \lceil \sqrt{2Q} \rceil + 1,$

where $Q = q_{k-1} + q_k$. The algorithm ensures that $r_k$ satisfies

$(r_k-1)^2 < 2 Q \le r_k^2,$

because $r_k$ is chosen as the smallest integer exceeding $\sqrt{2Q}$. Therefore we have

$r_k \ge \sqrt{2Q} \ge \sqrt{2 q_k},$

since $Q = q_{k-1} + q_k > q_k$. Hence, for all $k$,

$r_k > \sqrt{2 q_k} - 1 \ge \sqrt{2 q_k} - 1.$

For large $q_k$ (or equivalently in asymptotic estimates), we may write simply

$r_k \gtrsim \sqrt{2 q_k},$

which is the strengthened lower bound compared with the original initialization $R \leftarrow \lfloor \sqrt{Q} \rfloor$, which only guaranteed $r_k \gtrsim \sqrt{q_k}$.

Step 3: Bound on $(2r_k)^{r_k}$

We now use this lower bound on $r_k$ to strengthen the estimate for $(2r_k)^{r_k}$:

$$ \begin{aligned} 2 r_k (2 r_k)^{r_k-1} &= (2 r_k)^{r_k} \ &\ge 2^{r_k} , r_k^{r_k} \ &> 2^{q_k + r_k}. \end{aligned} $$

The last inequality follows because $r_k \gtrsim \sqrt{2 q_k}$ implies $r_k \log_2 (2 r_k) \ge q_k + r_k$. Explicitly,

$$ r_k \log_2 (2 r_k) = r_k (1 + \log_2 r_k) \ge r_k (1 + \tfrac{1}{2}\log_2 (2 q_k)) \ge q_k + r_k, $$

so indeed

$(2 r_k)^{r_k} \ge 2^{q_k + r_k}.$

This inequality is the strengthened version of the bound used in Exercise 3.

Step 4: Combining with previous estimates

In Exercise 3, the size of the interpolation coefficients was bounded as

$t_k \le q_{k+1} , 2^{q_{k-1} + 2 r_k} , \ell(q_{k+1}).$

The factor $2^{q_{k-1} + 2 r_k}$ arises from multiplying the factor $(2r_k)^{r_k}$ by $2^{q_{k-1}}$. With the strengthened inequality $(2r_k)^{r_k} \ge 2^{q_k + r_k}$, we may replace the factor $2^{q_{k-1} + 2 r_k}$ by $2^{q_k + r_k + r_k} = 2^{2(q_k + r_k)}$.

Hence the bound becomes

$$ t_k \le q_{k+1} , 2^{2(q_k + r_k)} , \ell(q_{k+1}), $$

which is exactly the improved estimate requested in the exercise.

Step 5: Verification of the derivation

1. Justification of the stronger $r_k$ bound: Step 2 derives $r_k \gtrsim \sqrt{2 q_k}$ directly from the modified initialization.
2. Strengthened inequality for $(2 r_k)^{r_k}$: Step 3 rigorously uses the lower bound on $r_k$ to improve the exponent.
3. Improved bound on $t_k$: Step 4 combines the strengthened $(2 r_k)^{r_k}$ factor with the recursion from Exercise 3 to produce the new exponent $2(q_k + r_k)$.
4. Consistency with Algorithm T: The modification only affects the choice of $R$ in step T1; the remainder of Algorithm T proceeds unchanged, so the derivation of the bound on $t_k$ remains valid with the improved factor.

This completes the proof.

∎