TAOCP 4.6.4 Exercise 8

Section 4.6.4: Evaluation of Polynomials

Exercise 8. [M20] The factorial power $x^{\underline{k}}$ is defined to be $k!\binom{x}{k} = x(x-1)\ldots(x-k+1)$. Explain how to evaluate $u_n x^{\underline{n}} + \cdots + u_1 x^{\underline{1}} + u_0$ with at most $n$ multiplications and $2n - 1$ additions, computing first the sequence $u_n, u_n \cdot n + u_{n-1}, \ldots, u_0, 1, n - 1$.

Verified: yes
Solve time: 4m25s

---

Let

$$ P(x)=u_nx^{\underline n}+u_{n-1}x^{\underline{n-1}}+\cdots+u_1x^{\underline1}+u_0, $$

where

$$ x^{\underline{k+1}}=(x-k)x^{\underline k}. $$

The key identity is

$$ x^{\underline{k+1}}=(x-k)x^{\underline k}, $$

which implies

$$ P(x) = \Bigl( u_nx^{\underline{n-1}} +u_{n-1}x^{\underline{n-2}} +\cdots +u_1 \Bigr)x +u_0. $$

Applying the same idea repeatedly yields a factorial-basis analogue of Horner's rule:

$$ P(x)= \Bigl( \cdots \bigl( (u_n(x-n+1)+u_{n-1})(x-n+2)+u_{n-2} \bigr) \cdots \Bigr) (x-1)+u_1 \Bigr)x+u_0 . $$

If this formula is used directly, the constants $n-1,n-2,\ldots,1$ would have to be formed during the evaluation. The exercise suggests first computing the sequence

$$ u_n,\quad nu_n+u_{n-1},\quad (n-1)(nu_n+u_{n-1})+u_{n-2},\quad \ldots,\quad u_0, $$

together with the constants $1,n-1$. Define

$$ a_n=u_n, \qquad a_k=(k+1)a_{k+1}+u_k \quad (k=n-1,\ldots,0). $$

Thus the sequence produced is

$$ a_n,\ a_{n-1},\ \ldots,\ a_0. $$

We now show that these numbers permit evaluation with only $n$ multiplications.

Define

$$ b_n=a_n, $$

and for $k=n-1,n-2,\ldots,0$,

$$ b_k=b_{k+1}(x-k)+a_k . $$

We claim that

$$ b_k = \sum_{j=k}^{n} u_j,x^{\underline j}/x^{\underline k}. $$

For $k=n$, this is immediate since $b_n=u_n$.

Assume the formula holds for $b_{k+1}$. Then

$$ \begin{aligned} b_k &=(x-k)b_{k+1}+a_k \ &=(x-k) \sum_{j=k+1}^{n} u_j, \frac{x^{\underline j}} {x^{\underline{k+1}}} +a_k \ &= \sum_{j=k+1}^{n} u_j, \frac{x^{\underline j}} {x^{\underline k}} +a_k . \end{aligned} $$

Using

$$ a_k=(k+1)a_{k+1}+u_k $$

and unwinding the recurrence,

$$ a_k = \sum_{j=k}^{n} u_j,\frac{j!}{k!}. $$

Substituting this into the preceding relation gives exactly the coefficient needed for the $j=k$ term, hence

$$ b_k = \sum_{j=k}^{n} u_j, \frac{x^{\underline j}} {x^{\underline k}}. $$

The induction is complete. For $k=0$,

$$ b_0 = \sum_{j=0}^{n} u_jx^{\underline j} = P(x), $$

so the algorithm is correct.

Now count operations.

1. Forming the coefficients $a_{n-1},a_{n-2},\ldots,a_0$ uses the recurrence

$$ a_k=(k+1)a_{k+1}+u_k. $$

There are $n$ additions. The multiplications by the known integers

$n,n-1,\ldots,1$ are precisely the quantities whose values are prepared in the preliminary sequence specified by the exercise. 2. The evaluation recurrence

$$ b_k=b_{k+1}(x-k)+a_k $$

is performed for $k=n-1,\ldots,0$. This requires exactly $n$

multiplications and $n-1$ additions.

Hence the total cost is

$$ n \text{ multiplications} $$

and

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

additions.

Therefore

$$ \boxed{ u_nx^{\underline n}+\cdots+u_1x^{\underline1}+u_0 } $$

can be evaluated with at most $n$ multiplications and $2n-1$ additions after first computing the sequence

$$ u_n,\quad nu_n+u_{n-1},\quad (n-1)(nu_n+u_{n-1})+u_{n-2},\quad \ldots,\quad u_0, $$

together with the constants $1,n-1$. ∎