Data Structures, Algorithms, & Applications in Java
Chapter 6, Exercise 66

package applications;

import exceptions.*;
import utilities.*;

public class Polynomial
{
   // instance data members
   int degree;            // polynomial degree
   int [] coeff;          // coeff[i] is coefficient of x^i

   // constructor
   /** create the zero polynomial */
   public Polynomial()
   {
      coeff = new int [1];
      coeff[0] = 0;
      // degree has its default value 0
   }

   // instance methods
   /** @return polynomial degree */
   public int degree()
      {return degree;}

   /** input the polynomial from the standard input stream */
   public void input(MyInputStream inStream)
   {
      // input new degree and get needed array space
      System.out.println("Enter the polynomial degree");
      degree = inStream.readInteger();
      if (degree < 0)
         throw new MyInputException("degree must be >= 0, it is "
                                    + degree);
      coeff = new int [degree + 1];
   
      // input the coefficients in increasing order of exponents
      System.out.println("Enter the coefficients in increasing order of"
                         + " exponent");
      for (int i = 0; i <= degree; i++)
         coeff[i] = inStream.readInteger();
   
      // make sure coeff[degree] is nonzero except when degree is 0
      if (degree != 0 && coeff[degree] == 0)
         throw new MyInputException("coefficient of highest "
                                    + "exponent term must be nonzero");
   }
   
   /** output the polynomial */
   public void output()
   {
      // output degree
      System.out.println("Degree = " + degree);
   
      // output the coefficients
      System.out.println("The coefficients, in increasing "
                         + "order of exponent are");
      for (int i = 0; i <= degree; i++)
         System.out.print(coeff[i] + "  ");
      System.out.println();
   }
   
   /** @return this + b */
   public Polynomial add(Polynomial b)
   {
      // define result polynomial w
      Polynomial w = new Polynomial();
   
      // compute result
      if (degree > b.degree)
      {// this has higher degree
         w.degree = degree;
         w.coeff = new int [w.degree + 1];

         // compute answer coefficients
         for (int i = 0; i <= b.degree; i++)
            w.coeff[i] = coeff[i] + b.coeff[i];
         for (int i = b.degree + 1; i <= degree; i++)
            w.coeff[i] = coeff[i];
      }
      else
         if (degree < b.degree)
         {// b has higher degree
            w.degree = b.degree;
            w.coeff = new int [w.degree + 1];

            // compute answer coefficients
            for (int i = 0; i <= degree; i++)
               w.coeff[i] = coeff[i] + b.coeff[i];
            for (int i = degree + 1; i <= b.degree; i++)
               w.coeff[i] = b.coeff[i];
         }
         else
         {// both polynomials have the same degree
            // find highest-exponent term that remains
            int i;
            for (i = degree; i > 0; i--)
               if (coeff[i] + b.coeff[i] != 0) break;

            // highest term with nonzero coefficient is x^i
            w.degree = i;
            w.coeff = new int [w.degree + 1];

            // compute answer coefficients
            for (i = 0; i <= w.degree; i++)
               w.coeff[i] = coeff[i] + b.coeff[i];
         }
       
      return w;
   }
   
   /** @return this - b */
   public Polynomial subtract(Polynomial b)
   {
      // define result polynomial w
      Polynomial w = new Polynomial();
   
      // compute result
      if (degree > b.degree)
      {// this has higher degree
         w.degree = degree;
         w.coeff = new int [w.degree + 1];

         // compute answer coefficients
         for (int i = 0; i <= b.degree; i++)
            w.coeff[i] = coeff[i] - b.coeff[i];
         for (int i = b.degree + 1; i <= degree; i++)
            w.coeff[i] = coeff[i];
      }
      else
         if (degree < b.degree)
         {// b has higher degree
            w.degree = b.degree;
            w.coeff = new int [w.degree + 1];

            // compute answer coefficients
            for (int i = 0; i <= degree; i++)
               w.coeff[i] = coeff[i] - b.coeff[i];
            for (int i = degree + 1; i <= b.degree; i++)
               w.coeff[i] = -b.coeff[i];
         }
         else
         {// both polynomials have the same degree
            // find highest-exponent term that remains
            int i;
            for (i = degree; i > 0; i--)
               if (coeff[i] - b.coeff[i] != 0) break;

            // highest term with nonzero coefficient is x^i
            w.degree = i;
            w.coeff = new int [w.degree + 1];

            // compute answer coefficients
            for (i = 0; i <= w.degree; i++)
               w.coeff[i] = coeff[i] - b.coeff[i];
         }
       
      return w;
   }
   
