Write a program which takes in the coefficients of a polynomial and a value of x, and computes the value of the polynomial at x by Horner's method.
Write and analyze (i.e. tell me its run-time in big-O notation) a function (or method or whatever) which takes in two polynomials, as above, and computes their sum, another polynomial.
Same thing, computing the product. If your polynomial data type is limited to degree 7, you may assume that each of the inputs is at most degree 3.
Extra credit: Same thing, computing the quotient and the remainder. You may assume that the polynomial you're dividing by has at least one nonzero coefficient.
Consider the system of linear equations
0.5x + 22.0y = 3.0 1000.0x - 5.0y = 4.0Typically, floating-point numbers are represented with a fixed relative accuracy, such as 2^{-23}. For the purposes of this exercise, we'll assume that all six numbers in the example are represented to a relative accuracy of 1 in 1000, i.e. ± 0.1%, so the system is really
(0.5 ± 0.1%)x + (22 ± 0.1%)y = 3.0 ± 0.1% (1000.0 ± 0.1%)x + (-5 ± 0.1%)y = 4.0 ± 0.1%or equivalently, written using absolute accuracy,
(0.5 ± 0.0005)x + (22 ± 0.022)y = 3.0 ± 0.003 (1000.0 ± 1.0)x + (-5 ± 0.005)y = 4.0 ± 0.004
Solve the above system, computing at each stage the bounds on the possible error in the results. (You may want to write a small program to help with this -- it took me 20-30 lines of Scheme -- or you can do it by hand.) For example, if the first thing you did were to compute the ratio of the entries in the first column, it would be
(1000 ± 0.1%) / (0.5 ± 0.1%) = 2000 ± 0.2% = 2000 ± 4Multiplying this by the first row would give you
(1000 ± 0.3%)x + (44000 ± 0.3%) = 6000 ± 0.3%or equivalently
(1000 ± 3)x + (44000 ± 132) = 6000 ± 18So far everything has been multiplication, so we've been adding relative errors. The next step is to subtract the above equation from the second row, so we'll add absolute errors instead:
(0 ± 4)x + (-43995 ± 132.005)y = -5994 ± 18.004Finish solving for x and y in this manner. What are the absolute and relative accuracies of the resulting x and y?
Then do the same again with pivoting, i.e. before you decide what to multiply by one row to subtract from another, shuffle rows so that the number with the largest absolute value is on the diagonal. You should get the same answers, but with different degrees of accuracy.
The "list of coefficients" representation given above is not the only reasonable way to represent a degree-n polynomial. Another way is a list of n+1 points on the curve, e.g. the polynomial
x^{2} - 3x + 7could also be represented by the three points (1,6), (2,9), (3,16), or by the three points (-3,34), (0,7), (2,9), or many other sequences of points.
Write and analyze an algorithm (in pseudocode, or a real language if you prefer) which takes in two polynomials in this form and computes their sum, another polynomial in this form. You may assume that the x-coordinates are the same for both polynomials.
Same thing, computing the product.
Note: The product of two degree-n polynomials is a
degree-2n polynomial, which means you'll need not n+1 but rather 2n+1
points to determine it uniquely. I recommend assuming that each of the
input polynomials is represented with at least 2n+1 points; this will
make the algorithm much easier.
Write and analyze an algorithm (in pseudocode, or a real language if you prefer) which takes in a polynomial in coefficients form and converts it to a polynomial in points form (say, with x-coordinates 0, 1, 2, ....)
Write and analyze an algorithm (in pseudocode, or a real language if you prefer) which takes in a polynomial in points form and converts it to a polynomial in coefficients form.