General Polynomial Evaluation

COMP 110 Project 4: General Polynomial Evaluation This is a continuation of Project 3 (polynomial evaluation). In this project, you will introduce modifications to make your solution more general, and will explore a well-known algorithm for making the evaluation more efficient. Part I: GenPoly.java In this lab you will modify your solution from Project 3 to allow the degree of the polynomial to be fully general (degree can be any integer > 0). The general solution requires the following modifications: • Instead of individual variables to hold a fixed number of coefficients, you will create an array of coefficients. • The size of the array is determined by the degree of the polynomial to be evaluated. The degree is another variable to be maintained by your program, and user will provide its value as a program input. • The portion of the algorithm where coefficients are input and the portion where the polynomial is evaluated will both require a counter-controlled loop. These are loops in addition to the loops that are already present. Background: Arrays, Indexes, Subscripts Sequences and series arise as data in both mathematics and computer science. The values in a sequence may be random values, or they may follow a pattern or formula. For example, consider the sequence of the squares of the integers: or 12, 22, 32, 42, 52, … 1, 4, 9, 16, 25, … We can also define a sequence symbolically for convenience using subscripted variables S = s1, s2, s3, s4, s5, … where the general term is given by si = i2 Any sequence can be subscripted for convenience. The subscript is just a way of referring to a specific value in the sequence. To store a sequence of values in Java, we use an array. An array is a variable that has storage cells for multiple values up to some finite limit. Here’s an example of a Java statement to create an array of 10 integers. int[] x = new int[10]; Once the array has been created, the values can be placed into the individual locations (or “slots” or “elements”), which in this case are indexed from 0 to 9. x[0] = 0; // store 0 into x element 0, same as x0 = 0; x[1] = 1; // store 1 into x element 1, same as x1 = 1; x[2] = 4; // store 4 into x element 2, same as x2 = 4; … x[9] = 81; // store 81 into x element 9, same as x9 = 81; The size of the array can also be indicated by a variable: int n = …; int[] x = new int[n]; Inside a loop, the variable used to control the loop can also be used as the array subscript: int i = 0; int[] x = new int[100]; while (i<100) { … x[i] = …; i++; } For your polynomial evaluator, you will need to make the following changes: • Replace the declaration of individual coefficients with the declaration of an array for all the coefficients. This array must be of type double. • Declare a new input variable “int n” to hold the degree of the polynomial. Note that the index expression for an array is always an int, regardless of what kind of data is stored in the array (int, double, char, etc.) • Replace code to input individual coefficients with a loop to input coefficients once per loop execution • Replace formula to evaluate polynomial with a loop that evaluates the polynomial one term at a time and accumulates the final result. Example Run Use the same test runs that you used for the last part of project 3. However, the new runs require an additional input for the polynomial degree. Also, your program will only prompt for coefficients that are required for that polynomial. If the user enters, for example “3” for the poly degree, the program will only prompt for coefficients for x3 through x0. You will not enter a bunch of 0s for large unused terms in the polynomial. Finally, use the same loops from Project 3 that allow the user to enter multiple x values and multiple polynomials as before. > java GenPoly Polynomial Evaluator Release 4.1 Enter degree of polynomial: 3 (note: new input) Enter coefficient 3: 1 (note: don’t start with 5th coeff.) Enter coefficient 2: -1 Enter coefficient 1: 1 Enter coefficient 0: 0 Enter x: 20 Value is 7620 … Part II: Horner.java The obvious algorithm for evaluating polynomials is correct, but it is not efficient for large degree polynomials. That is, it is wasteful of computer operations and performs more computations than are really needed. To understand the amount of computation used, let’s assume that powers of x are computed by direct multiplication, rather than the Math.pow() operation. For example, consider the computation 3x3 – 4x2 + 15x – 29 Imagine this expression expanded out as follows: 3 * x * x * x – 4 * x * x + 15 * x – 29 This expression is correct, but notice how the various powers of x are computed. They are each calculated from scratch, when in fact, a higher power of x could be more efficiently calculated by using a lower power of x as a starting point. In other words, if we know x2, we can use it to calculate x3, and if we know x3, we can use it to calculate x4, and so on. If we rearrange the calculation and save some important temporary values, we can get the same answer with less work. Consider the “obvious” way to calculate x2 and x3: double b = x * x; double a = x * x * x; which uses 3 multiplications. In contrast: double b = x * x; double a = b * x; uses only 2 multiplications. This may not seem like a big difference, but imagine a polynomial of high degree, and the savings could be substantial. Exercise #1 Look at the following expression for a general polynomial with degree = n. cnxn + cn-1xn-1 + cn-2xn-2 + … + c2x2 + c1x + c0 Determine how many multiplications and how many additions are required by the “obvious” polynomial evaluation algorithm to evaluate the expression. Assume repeated multiplication, not the Math.pow() function which evaluates powers directly. Your answer should be left in terms of n. Use the series result n ∑i = i =1 n * ( n + 1) 2 Exercise #2 There is in fact a well-known algorithm for efficient evaluation of polynomials called Horner’s Rule. For Part II, research this algorithm and rewrite your program to implement it. Name your class HornerPoly and save to file HornerPoly.java. Don’t confuse with Horner’s Method (for finding roots). Hints will be provided in lab, but you are expected to create an initial design on your own. Use Horner’s Rule to reevaluate the expression above then determine how many multiplications and additions are now required. Hint: HornerPoly.java is identical to GenPoly.java except for the loop that performs the polynomial eval. 2 Example Compare the evaluation of for both algorithms. GenPoly algorithm 3 * x * x * x 3 * 2 * 2 * 2 3 * 8 24 9 f(x) = 3x3 – 4x2 + 15x – 29 – – – – 4 * x * x 4 * 2 * 2 4 * 4 16 + + + + 15 * x 15 * 2 15 * 2 30 – – – – for x = 2 29 29 29 29 Total multiplications = 6 HornerPoly algorithm 3 3 * 2 = 6 6 – 4 = 2 2 * 2 = 4 4 + 15 = 19 19 * 2 = 38 38 – 29 = 9 initialize value to 3 multiply by 2 add -4 multiply by 2 add 15 multiply by 2 add -29 Total multiplications = 3 Horner’s rule evaluates the polynomial in the following steps. Initialize a variable to the value of the largest coefficient (3 in the example). Next, multiply by the value of x (2 in the example) Next, add the next coefficient (–4 in the example) Next, multiply by x (2) Next, add the next coefficient (15) Next, multiply by x (2) Next, add the next coefficient (0 – 29) When the last coefficient has been added, the polynomial has been evaluated (final value of 9). This algorithm can be implemented as a loop: Let n be the degree of the polynomial. Let c[i] be the coefficient for the xi. Let x be the value of x. Let value be the value of the polynomial Initialize value to c[n]. For all coefficients i n-1 down to 0 value = value * 2 value = value + c[i] 3