   /** @return w = this * b */
   public Polynomial multiply(Polynomial b)
   {
      Polynomial w = new Polynomial();  // result polynomial
   
      // see if either this or b is zero
      if ((degree == 0 && coeff[0] == 0) ||
          (b.degree == 0 && b.coeff[0] == 0))
         // answer is zero polynomial
         return w;
   
      // neither is zero, so answer is nonzero
      // determine degree of answer and get array of correct size
      w.degree = degree + b.degree;
      w.coeff = new int [w.degree + 1];
      
      // multiply the two polynomials
      // first multiply this and b.coeff[0]
      for (int i = 0; i <= degree; i++)
         w.coeff[i] = coeff[i] * b.coeff[0];
   
      // now multiply remaining terms of b
      for (int j = 1; j <= b.degree; j++)
      {// multiply this and b.coeff[j] and add to w
         for (int i = 0; i < degree; i++)
            w.coeff[i + j] += coeff[i] * b.coeff[j];

         // do the last term
         w.coeff[degree + j] = coeff[degree] * b.coeff[j];
      }
   
      return w;
   }

   /** @return a clone */
   public Object clone()
   {
      // define the clone
      Polynomial w = new Polynomial();

      // set the degree and coefficients
      w.degree = degree;
      w.coeff = new int [degree + 1];
      for (int i = 0; i <= degree; i++)
         w.coeff[i] = coeff[i];

       return w;
   }
   
   /** @return w = this / b, discard remainder */
   public Polynomial divide(Polynomial b)
   {
      if (b.degree == 0 && b.coeff[0] == 0)
         // division by zero
         throw new IllegalArgumentException
                   ("divisor cannot be zero");
   
      Polynomial w = new Polynomial();  // result polynomial
   
      // see if answer is zero
      if (degree < b.degree)
         // answer is zero
         return w;
   
      // answer is nonzero
      // determine degree of answer and get array of correct size
      w.degree = degree - b.degree;
      w.coeff = new int [w.degree + 1];
   
      // r is current remainder
      Polynomial r = (Polynomial) clone();

      // divide the two polynomials
      int nextw = w.degree;  // w.coeff[nextw] is next
                             // w coefficient to be computed
      do {
         // compute next nonzero term in w
         // e is exponent of next term in quotient
         int e = r.degree - b.degree;
   
         if (e < nextw) 
            // set coeff[e+1:nextw] to 0
            for (int i = e + 1; i <= nextw; i++)
               w.coeff[i] = 0;
      
         // compute next coefficient
         w.coeff[e] = r.coeff[r.degree] / b.coeff[b.degree];
         if (r.coeff[r.degree] != b.coeff[b.degree] * w.coeff[e])
         {// remaining coefficients are zero, remainder has same
          // degree as r
            for (int i = 0; i < e; i++)
               w.coeff[i] = 0;
            return w;
         }

         // remainder has smaller degree than r, compute remainder polynomial
         // r = r - p * w.coeff[e] * x^e
         // q  = p * w.coeff[e] * x^e will have degree r.degree
         Polynomial q = new Polynomial();
         q.coeff = new int [r.degree + 1];
         q.degree = r.degree;
         for (int i = 0; i < e; i++)
            q.coeff[i] = 0;
         for (int i = e; i <= r.degree; i++)
            q.coeff[i] = b.coeff[i - e] * w.coeff[e];
   
         // compute new remainder
         r = r.subtract(q);
         nextw = e - 1;
      } while (nextw >= 0 && r.degree >= b.degree);
   
      // do left over coefficients
      for (int i = 0; i <= nextw; i++)
         w.coeff[i] = 0;
   
      return w;
   }
   
   /** @return the value of the polynomial at x */
   public int valueOf(int x)
   {// use Horner's rule to compute the polynomial value
      int value = coeff[degree];
      for (int i = 1; i <= degree; i++)
         value = value * x + coeff[degree - i];
      return value;
   }
}