where x is the independent variable and each of the ci's is a so-called coefficient. (In this assignment, all coefficients will be of type int.) Each of the summands cixi is referred to as a term. The largest power of x among those terms with a non-zero coefficient is called the degree of the polynomial. (The absence of terms cm+1xm+1, cm+2xm+2, etc., etc., can be taken to imply that each of cm+1, cm+2, etc., etc., is zero.) For the special case of the polynomial having no nonzero coefficients, we call it the "zero polynomial" and define its degree to be zero.
For example, if we choose as coefficients c0 = 5, c1 = −3, c2 = 1, c3 = 0, and c4 = 2, we get the polynomial (of degree four)
By convention, when displaying a polynomial we usually omit coefficients that are 1 and any term whose coefficient is zero. Also, we use infix minus operators rather than unary ones, except in the first term. Thus, our example p(x) would more likely be written as
As with any mathematical function, a polynomial can be evaluated at (or applied to, if you prefer) a specified value of x. For example, to evaluate p(x) at 2.5, we plug in 2.5 for x and carry out the prescribed multiplications and additions:
| p(2.5) | = | (5)(2.50) + (−3)(2.51) + (1)(2.52) + (0)(2.53) + (2)(2.54) |
| = | (5)(1) + (−3)(2.5) + (1)(6.25) + (0)(15.625) + (2)(39.0625) | |
| = | 5 + −7.5 + 6.25 + 0 + 78.125 | |
| = | 81.875 |
A clever way of evaluating a polynomial —and one that is more efficient than the more obvious approach— is based on the observation that
You are encouraged to apply this approach in the relevant method (valueAt()), but it is not a requirement.
Suppose that q(x) and r(x) are polynomials as follows:
Without loss of generality, we assume m≤n. Then the sum of q(x) and r(x) is the polynomial (q+r):
That is, each coefficient of (q+r)(x) is obtained by adding the corresponding coefficients of q(x) and r(x). Notice that because m≤n, we take each of am+1, am+2, ..., an to be zero. For example, if q(x) = −3 + 2x + 8x3 and r(x) = 7 + −11x + 4x2, then
Analogously, each coefficient of the difference of q(x) and r(x), (q−r)(x), is obtained by taking the difference (ai−bi) of the corresponding coefficients of q and r. Continuing our example,
The product of q(x) and r(x), (q·r)(x), is a bit more difficult to compute. First, the degree of (q·r)(x) is m+n, the sum of the degrees of q(x) and r(x). (An exception to this occurs when either q(x) or r(x) is the zero polynomial, as then the product is the zero polynomial (which has degree zero).) For each k in the range [0 .. m+n], the coefficient of the xk-term in (q·r)(x) is
| Σ0≤i≤k (ai·bk−i) | = | a0·bk + a1·bk-1 + a2·bk-2 + ... + ak·b0 |
Notice how the subscripts in each term of the sum add up to k.
Continuing our example, we compute the coefficient of x3 in (q·r)(x) as follows:
| a0·b3 + a1·b2 + a2·b1 + a3·b0 | |
| = | (−3)(0) + (2)(4) + (0)(−11) + (8)(7) |
| = | 0 + 8 + 0 + 56 |
| = | 64 |
Carrying out the similar calculations for the other coefficients, we find that
Let f(x) be a function. Then any value a such that f(a) = 0 is said to be a root (or zero) of f.
All polynomials are continuous functions, which, informally, means that each one's graph can be drawn without "lifting pencil off paper". For any continuous function f(x) and real numbers a and b with a < b, if f(a)·f(b) ≤ 0 (which is to say that either one of a or b is a root or else f(a) and f(b) have opposite signs), then there is a real number c with a ≤ c ≤ b such that c is a root of f(x).
It follows that, to search for a root in the interval [a,b], we can choose any d between a and b and then determine, based upon the value of f(a)·f(d), whether or not there is sure to be a root in the interval [a,d]. If so, continue the search there. If not, search in [d,b]. (If the term binary search has not already come to your mind, it should have!)
For this assignment, you are to complete the Polynomial class, each instance of which represents a polynomial with integer coefficients.
Methods that need to be completed (all of which include the word STUB) include those that carry out the operations described above. By examining the accompanying comments, you will notice that the methods that compute the sum (addTo()), difference (subtractFrom()), and product (multiplyBy()) of two polynomials are intended to be mutators, the term we use to refer to methods that have the effect of changing the state of the "target object" (i.e., the object to which the method was applied).
For example, if p and q are instances of the Polynomial class, the method call p.addTo(q) is intended to have the effect of changing the state of p so that it becomes the sum of its former self and q. (Informally, you can think of it as being analogous to the assignment statement p = (p+q).)
Take, for example, a Polynomial object that represents the polynomial
Then the value of its coeff instance variable would be (a reference to) the ArrayList
0 1 2 3 4 +---+---+---+---+---+ | 4 | -7| 0 | 1 | 5 | +---+---+---+---+---+ |
That is, for each i in the range [0..n], where n is the degree of the polynomial, coeff.get(i) holds the coefficient of xi.
In any case, the code that the student needs to supply should not refer directly to coeff; rather, all references to it should occur indirectly via calls to the coefficient() and setCoefficient() methods, both of which are provided in full.
It is recommended that, in attempting to complete the source code of the Polynomial class, students tackle the tasks confronting them in something approximating this order:
Note that, as provided, the toString() method makes use of an instance of the StringBuilder class. In effect, an instance of that class is a "mutable" sequence of characters, in contrast to instances of the String class, which are immutable. You are free to resort to using String objects if you wish.
Welcome to the Polynomial Tester Program! 1: Test Evaluate 2: Test Root Find 3: Test Arithmetic 4: Quit Enter choice: 1 Enter the coefficients for polynomial p: -2 6 1 Polynomial p = -2 + 6x + x^2 Enter value at which to evaluate p (empty string to exit): 0.0 p(0.0) = -2.0 Polynomial p = -2 + 6x + x^2 Enter value at which to evaluate p (empty string to exit): 5.25 p(5.25) = 57.0625 Polynomial p = -2 + 6x + x^2 Enter value at which to evaluate p (empty string to exit): -7.5 p(-7.5) = 9.25 Polynomial p = -2 + 6x + x^2 Enter value at which to evaluate p (empty string to exit): 1: Test Evaluate 2: Test Root Find 3: Test Arithmetic 4: Quit Enter choice: 2 Enter the coefficients for polynomial p: -30 4 2 Polynomial p = -30 + 4x + 2x^2 Enter endpoints of interval in which to search for a root (empty string to exit): -10 0 Root found at z = -5.000004768; p(z) = 0.000076294 Polynomial p = -30 + 4x + 2x^2 Enter endpoints of interval in which to search for a root (empty string to exit): 0 8 Root found at z = 2.999996185; p(z) = -0.000061035 Polynomial p = -30 + 4x + 2x^2 Enter endpoints of interval in which to search for a root (empty string to exit): 5 10 java.lang.IllegalArgumentException: Values at endpoints have same sign! at Polynomial.rootOf(Polynomial.java:117) at PolynomialTester.testRootFind(PolynomialTester.java:139) at PolynomialTester.main(PolynomialTester.java:34) Polynomial p = -30 + 4x + 2x^2 Enter endpoints of interval in which to search for a root (empty string to exit): 1: Test Evaluate 2: Test Root Find 3: Test Arithmetic 4: Quit Enter choice: 3 Enter the coefficients for polynomial p: 4 -8 3 p, of degree 2, is 4 - 8x + 3x^2 Enter the coefficients for polynomial q: -3 4 2 1 q, of degree 3, is -3 + 4x + 2x^2 + x^3 p+q is 1 - 4x + 5x^2 + x^3 p-q is 7 - 12x + x^2 - x^3 p*q is -12 + 40x - 33x^2 - 2x^4 + 3x^5 1: Test Evaluate 2: Test Root Find 3: Test Arithmetic 4: Quit Enter choice: 4 Goodbye |
Make sure to include comments at the beginning of your program that
Be aware that you can submit more than one time. Hence, if, after submitting, you improve your program (e.g., by fixing logic errors), you should submit the newer version. (Do not change the name of the class!)