# RationalPolynomial.java

Below is the syntax highlighted version of RationalPolynomial.java from §9.2 Floating Point.

```/******************************************************************************
*  Compilation:  javac RationalPolynomial.java
*  Execution:    java RationalPolynomial
*
*  A polynomial with arbitrary precision rational coefficients.
*
******************************************************************************/

public class RationalPolynomial {
public final static RationalPolynomial ZERO = new RationalPolynomial(BigRational.ZERO, 0);

private BigRational[] coef;   // coefficients
private int deg;              // degree of polynomial (0 for the zero polynomial)

// a * x^b
public RationalPolynomial(BigRational a, int b) {
coef = new BigRational[b+1];
for (int i = 0; i < b; i++)
coef[i] = BigRational.ZERO;
coef[b] = a;
deg = degree();
}

// return the degree of this polynomial (0 for the zero polynomial)
public int degree() {
int d = 0;
for (int i = 0; i < coef.length; i++)
if (coef[i].compareTo(BigRational.ZERO) != 0) d = i;
return d;
}

// return c = a + b
public RationalPolynomial plus(RationalPolynomial b) {
RationalPolynomial a = this;
RationalPolynomial c = new RationalPolynomial(BigRational.ZERO, Math.max(a.deg, b.deg));
for (int i = 0; i <= a.deg; i++) c.coef[i] = c.coef[i].plus(a.coef[i]);
for (int i = 0; i <= b.deg; i++) c.coef[i] = c.coef[i].plus(b.coef[i]);
c.deg = c.degree();
return c;
}

// return c = a - b
public RationalPolynomial minus(RationalPolynomial b) {
RationalPolynomial a = this;
RationalPolynomial c = new RationalPolynomial(BigRational.ZERO, Math.max(a.deg, b.deg));
for (int i = 0; i <= a.deg; i++) c.coef[i] = c.coef[i].plus(a.coef[i]);
for (int i = 0; i <= b.deg; i++) c.coef[i] = c.coef[i].minus(b.coef[i]);
c.deg = c.degree();
return c;
}

// return (a * b)
public RationalPolynomial times(RationalPolynomial b) {
RationalPolynomial a = this;
RationalPolynomial c = new RationalPolynomial(BigRational.ZERO, a.deg + b.deg);
for (int i = 0; i <= a.deg; i++)
for (int j = 0; j <= b.deg; j++)
c.coef[i+j] = c.coef[i+j].plus(a.coef[i].times(b.coef[j]));
c.deg = c.degree();
return c;
}

// return (a / b)
public RationalPolynomial divides(RationalPolynomial b) {
RationalPolynomial a = this;
if ((b.deg == 0) && (b.coef.compareTo(BigRational.ZERO) == 0))
throw new ArithmeticException("call divides() with denominator that is the zero polynomial");

if (a.deg < b.deg) return ZERO;

BigRational coefficient = a.coef[a.deg].divides(b.coef[b.deg]);
int exponent = a.deg - b.deg;
RationalPolynomial c = new RationalPolynomial(coefficient, exponent);
return c.plus( (a.minus(b.times(c)).divides(b)) );
}

// truncate to degree d
public RationalPolynomial truncate(int d) {
RationalPolynomial p = new RationalPolynomial(BigRational.ZERO, d);
for (int i = 0; i <= d; i++)
p.coef[i] = coef[i];
p.deg = p.degree();
return p;
}

// use Horner's method to compute and return the polynomial evaluated at x
public BigRational evaluate(BigRational x) {
BigRational p = BigRational.ZERO;
for (int i = deg; i >= 0; i--)
p = coef[i].plus(x.times(p));
return p;
}

// differentiate this polynomial and return it
public RationalPolynomial differentiate() {
if (deg == 0) return ZERO;
RationalPolynomial deriv = new RationalPolynomial(BigRational.ZERO, deg-1);
for (int i = 0; i < deg; i++)
deriv.coef[i] = coef[i+1].times(new BigRational(i + 1));
deriv.deg = deriv.degree();
return deriv;
}

// return antiderivative
public RationalPolynomial integrate() {
RationalPolynomial integral = new RationalPolynomial(BigRational.ZERO, deg + 1);
for (int i = 0; i <= deg; i++)
integral.coef[i+1] = coef[i].divides(new BigRational(i + 1));
integral.deg = integral.degree();
return integral;
}

// return integral from a to b
public BigRational integrate(BigRational a, BigRational b) {
RationalPolynomial integral = integrate();
return integral.evaluate(b).minus(integral.evaluate(a));
}

// convert to string representation
public String toString() {
if (deg ==  0) return "" + coef;
if (deg ==  1) return coef + " x + " + coef;
String s = coef[deg] + " x^" + deg;
for (int i = deg-1; i >= 0; i--) {
int cmp = coef[i].compareTo(BigRational.ZERO);
if      (cmp == 0) continue;
else if (cmp  > 0) s = s + " + " + ( coef[i]);
else if (cmp  < 0) s = s + " - " + (coef[i].negate());
if      (i == 1) s = s + " x";
else if (i >  1) s = s + " x^" + i;
}
return s;
}

// test client
public static void main(String[] args) {
BigRational half  = new BigRational(1, 2);
BigRational three = new BigRational(3, 1);

RationalPolynomial p = new RationalPolynomial(half,  1);
RationalPolynomial q = new RationalPolynomial(three, 2);
RationalPolynomial r = p.plus(q);
RationalPolynomial s = p.times(q);
RationalPolynomial t = r.times(r);
RationalPolynomial u = t.minus(q.times(q));
RationalPolynomial v = t.divides(q);
RationalPolynomial w = v.times(q);

StdOut.println("p(x)                      = " + p);
StdOut.println("q(x)                      = " + q);
StdOut.println("r(x) = p(x) + q(x)        = " + r);
StdOut.println("s(x) = p(x) * q(x)        = " + s);
StdOut.println("t(x) = r(x) * r(x)        = " + t);
StdOut.println("u(x) = t(x) - q^2(x)      = " + u);
StdOut.println("v(x) = t(x) / q(x)        = " + v);
StdOut.println("w(x) = v(x) * q(x)        = " + w);
StdOut.println("t(3)                   = " + t.evaluate(three));
StdOut.println("t'(x)                  = " + t.differentiate());
StdOut.println("t''(x)                 = " + t.differentiate().differentiate());
StdOut.println("f(x) = int of t(x)     = " + t.integrate());
StdOut.println("integral(t(x), 1/2..3) = " + t.integrate(half, three));
}

}
```

Copyright © 2000–2017, Robert Sedgewick and Kevin Wayne.
Last updated: Fri Oct 20 14:12:12 EDT 2017.