TAOCP 4.6.4 Exercise 22

Section 4.6.4: Evaluation of Polynomials

Exercise 22. [**] [18] What is the scheme for evaluating $x^9 - 3x^5 + x^4 - 2x^3 + x^2 - 3x - 1$, using Pan's method (16)?

Verified: yes
Solve time: 3m59s

Exercise 4.6.4.22

Evaluate

$$ u(x)=x^9-3x^5+x^4-2x^3+x^2-3x-1 $$

using Pan's method (16).

Pan's method groups the coefficients according to their exponents modulo $m$. Since the degree is $9=3^2$, we take $m=3$ and write the polynomial in the form

$$ u(x)=Q_0(y)+xQ_1(y)+x^2Q_2(y), \qquad y=x^3. $$

Collecting terms with exponents congruent to $0,1,2 \pmod 3$,

$$ \begin{aligned} Q_0(y) &=y^3-2y-1,\[2mm] Q_1(y) &=y-3,\[2mm] Q_2(y) &=-3y+1. \end{aligned} $$

Indeed,

$$ \begin{aligned} Q_0(y)+xQ_1(y)+x^2Q_2(y) &=(y^3-2y-1)+x(y-3)+x^2(-3y+1)\ &=x^9-2x^3-1+x^4-3x-3x^5+x^2\ &=x^9-3x^5+x^4-2x^3+x^2-3x-1. \end{aligned} $$

Now evaluate the three coefficient polynomials. Since $Q_1$ and $Q_2$ are linear in $y$, only $Q_0$ requires a Horner step:

$$ Q_0(y)=((y)y-2)y-1. $$

Hence the Pan evaluation scheme is

$$ \boxed{ \begin{aligned} t &\leftarrow x^2,\ y &\leftarrow xt ;(=x^3),\ a &\leftarrow -3y+1,\ b &\leftarrow y-3,\ c &\leftarrow ((y)y-2)y-1,\ u &\leftarrow (ax+b)x+c. \end{aligned} } $$

Verification:

$$ (ax+b)x+c = x^2(-3y+1)+x(y-3)+(y^3-2y-1) = u(x), $$

with $y=x^3$. Therefore this is the evaluation scheme obtained from Pan's method (16).