# How to show that this algorithm for evaluating polynomials works?

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;
}

• Here's a starting hint : Suppose your professor only wants you to prove for the case that n = 0. Can you do it? Sep 17 '14 at 1:21
• Well, yeah. That would just mean I would suppose that n=0 and I would just go through the algorithm and then display the output which would simply be y = $a_0$ Sep 17 '14 at 1:24
• @TwilightSparkleTheGeek Kurt Mueller is right on this approach. You can try your code on different inputs. If you consider proving correctness as machine learning, then to prove that a piece of code (not algorithm) works, theoretically you want to prove that your specific piece of code partitions the input space into multiple parts. Then you use test case from each part to run the code. If your code is correct after a number of test cases, you are more confident that it will be correct for all inputs... Sep 17 '14 at 2:30
• The way to prove this has nothing to do with machine learning. You don't need to partition the input space (there is no partition of the input space here; everything is continuous and linear). The analogy to machine learning is not helpful here.
– D.W.
Sep 17 '14 at 2:53
• @TwilightSparkleTheGeek I thought you were going to ask for proving correctness of an implementation, so that's why I typed the typical view of testing (implementation). However, since your point here is about proving correctness of a small trick, then go with other people's suggestion, use induction. Or you can simply rewrite the formula as Decker has done. Sep 17 '14 at 3:04

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.

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.

• Okay, I understand this. I see, in class we are also learning proof by induction so more or less I'm new this technique, I just read it in my textbook. Sep 17 '14 at 3:41