Check back frequently for potential updates!

Some applications involve polynomials which can be modeled as "objects" in an Object-Oriented Programming program. Hence, we need a class named Polynomial that can be used to create and operate on polynomials. In this project, you will write a class that implements polynomials and polynomial arithmetic. I have provided a zip file (see link above) with a JUnit TestCase class that you can use to test your Polynomial class. Unzip the directory and setup a Dr Java project. In your Dr Java project, create/save a new source file named Polynomial.java and write your code in it, compile it, and test it. Keep testing it until the code for your Polynomial class passes all the test cases in TestPolynomial (shows all green). The UML class diagram describing the API for the Polynomial class is provided here.

Polynomial implements Comparable<Polynomial> 
- coefficients : List<Integer> // polynomial coefficients  
+ Polynomial(int... coefficients)       // constructor with variable length coefficients

+ toString( ) : String                  // return a String representing the polynomial

+ compareTo(that : Polynomial) : int    // returns -, 0, +

+ equals(that : Polynomial) : boolean   // returns true or false


// Polynomial arithmetic methods:

+ plus(that : Polynomial) : Polynomial     // add

+ minus(that : Polynomial) : Polynomial    // subtract

+ multiply(that : Polynomial) : Polynomial

+ divide(divisor : Polynomial) : Polynomial [] {[0] = quotient, [1] = remainder}

+ evaluate(x : double) : double         // return the value of polynomial evaluated for x

+ derivative() : Polynomial             // return the derivative of the Polynomial

+ root(guess : double, TOLERANCE : double, iterations : int) : double // get root

The Polynomial class encapsulates one private List<Integer> of coefficients. The value for each array element is the coefficient of that exponent in the polynomial. For example: An array with coefficients[0] = 1, coefficients [1] = -2, and coefficients[2] = 2 represents the polynomial 2*x2 - 2*x1 + 1*x0 (or more compactly 2x2 - 2x + 1).

The Polynomial class implements the interface Comparable<Polynomial>. An object of your Polynomial class can be compared to other Polynomial class objects so we will write the code in the class header as implements Comparable<Polynomial>

If you need JUnit, you can download it with this link: junit-4.12.jar

Code outside of your Polynomial class can do the following:

  1. Create a Polynomial object by calling the Polynomial constructor with a list of int variables for the coefficients starting with the coefficient of x0 and ending with the coefficient for the largest power of x present. Here is an example:
    // create a polynomial corresponding to above example
Polynomial p = new Polynomial(1, -2, 2); // representing 2*x2 - 2*x1 + 1*x0
    Notice that after code outside of the Polynomial class creates a Polynomial object with terms for all exponents, it does not ever need to access the coefficients again. Hence, there are no mutator ("setter") or accessor ("getter") methods. All operations on the coefficients of Polynomial objects are done in the code of the Polynomial class itself, for example...
  2. Display Polynomial objects using the toString method; for example:
        // print a polynomial (the toString method for p is automatically called)
    System.out.println(p);
    The String representing a polynomial is a concatenation of the coefficients in the array and their corresponding powers of x. See the provided TestPolynomial class to understand the exact format your code needs to produce. Although the ^ symbol is not used as an exponentiation operator in Java, we use it to indicate superscripting in the string representation of our polynomials.
  3. Compare two polynomials via the compareTo method. This is the method required to implement the interface Comparable. Look up the interface Comparable on the Sun web site and study the meaning of implementing this interface. You should also include an equals method for comparisons.
    // compare two polynomials p and q

