Say that you are interested in the value of the quadratic...
3X2 - 8X + 4
...for several values of X. Write a program that has a double precision variable X. Assign a value to it. Write statement that computes a value for the quadratic and stores the result in another double precision variable. Finally write out the result, something like:
At X = 4.0 the value is 20.0

 

... And your question is...?

 

Moved from Programmer's Corner to Homework Help.

 

Take your best shot at solving the problem and post it here (please use CODE tags to make your post more readable). Remember comments!

We can then review your code and make suggestions to help steer you in the right direction.

 

You can use synthetic division faster than writing a program.

 

You can use synthetic division faster than writing a program.

Though since the assignment is to write a program, they may not get a lot of credit if they go that route.

Also, I'm not seeing how synthetic division even enters into this. But, then again, I've never done much with synthetic division as dividing one polynomial by another always seemed very straight-forward to me and it's something that I can do even if it's been years and years since I've done it, where as synthetic division has always seemed to be a cookbook recipe procedure that one has to pretty much just memorize and I'm just not good at that.

 

You can use synthetic division faster than writing a program.

He's not being asked to divide two polynomials, he's just being asked to evaluate a polynomial given an assignment for x.

OP, nobody is going to do your homework for you. Try it and ask specific questions if you get stuck.

 

And it is a little known fact that synthetic division can ALSO be used to evaluate a polynomial. As such it can also be used as the basis of a program.

 

And it is a little known fact that synthetic division can ALSO be used to evaluate a polynomial. As such it can also be used as the basis of a program.

What are you talking about? How can synthetic division be used to evaluate a polynomial? Evaluating means plugging in a value for x, raising it to whatever degree that term has, multiplying the result by the coefficient, and then adding up all the terms. There's no shortcut or trick, if you have a 4x^2, you have to replace x with its assignment, square it, then multiply the result by 4. He's not root-finding, he's just doing arithmetic.

 

And it is a little known fact that synthetic division can ALSO be used to evaluate a polynomial. As such it can also be used as the basis of a program.

I'm also not seeing how it would be the basis for such a program. Perhaps an example might shed some light.

To use something different, but similar, to the OP's problem, what if the polynomial in question was

5x² - 7x + 9

and we wanted to evaluate it for several values of x, say x=4 to x=6 in 0.1 increments.

I can see some games that could be played to exploit the uniform increment, though whether any of them made things easier is debatable. But I don't see how synthetic division could be employed and would be interested in finding out.

 

  __4__ |  5    -7     9
                20    52
          ----------------
           5    13    61

1. Write the coefficients and the value of x to be used in the evaluation on the top line
2. Bring the first coefficient (5) down below the dotted line
3. Multiply (5) by (4) to get (20) and place that result underneath the (-7)
4. Add (-7) and (20) to get (13)
5. Multiply (13) by (4) to get (52)
6. Add (52) and (9) to get (61)

(61) is the value of the polynomial at x=4
For x = 4.1 the result is 63, and so on upto x = 6
If you count the basic operations, it is 2 multiplies and 2 additions, which is more efficient algorithmiclly than a straight forward evaluation.

We used to use this rapid evaluation technique to find sign changes which help to locate zeros of cubic and higher order polynomials, in the days before calculators.

 

What are you talking about? How can synthetic division be used to evaluate a polynomial? Evaluating means plugging in a value for x, raising it to whatever degree that term has, multiplying the result by the coefficient, and then adding up all the terms. There's no shortcut or trick, if you have a 4x^2, you have to replace x with its assignment, square it, then multiply the result by 4. He's not root-finding, he's just doing arithmetic.

You are just plain wrong and I'm sorry your mind is closed.
http://www.mesacc.edu/~scotz47781/mat120/notes/divide_poly/remainder/remainder_thm.html

It is called the "remainder theorem"

 

Ok, you definitely showed me. Apparently called Horner's method.

 

Ok, you definitely showed me. Apparently called Horner's method.

Only by virtue of paying attention in Mrs Gray's 7th grade math class. This was neat stuff to a 12 year old.

 

Thanks. I don't see it as being any more efficient, but it's useful to see the technique. I'll study it to make sure I know how it works.

The reason I don't see it as being any more efficient is because you can trivially rewrite the equation as:

y = 5x² - 7x + 9 = x(5x - 7) + 9

So let's evaluate it at x=4.

1) Take the value of x and multiply it by 5. (4·5 = 20)
2) Add -7. (20 + -7 = 13)
3) Multiply this by x. (4·13 = 52)
4) Add 9. (52 + 9 = 61)

