TAOCP 4.6.4 Exercise 2

Let $u(x) = u_n x^n + u_{n-1} x^{n-1} + \cdots + u_1 x + u_0$ be a polynomial over a ring $R$, and suppose we wish to compute $u(x)$ where $x$ itself is a polynomial, or more generally an element of a...

taocpmathematicsalgorithmsvolume-2math-medium

Section 4.6.4: Evaluation of Polynomials

Exercise 2. ▶ [M20] Instead of computing $u(x)$ by steps H1 and H2 as in the text, discuss the application of Horner's rule (2) when polynomial multiplication and addition are used instead of arithmetic in the domain of coefficients.

Verified: yes
Solve time: 1m13s

Solution

Let

$u(x) = u_n x^n + u_{n-1} x^{n-1} + \cdots + u_1 x + u_0$

be a polynomial over a ring $R$, and suppose we wish to compute $u(x)$ where $x$ itself is a polynomial, or more generally an element of a nontrivial algebra over $R$. That is, the arithmetic operations $+$ and $\cdot$ in Horner's rule (2) are interpreted as polynomial addition and multiplication rather than scalar operations.

Horner's rule (2) states

$u(x) = (\cdots((u_n x + u_{n-1}) x + u_{n-2}) x + \cdots + u_1)x + u_0.$

When $x$ is a polynomial, each step consists of two operations:

  1. Multiplying the current accumulator by the polynomial $x$.
  2. Adding the next coefficient $u_k$, which may also be a polynomial.

Let $v_k$ denote the accumulator after processing the $k$th coefficient:

$$ v_n = u_n, \qquad v_{k} = v_{k+1} \cdot x + u_k, \quad k = n-1, n-2, \ldots, 0. $$

Then $v_0 = u(x)$. This defines a recursion identical to the standard Horner scheme, except that $+$ and $\cdot$ are interpreted in the algebra of polynomials. Each multiplication $v_{k+1} \cdot x$ increases the degree of the accumulator by $\deg(x)$, so the degrees of the intermediate results are bounded by

$$ \deg(v_k) \le n-k + \deg(x) \quad \text{(more precisely, } \deg(v_k) = n \cdot \deg(x) \text{ if } \deg(u_n) = 0\text{)}. $$

No intermediate results need to be stored beyond the current $v_k$, since each $v_{k}$ depends only on $v_{k+1}$ and $u_k$. Therefore the memory requirement is minimal: a single polynomial accumulator suffices.

If $x$ has special structure, further simplifications can reduce the number of multiplications. For instance, if $x$ is sparse or factorizable, we may precompute powers of $x$ or subexpressions and reuse them. Nevertheless, the essential property remains: Horner's rule minimizes the number of multiplications required, performing exactly $n$ polynomial multiplications and $n$ polynomial additions.

The generalization is therefore straightforward: interpret the scalar operations in Horner's scheme as polynomial operations. The algorithm proceeds as in steps H1 and H2 of the text:

H1. Set $v_n \leftarrow u_n$.

H2. For $k = n-1, n-2, \ldots, 0$, set

$$ v_k \leftarrow v_{k+1} \cdot x + u_k. $$

H3. Return $v_0 = u(x)$.

This procedure computes $u(x)$ in exactly $n$ multiplications and $n$ additions in the algebra of polynomials, with no unnecessary storage. Each intermediate $v_k$ is a polynomial of degree at most $n \deg(x)$, and the computation preserves the algebraic structure.

This completes the solution.

∎