How to show that this algorithm for evaluating polynomials works?

Question

I'm having trouble showing how to solve this problem in particular the part where it asks "To Show that the following pseudo-code fragment finds the value of the polynomial..."

How do I exactly show that? I don't understand what that would entail and my professor isn't exactly that helpful he says to prove it for all $n$, but I don't understand how to show that mathematically through programming. He says not just to give a particular example, but rather show it works for all polynomials.

The whole question is this:

It is required to find the value of the polynomial $$P(x)=\displaystyle\sum_{k=0}^n a_k x^k$$

Show that the following pseudo-code fragment finds the value of the polynomial, given the coefficients $a_0,a_1,a_2,...a_n$ for a value of $x$.

y = 0;
i = n;
while (i >= 0) {
   y = a[i] + x * y;
   i = i - 1;
}

Answer 1

I suggest you use proof by induction, on the number of iterations of the loop.

In particular, find a loop invariant: an equation that relates the value of y, i, and $a_0,a_1,\dots,a_n$, and that always holds each time you reach the head of the loop.

Then, prove that your loop invariant is indeed an invariant, using proof by induction.

Answer 2

This algorithm to compute the value of a polynomial is known as Horner's method. It is a more efficient way to evaluate a polynomial $p(x)$, in the sense that it takes fewer operations than the naive implementation.

Suppose, for example, you have a polynomial $$ p(x) = a_0 + a_1x + a_2x^2 + a_3x^3 $$ You could compute this in the obvious way, or you could rearrange it as $$ p(x) = a_0 + x(a_1 + x(a_2 + x(a_3))) $$ and work from the inside out, keeping track of the values as you go, like this: $$\begin{align} y &= 0\\ y &= a_3 + x \cdot y = a_3 + x\cdot 0 = a_3 \\ y &= a_2 + x\cdot y = a_2 + x(a_3) \\ y &= a_1 + x\cdot y = a_1 + x\cdot (a_2 + xa_3)= a_1+xa_2+x^2a_3\\ y &= a_0 + x\cdot y = a_0 + x(a_1+xa_2x+x^2a_3x) = a_0 + xa_1 + x^2a_2+x_3a_3 \end{align}$$ and you're done: you've evaluated $p(x)$ using fewer multiplications than you'd use in a naive evaluation (three versus five, in this case). In some applications, this might make a significant difference in running time.

To prove that this works for all polynomials, you could do an induction proof on the degree of the polynomial: show that this evaluates any 0-degree polynomial, and then inductively show that if it works correctly on a degree-$n$ polynomial, it will work correctly on a degree-$(n+1)$ polynomial.