TAOCP 4.6.4 Exercise 1

Section 4.6.4: Evaluation of Polynomials

Exercise 1. [15] What is a good way to evaluate an "odd" polynomial

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

Verified: yes
Solve time: 1m12s

---

Solution

Write the polynomial in the form

$$ u(x)=x\bigl(u_{2n+1}x^{2n}+u_{2n-1}x^{2n-2}+\cdots+u_1\bigr). $$

Let

$$ y=x^2. $$

Then

$$ u(x)=x,v(y), $$

where

$$ v(y)=u_{2n+1}y^n+u_{2n-1}y^{n-1}+\cdots+u_1. $$

The polynomial $v(y)$ has degree $n$, so Horner's rule applied to $v$ gives

$$ v(y) = (\cdots((u_{2n+1}y+u_{2n-1})y+u_{2n-3})y+\cdots)y+u_1. $$

Therefore

$$ u(x) = x\Bigl((\cdots((u_{2n+1}x^2+u_{2n-1})x^2+u_{2n-3})x^2+\cdots)x^2+u_1\Bigr). $$

To evaluate $u(x)$:

1. Compute $y=x^2$.
2. Evaluate $v(y)$ by Horner's rule.
3. Multiply the result by $x$.

The operation count is:

• one multiplication to obtain $y=x^2$;
• $n$ multiplications and $n$ additions in Horner's rule for the degree-$n$ polynomial $v$;
• one final multiplication by $x$.

Hence the total cost is

$$ n+2 $$

multiplications and

$$ n $$

additions.

Ordinary Horner evaluation of the degree-$2n+1$ polynomial would require $2n+1$ multiplications and $2n+1$ additions. Exploiting the odd structure therefore saves

$$ (2n+1)-(n+2)=n-1 $$

multiplications and

$$ (2n+1)-n=n+1 $$

additions.

Thus a good way to evaluate an odd polynomial is to regard it as $x$ times a polynomial in $x^2$ and apply Horner's rule to that polynomial:

$$ \boxed{ u(x) = x\Bigl((\cdots((u_{2n+1}x^2+u_{2n-1})x^2+u_{2n-3})x^2+\cdots)x^2+u_1\Bigr). } $$