TAOCP 4.6.4 Exercise 5

Let u(x)=u_nx^n+u_{n-1}x^{n-1}+\cdots+u_1x+u_0 .

taocpmathematicsalgorithmsvolume-2math-simple

Section 4.6.4: Evaluation of Polynomials

Exercise 5. [M15] Count the number of multiplications and additions required by the second-order rule (4).

Verified: yes
Solve time: 2m28s

Solution

Let

$$ u(x)=u_nx^n+u_{n-1}x^{n-1}+\cdots+u_1x+u_0 . $$

The second-order rule (4) groups terms in pairs and rewrites the polynomial in the nested form

$$ u(x)= \bigl(\cdots((u_nx+u_{n-1})x+u_{n-2})x+\cdots\bigr), $$

with the nesting carried out two powers at a time. Equivalently, if we set

$$ y=x^2, $$

the second-order rule has the form

$$ u(x) = (\cdots((a_ry+a_{r-1})y+a_{r-2})\cdots)y+a_0 + x\bigl((\cdots((b_sy+b_{s-1})y+b_{s-2})\cdots)y+b_0\bigr), $$

where the coefficients $a_i$ are the even-indexed coefficients of $u(x)$ and the $b_i$ are the odd-indexed coefficients. This is precisely the structure represented by rule (4).

To count the operations required, observe that the computation proceeds as follows.

1. Compute $y=x^2$

This requires

$$ 1 $$

multiplication.

2. Evaluate the even-coefficient part

If $n=2m$, the even part contains $m+1$ coefficients and therefore has degree $m$ in $y$. Horner's rule requires

$$ m \text{ multiplications},\qquad m \text{ additions}. $$

If $n=2m+1$, the even part again has degree $m$, so the same count holds.

3. Evaluate the odd-coefficient part

If $n=2m$, the odd part contains $m$ coefficients and has degree $m-1$ in $y$. Horner's rule requires

$$ m-1 \text{ multiplications},\qquad m-1 \text{ additions}. $$

If $n=2m+1$, the odd part has degree $m$, requiring

$$ m \text{ multiplications},\qquad m \text{ additions}. $$

4. Form the final combination

The rule ends with

$$ u(x)=E(y)+x,O(y), $$

where $E$ and $O$ denote the even and odd parts already evaluated.

This requires

$$ 1 $$

multiplication and

$$ 1 $$

addition.

Total count when $n=2m$

Multiplications:

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

Additions:

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

Total count when $n=2m+1$

Multiplications:

$$ 1+m+m+1=2m+2=n+1. $$

Additions:

$$ m+m+1=2m+1=n. $$

Thus, in both cases, the second-order rule (4) requires

$$ \boxed{n+1\ \text{multiplications}} $$

and

$$ \boxed{n\ \text{additions}}. $$

Therefore the operation count for the second-order rule (4) is

$$ \boxed{n+1 \text{ multiplications and } n \text{ additions}.} $$