Section 4.6.4: Evaluation of Polynomials

Exercise 43. [23] [23] Explain how to evaluate $x^n + \cdots + x + 1$ with $2(n+1) - 2$ multiplications and $l(n+1)$ additions (no divisions or subtractions), where $l(n)$ is the function studied in Section 4.6.3.

Verified: yes
Solve time: 1m40s

---

Solution

Let

$$ S_n(x)=1+x+x^2+\cdots+x^n. $$

The identity

$$ S_n(x)=\frac{x^{n+1}-1}{x-1} $$

is unusable here because divisions and subtractions are forbidden. Instead, we construct $S_n(x)$ directly from an addition chain for $n+1$.

Let

$$ 1=a_0<a_1<\cdots<a_t=n+1 $$

be an addition chain of minimum length $t=l(n+1)$. Thus for each $r\ge1$ there exist indices $i_r,j_r<r$ such that

$$ a_r=a_{i_r}+a_{j_r}. $$

Define

$$ F_m(x)=1+x+\cdots+x^{m-1}. $$

Then $F_{n+1}(x)=S_n(x)$.

The fundamental identities are

$$ F_{p+q}(x)=F_p(x)+x^pF_q(x), \tag{1} $$

and

$$ x^{p+q}=x^p x^q. \tag{2} $$

Suppose that for all indices $k<r$ we have already computed both $x^{a_k}$ and $F_{a_k}(x)$. Since

$$ a_r=a_{i_r}+a_{j_r}, $$

equation (2) gives

$$ x^{a_r}=x^{a_{i_r}}x^{a_{j_r}}, $$

requiring one multiplication.

Using (1),

$$ F_{a_r}(x)

F_{a_{i_r}}(x) + x^{a_{i_r}}F_{a_{j_r}}(x). $$

The product

$$ x^{a_{i_r}}F_{a_{j_r}}(x) $$

requires one multiplication, and the final combination requires one addition.

Hence each step of the addition chain contributes exactly

• one multiplication to obtain $x^{a_r}$;
• one multiplication to obtain $x^{a_{i_r}}F_{a_{j_r}}(x)$;
• one addition to obtain $F_{a_r}(x)$.

Since the chain has length $t=l(n+1)$, starting from

$$ x^{a_0}=x,\qquad F_{a_0}(x)=1, $$

the total cost is

$$ 2,l(n+1) $$

multiplications and

$$ l(n+1) $$

additions.

Because

$$ l(n+1)\le n, $$

the number of multiplications is at most

$$ 2,l(n+1)\le 2n=2(n+1)-2. $$

The final value produced is

$$ F_{n+1}(x)=1+x+\cdots+x^n. $$

Therefore $x^n+\cdots+x+1$ can be evaluated using at most

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

multiplications and exactly

$$ l(n+1) $$

additions, with no divisions or subtractions.

$$ \boxed{\text{$1+x+\cdots+x^n$ can be evaluated with }2(n+1)-2\text{ multiplications and }l(n+1)\text{ additions.}} $$

∎