Notice that this is not only the same number of operations, but that the operations and the order in which they are performed are exactly the same.

My guess is that the synthetic division approach is doing nothing except this exact same factoring out process. But the factoring out process outlined above is glaringly obvious both how to do it and why it is valid. The synthetic division, as described, seems to be nothing more than a set of memorized steps that are thrown at a problem without understanding (not that I am in any way claiming that YOU don't understand it, but only that I suspect most people that would use it would fall into that category).

Notice that this approach is trivially extensible to any order polynomial. For instance:

y = ax^3 + bx^2 + cx + d = x(x(ax+b)+c)+d

A more general form would be:

y = (((a)x+b)x+c)x+d

which lends itself to direct RPN or other stack-oriented evaluation.

Notice that either approach requires 2x & 2+ per evaluation so if we want to evaluate 21 points (using my example, for example), then we would perform 42x & 42+.

Can we do better?

Yep.

Note that

y(x) = ax² + bx + c

y(x+Δ) = a(x+Δ)² + b(x+Δ) + c
y(x+Δ) = a(x²+2xΔ+Δ²) + b(x+Δ) + c
y(x+Δ) = ax² + 2aΔx + aΔ² + bx + bΔ + c
y(x+Δ) = (ax² + bx + c) + [2aΔ]x + [(Δa+b)Δ]
y(x+Δ) = y(x) + Ax + B
A = 2aΔ
B = (Δa+b)Δ

Our first evaluation requires the same four operations (2x & 2+). Evaluating the A requires 2x and evaluating B requires 2x & 1+.

After that, we can evaluate the next y(x) in the sequence with just 1x & 2+.

So evaluating N points directly requires 2Nx & 2N+ operations.
Doing it incrementally requires (N+5)x & (2N+1)+ operations (for N>1)

We will always do one more add operation this way, but we will do (N-5) fewer multiplication operations, which are generally much more expensive. So we start realizing a net gain in computational efficiency for N>5. For N=21, we would have 26x & 43+.

 

I would argue that efficient factorization of polynomials for rapid evaluation may be glaringly obvious to some, but less so to the vast majority. I'm not sure I could offer a proof of the Remainder Theorem, also known as Horner's Method, but I think it fits into a higher category than a "memorized sequence of steps". Ya need to come off yer high horse cuz they are really the same thing - surprise surprise.

 

I would argue that efficient factorization of polynomials for rapid evaluation may be glaringly obvious to some, but less so to the vast majority. I'm not sure I could offer a proof of the Remainder Theorem, also known as Horner's Method, but I think it fits into a higher category than a "memorized sequence of steps". Ya need to come off yer high horse cuz they are really the same thing - surprise surprise.

Again, I'm not suggesting -- and tried to be ultra explicit about that point -- that YOU do not understand why and how it works. I would still maintain, though, that the lion's share of people that would use it WOULD just be memorizing it. In fact, when I went out and did a Google search on synthetic division, every site I looked at (and that was only about half a dozen, so not extensive by any means) placed it squarely in the "memorize these steps" category. None of them developed it, justified it, or did anything except say, "Do this, then do this, then do this, then write the result by taking rewriting these numbers like this." That in no way says anything about the utility, beauty, elegance, or power of the method itself, only that it would appear that it is typically thrown out as a cookbook algorithm used largely by people that neither have, nor want, any desire to understand why what they are doing works.

I'm not surprised at all that they are really the same thing. In fact, I seem to recall saying something like, "My guess is that the synthetic division approach is doing nothing except this exact same factoring out process."

As for the efficient factorization of polynomials, notice that the approach I was discussing did not involve factoring polynomials at all.

As for a proof of why it works, I think that is fairly straightforward, though I'm winging it and probably won't come up with the most direct or rigorous proof.

If we have some polynomial, f(x), that we want to evaluate at a particular point, x=a, then it appears from your synthetic division approach that you divided the original polynomial by (x-a). So let's see where that leads us. When we divide f(x) by (x-a) we will get a new polynomial, g(x), and, in general, some remainder R (which, since (x-a) is of degree one, will be a constant). These will be related by

\(
\frac{f(x)}{(x-a)} \; = \; g(x) + \frac{R}{(x-a)}
\)

This means that
\(
f(x) \; = \; g(x) \cdot (x-a) + R
\)

If we set x equal to a, then (x-a) is identically zero, leaving only R

\(
f(a) \; = \; g(a) \cdot (a-a) + R \; = \; R
\)

 

Sounds like a job for MatLab.