TAOCP 4.6.4 Exercise 32

**Corrected Solution for Exercise 4.

taocpmathematicsalgorithmsvolume-2math-simple

Section 4.6.4: Evaluation of Polynomials

Exercise 32. [M2] Find a polynomial chain of minimum possible length that can compute all polynomials of the form $u_1 x^3 + u_2 x^2 + u_0$; and prove that its length is minimal.

Verified: no
Solve time: 9m09s

Corrected Solution for Exercise 4.6.4.32 [M2]

We are asked to find a polynomial chain of minimum possible length that computes all polynomials of the form

$$ u_1 x^3 + u_2 x^2 + u_0 $$

with parameters $u_0,u_1,u_2$ arbitrary, and to prove that the length is minimal.

Step 1: Exhibit a polynomial chain

Consider the identity

$$ u_1x^3 + u_2x^2 + u_0 = (u_1 x + u_2)x^2 + u_0. $$

A corresponding polynomial chain is

$$ \begin{aligned} t_1 &\leftarrow x \cdot x, \ t_2 &\leftarrow u_1 \cdot x, \ t_3 &\leftarrow t_2 + u_2, \ t_4 &\leftarrow t_3 \cdot t_1, \ t_5 &\leftarrow t_4 + u_0. \end{aligned} $$

Then

$$ t_5 = (u_1 x + u_2)x^2 + u_0 = u_1 x^3 + u_2 x^2 + u_0, $$

so every polynomial in the family is computed with $5$ replacements.

Thus a chain of length $5$ exists.

Step 2: Prove minimality

Let a polynomial chain have length $L$, with $m$ multiplications and $a$ additions or subtractions, so that $L = m + a$.

We must show that any chain computing all polynomials in the family satisfies $L \ge 5$.

(a) Lower bound on multiplications

Let $\deg(p)$ denote the degree of a polynomial $p$ in $x$ after a chain step. Initially, $x$ has degree $1$ and parameters $u_i$ have degree $0$.

A multiplication increases degree by at most the sum of the degrees of its two factors. To obtain a cubic term $u_1 x^3$, we need at least two multiplications:

  1. A single multiplication of two degree-$1$ polynomials produces degree at most $2$. Therefore one multiplication cannot yield $x^3$.
  2. Two multiplications suffice, but we must verify whether two multiplications can yield all polynomials in the family.

Assume there is a chain with exactly $m=2$ multiplications that computes all polynomials $u_1x^3 + u_2x^2 + u_0$.

  • Let $M_1$ be the first multiplication and $M_2$ the second.
  • After $M_1$, the output has degree at most $2$. Let the result of $M_1$ be $p_2(x)$.
  • The second multiplication $M_2$ must produce a cubic term. Let the other factor in $M_2$ be $q(x)$. Then

$$ M_2: p_2(x) \cdot q(x) = r(x) \text{ of degree } 3. $$

(b) Analysis of possible forms

All quantities before the first multiplication are affine in $x$ (degree $\le 1$). Hence $p_2(x)$ is at most quadratic in $x$:

$$ p_2(x) = \alpha x^2 + \beta x + \gamma, $$

where $\alpha,\beta,\gamma$ are linear combinations of the parameters $u_0,u_1,u_2$ used so far. Similarly, $q(x)$ is affine:

$$ q(x) = \delta x + \epsilon. $$

Then the second multiplication yields

$$ r(x) = p_2(x) \cdot q(x) = \alpha\delta x^3 + (\alpha\epsilon + \beta\delta)x^2 + (\beta\epsilon + \gamma\delta)x + \gamma\epsilon. $$

To match the desired family $u_1 x^3 + u_2 x^2 + u_0$, the coefficient of $x$ must vanish:

$$ \beta \epsilon + \gamma \delta = 0 $$

for all $u_1,u_2,u_0$. Similarly, the constant term must satisfy

$$ \gamma \epsilon = u_0. $$

(c) Contradiction

Since $u_0$ is arbitrary, $\gamma$ and $\epsilon$ must be able to produce any value $u_0$. Therefore at least one of $\gamma$ or $\epsilon$ must depend nontrivially on $u_0$. But then $\beta \epsilon + \gamma \delta$ becomes nonzero for some choice of parameters, producing a nonzero coefficient for $x$.

Hence it is impossible to realize all polynomials $u_1x^3 + u_2x^2 + u_0$ with only two multiplications. Therefore

$$ m \ge 3. $$

(d) Lower bound on additions

To introduce all parameters independently:

  • $u_2$ appears in the $x^2$ term. Since it is independent of $u_1$, there must be an addition introducing $u_2$ into the quadratic term.
  • $u_0$ appears in the constant term. Another addition is required to introduce $u_0$ independently.

Hence

$$ a \ge 2. $$

Step 3: Combine bounds

Combining (c) and (d), any polynomial chain computing all members of $\mathcal F$ satisfies

$$ L = m + a \ge 3 + 2 = 5. $$

Step 4: Conclusion

We exhibited a chain of length $5$, and any chain must have length at least $5$. Therefore the minimum length is

$$ \boxed{5}. $$

The chain

$$ t_1 = x^2,\quad t_2 = u_1 x,\quad t_3 = t_2 + u_2,\quad t_4 = t_3 t_1,\quad t_5 = t_4 + u_0 $$

achieves this minimum.

Answer:

$$ \text{Minimum length of a polynomial chain computing } u_1 x^3 + u_2 x^2 + u_0 \text{ is } 5. $$