0
$\begingroup$

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;
}
$\endgroup$
8
  • $\begingroup$ Here's a starting hint : Suppose your professor only wants you to prove for the case that n = 0. Can you do it? $\endgroup$ Sep 17, 2014 at 1:21
  • $\begingroup$ 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$ $\endgroup$ Sep 17, 2014 at 1:24
  • $\begingroup$ @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... $\endgroup$
    – InformedA
    Sep 17, 2014 at 2:30
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Sep 17, 2014 at 2:53
  • $\begingroup$ @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. $\endgroup$
    – InformedA
    Sep 17, 2014 at 3:04

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Sep 17, 2014 at 3:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.