These exercises demonstrate several ways of evaluating a 10-degree polynomial. The polynomial is formed from the ten roots

1/3 8/7 2.1 3.2 4.3 5.4 6.6 7.7 8.8 9.9 and has the following floating point coefficients to machine accuracy (from low to high power, that is, from a0 to a10)

263181.10629888007 a0 -1467883.5529881604 2745869.426605989 -2535885.7388542863 1348084.367903810 -444015.39169047633 93545.52310952383 -12616.661904761906 1052.9380952380952 -49.476190476190481 1.0 a10 a) Make a spreadsheet to evaluate the polynomial by i. product of linear factors ii. linear combination of powers (I suggest you cut and paste the coefficients from the online version of this assignment) iii. Horner's Method Be sure to set the display precision to 15 places.

b) How many additions and how many multiplications does each of the three methods use? (Look at your spreadsheet and count how many additions and how many multiplications it must do when you put in a new x.)

c) For each root, evaluate the polynomial by each method and report the polynomial value. Obviously the root method should give all zeroes, but is Horner's Method more accurate than the linear combination method?

d) Let's see how sensibly each method behaves for small changes in x. For eps = 1e-14, evaluate the polynomial by the three methods at 9.9, 9.9+eps, 9.9+2*eps, 9.9+3*eps, 9.9+4*eps Do the values form a smooth curve? That is, if you plot the polynomial value against the eps multiple, do you get a nice straight line?

e) Verify that x = 2 is a root of p(x) = x^4 + 3 x^3 - 7 x^2 + x - 14, and use polynomial division to find a polynomial Q(x) such that P(x) = (x - 2)Q(x).

f) Find 39^83 mod 100 using the squaring method described above.

Here is the needed spreadsheet for reference

E B 1 Polynomial evaluation 2 3 Roots: 4 3.2 5 4.6 6 7.1 7 8 Coefficients, low power to high: Power of x 9 -104.5 al x0 10 70.1 al x 1 11 -14.9 a2 x2 12 1 a3 x 3 13 14 Product of linear factors: 15 factor plx) 16 1.1 -2.1 -44.1 17 -3.5 18 -6 19 20 21 Linear combination of powers: 22 X power X power term 23 1.1 1 -104.51 24 1.1 77.11 25 1.21 -18.029 26 1.331 1.331 27 28 Horner's Method: 29 power result 30 1.1 -44.1 31 1 54.92 32 -13.8 33 1 34 p(x) -44.1 WNO p(x) -44.1 WNO E B 1 Polynomial evaluation 2 3 Roots: 4 3.2 5 4.6 6 7.1 7 8 Coefficients, low power to high: Power of x 9 -104.5 al x0 10 70.1 al x 1 11 -14.9 a2 x2 12 1 a3 x 3 13 14 Product of linear factors: 15 factor plx) 16 1.1 -2.1 -44.1 17 -3.5 18 -6 19 20 21 Linear combination of powers: 22 X power X power term 23 1.1 1 -104.51 24 1.1 77.11 25 1.21 -18.029 26 1.331 1.331 27 28 Horner's Method: 29 power result 30 1.1 -44.1 31 1 54.92 32 -13.8 33 1 34 p(x) -44.1 WNO p(x) -44.1 WNO