int n = p.compareTo(q); // n = -, 0, or + value based on comparision
boolean b = p.equals(q); // b = true or false based on comparison
    The compareTo method implements the "natural ordering" of polynomials as follows: Once you have written a compareTo method, you can use it to write a simple equals method. Return true or false based on the return value from a call to the compareTo method being equal to 0 or not.
  4. Do arithmetic on Polynomials using the arithmetic methods of the Polynomial class, for example:
         Polynomial sum = p.plus(q);          // return sum of p + q
     Polynomial diff = p.minus(q);        // return result of p - q
     Polynomial product = p.multiply(q);  // return product of p * q
     Polynomial [] qr = p.divide(q);      // return quotient and remainder of p / q
    Note that these methods are normal methods and are called the same way as normal methods. They are not "magic methods" like in Python and do not overload the operators: +, -, *, and /. Operator overloading is not supported in Java.
  5. Evaluate the polynomial at a specific value of x
      // evaluate polynomial with x = 3 and print the value
  System.out.println(p.evaluate(3));
  6. Obtain a Polynomial that represents the derivative (slope function) of the existing Polynomial
      // obtain the derivative and print the function
  System.out.println(p.derivative());
  7. Obtain an estimate of a root of the Polynomial using Newton's method - providing an initial guess, a required tolerance, and a maximum number of iterations to use.
      // obtain a root of the Polynomial using Newton’s method
  System.out.println(p.root(1.5, 0.0001, 10));   // guess, tolerance, iterations

Notes on the implementation:

The Constructor

For the constructor, we are using the variable length argument list capability of the Java language. We declare the method header for the overloaded constructor as follows:

  public Polynomial(int... coefficients);   // a list of ints will be placed in an array.
Our code can call this constructor either of two ways: with an arbitrarily long list of int variables or one variable of type int [ ] . You will need to choose an implementation of the List<Integer> interface: ArrayList<Integer> , LinkedList<Integer> , etc.

Normally, we would think that the highest power of x in the polynomial would be the length of the array minus one. However, the user may provide a list of variables with zero values for the larger indexed coefficients in the array. Hence the length of the array does not directly indicate the degree of the polynomial. After copying the coefficients array into the List attribute, loop through the List and remove any high order zero coefficients. Now the List size() method indicates the order of the polynomial.

Arithmetic Methods

The methods implementing the polynomial arithmetic should operate on the coefficients of "this" polynomial with the coefficients of "that" polynomial. The word "that" is not a Java reserved word. We can use it for a variable name in the parameter list. For example, use as the method header for plus:

    public Polynomial plus(Polynomial that)
Calculate the new coefficients for the result of each arithmetic method and return them in a new Polynomial object, as follows:

Derivative method

In calculus, the derivative of a term in a polynomial can be calculated easily. The derivative of the term Cnxn is:
n*Cnx(n – 1)
The derivative of the entire polynomial is the sum of the derivatives of every term. Use the arithmetic methods of the Polynomial class, as needed.

Root Method

The root method needs to implement a loop refining the initial guess at each iteration i using Newton’s method and the Polynomial arithmetic, derivative, and evaluate methods.

    guess(i + 1) = guess(i) – polynomial value at guess(i) / derivative value at guess(i)
The loop should terminate when the value of the polynomial at guess(i) is within the TOLERANCE of zero, the derivative at guess(i) is zero (failure of Newton’s method), or the number of iterations is exceeded (to prevent infinite loops).

General Guidelines

Include Javadoc comments in your Polynomial class code with @author and @version for the class and with @param and @return for each method. In the Javadoc comments for each method, include a brief description of the calculation that your code performs. Run javadoc on your Polynomial class file to create a webpage describing the API to your Polynomial class. Keep improving the Javadoc comments in your code until it produces a readable and useful webpage. The webpage files should be in a folder called doc . Include a copy of that javadoc generated directory (with the contained files) in your project folder.

Now, edit the application class PolynomialApp. Use your javadoc webpage and the Sun webpage for the java.util.Arrays class as guidance while you are writing the code for this class. You should find it easy to create and do operations on polynomials without knowing much about the mathematics of them. In the Arrays class webpage, locate the sort(Object [] a) method described there. Note that it requires an array of Objects that have a natural ordering based on the Comparable compareTo method.

The main method of the PolynomialApp class should (1) instantiate an array of more than 5 Polynomial objects and (2) instantiate a different Polynomial object in each element of the array. Be sure that you put them in the array out of their natural ordering so that you can see the results of sorting the array. Have your code print out the Polynomial objects in your array before sorting them, call Arrays.sort to sort the array of Polynomials, and print out the contents of the array again to show that they are now sorted in their natural order based on the rules given above for the Polynomial class compareTo method. Finally, for each Polynomial object in the array, print its derivative.