package org.spaceroots.mantissa.algebra;
import java.io.Serializable;
import java.math.BigInteger;
import java.util.Arrays;
/** This class implements polynomials with one unknown.
* This is an abstract class that only declares general methods but
* does not hold the coefficients by themselves. Specific subclasses
* are used to handle exact rational coefficients or approximate real
* coefficients. This design is taken from the various java.awt.geom
* classes (Point2D, Rectangle2D ...)
* The methods implemented deal mainly with the polynomials algebra
* (addition, multiplication ...) but the analysis aspects are also
* considered (value of the polynom for a given unknown,
* derivative).
* Instances of this class are immutable.
* @version $Id: Polynomial.java 1716 2006-12-13 22:56:35Z luc $
* @author L. Maisonobe
*/
public abstract class Polynomial
implements Serializable {
/** Check if the instance is the null polynomial.
* @return true if the polynomial is null
*/
public abstract boolean isZero();
/** Check if the instance is the constant unit polynomial.
* @return true if the polynomial is the constant unit polynomial
*/
public abstract boolean isOne();
/** Check if the instance is the identity polynomial.
* @return true if the polynomial is the identity polynomial
*/
public abstract boolean isIdentity();
/** Get the polynomial degree.
* @return degree
*/
public abstract int getDegree();
/** Negate the instance.
* @return a new polynomial
*/
public abstract Polynomial negate();
/** Multiply the instance by a constant.
* @param r constant to multiply by
* @return a new polynomial
*/
public abstract Polynomial multiply(RationalNumber r);
/** Multiply the instance by a constant.
* @param l constant to multiply by
* @return a new Polynomial
*/
public abstract Polynomial multiply(long l);
/** Multiply the instance by a constant.
* @param i constant to multiply by
* @return a new Polynomial
*/
public Polynomial multiply(BigInteger i) {
return multiply(new RationalNumber(i));
}
/** Divide the instance by a constant.
* @param l constant to multiply by
* @return a new polynomial
* @exception ArithmeticException if the constant is zero
*/
public Polynomial divide(long l) {
return divide(new RationalNumber(l));
}
/** Divide the instance by a constant.
* @param r constant to multiply by
* @return a new polynomial
* @exception ArithmeticException if the constant is zero
*/
public Polynomial divide(RationalNumber r) {
return multiply(r.invert());
}
/** Divide the instance by a constant.
* @param i constant to multiply by
* @return a new polynomial
* @exception ArithmeticException if the constant is zero
*/
public Polynomial divide(BigInteger i) {
return divide(new RationalNumber(i));
}
/** Get the value of the polynomial for a specified unknown.
* @param x value of the unknown
* @return value of the polynomial
*/
public abstract double valueAt(double x);
/** Get the derivative of the instance with respect to the unknown.
* The derivative of a n degree polynomial is a n-1 degree polynomial of
* the same type.
* @return a new polynomial which is the derivative of the instance
*/
public abstract Polynomial getDerivative();
/** This class implements polynomials with one unknown and rational
* coefficients.
* In addition to classical algebra operations, euclidian
* division and remainder are handled.
*/
public static class Rational extends Polynomial {
/** Simple constructor.
* Build a null polynomial
*/
public Rational() {
a = new RationalNumber[] { RationalNumber.ZERO };
}
/** Simple constructor.
* Build a constant polynomial
* @param value constant value of the polynomial
*/
public Rational(long value) {
this(new RationalNumber(value));
}
/** Simple constructor.
* Build a constant polynomial
* @param value constant value of the polynomial
*/
public Rational(RationalNumber value) {
a = new RationalNumber[] { value };
}
/** Simple constructor.
* Build a first degree polynomial
* @param a1 leeding degree coefficient
* @param a0 constant term
*/
public Rational(long a1, long a0) {
this(new RationalNumber(a1), new RationalNumber(a0));
}
/** Simple constructor.
* Build a first degree polynomial
* @param a1 leeding degree coefficient
* @param a0 constant term
*/
public Rational(RationalNumber a1, RationalNumber a0) {
if (! a1.isZero()) {
a = new RationalNumber[] { a0, a1 };
} else {
a = new RationalNumber[] { a0 };
}
}
/** Simple constructor.
* Build a second degree polynomial
* @param a2 leeding degree coefficient
* @param a1 first degree coefficient
* @param a0 constant term
*/
public Rational(long a2, long a1, long a0) {
this(new RationalNumber(a2),
new RationalNumber(a1),
new RationalNumber(a0));
}
/** Simple constructor.
* Build a second degree polynomial
* @param a2 leeding degree coefficient
* @param a1 first degree coefficient
* @param a0 constant term
*/
public Rational(RationalNumber a2, RationalNumber a1, RationalNumber a0) {
if (! a2.isZero()) {
a = new RationalNumber[] { a0, a1, a2 };
} else {
if (! a1.isZero()) {
a = new RationalNumber[] { a0, a1 };
} else {
a = new RationalNumber[] { a0 };
}
}
}
/** Simple constructor.
* Build a third degree polynomial
* @param a3 leeding degree coefficient
* @param a2 second degree coefficient
* @param a1 first degree coefficient
* @param a0 constant term
*/
public Rational(long a3, long a2, long a1, long a0) {
this(new RationalNumber(a3),
new RationalNumber(a2),
new RationalNumber(a1),
new RationalNumber(a0));
}
/** Simple constructor.
* Build a third degree polynomial
* @param a3 leeding degree coefficient
* @param a2 second degree coefficient
* @param a1 first degree coefficient
* @param a0 constant term
*/
public Rational(RationalNumber a3, RationalNumber a2,
RationalNumber a1, RationalNumber a0) {
if (! a3.isZero()) {
a = new RationalNumber[] { a0, a1, a2, a3 };
} else {
if (! a2.isZero()) {
a = new RationalNumber[] { a0, a1, a2 };
} else {
if (! a1.isZero()) {
a = new RationalNumber[] { a0, a1 };
} else {
a = new RationalNumber[] { a0 };
}
}
}
}
/** Simple constructor.
* Build a polynomial from its coefficients
* @param a coefficients array, the a[0] array element is the
* constant term while the a[a.length-1] element is the leeding
* degree coefficient. The array is copied in a new array, so it
* can be changed once the constructor as returned.
*/
public Rational(RationalNumber[] a) {
// remove null high degree coefficients
int i = a.length - 1;
while ((i > 0) && (a[i].isZero())) {
--i;
}
// copy the remaining coefficients
this.a = new RationalNumber[i + 1];
System.arraycopy(a, 0, this.a, 0, i + 1);
}
/** Simple constructor.
* Build a one term polynomial from one coefficient and the corresponding degree
* @param c coefficient
* @param degree degree associated with the coefficient
*/
public Rational(RationalNumber c, int degree) {
if (c.isZero() || degree < 0) {
a = new RationalNumber[] { RationalNumber.ZERO };
} else {
a = new RationalNumber[degree + 1];
Arrays.fill(a, 0, degree, RationalNumber.ZERO);
a[degree] = c;
}
}
/** Check if the instance is the null polynomial.
* @return true if the polynomial is null
*/
public boolean isZero() {
return (a.length == 1) && a[0].isZero();
}
/** Check if the instance is the constant unit polynomial.
* @return true if the polynomial is the constant unit polynomial
*/
public boolean isOne() {
return (a.length == 1) && a[0].isOne();
}
/** Check if the instance is the identity polynomial.
* @return true if the polynomial is the identity polynomial
*/
public boolean isIdentity() {
return (a.length == 2) && a[0].isZero() && a[1].isOne();
}
/** Get the polynomial degree.
* @return degree
*/
public int getDegree() {
return a.length - 1;
}
/** Get the coefficients of the polynomial.
* @return a copy of the coefficients array, the array
* element at index 0 is the constant term while the element at
* index a.length-1 is the leading degree coefficient
*/
public RationalNumber[] getCoefficients() {
return (RationalNumber[]) a.clone();
}
/** Add a polynomial to the instance
* @param p polynomial to add
* @return a new polynomial which is the sum of the instance and p
*/
public Rational add(Rational p) {
// identify the lowest degree polynomial
int lowLength = Math.min(a.length, p.a.length);
int highLength = Math.max(a.length, p.a.length);
// build the coefficients array
RationalNumber[] newA = new RationalNumber[highLength];
for (int i = 0; i < lowLength; ++i) {
newA[i] = a[i].add(p.a[i]);
}
System.arraycopy((a.length < p.a.length) ? p.a : a,
lowLength, newA, lowLength, highLength - lowLength);
return new Rational(newA);
}
/** Subtract a polynomial from the instance.
* @param p polynomial to subtract
* @return a new polynomial which is the difference the instance minus p
*/
public Rational subtract(Rational p) {
// identify the lowest degree polynomial
int lowLength = Math.min(a.length, p.a.length);
int highLength = Math.max(a.length, p.a.length);
// build the coefficients array
RationalNumber[] newA = new RationalNumber[highLength];
for (int i = 0; i < lowLength; ++i) {
newA[i] = a[i].subtract(p.a[i]);
}
if (a.length < p.a.length) {
for (int i = lowLength; i < highLength; ++i) {
newA[i] = p.a[i].negate();
}
} else {
System.arraycopy(a, lowLength, newA, lowLength, highLength - lowLength);
}
return new Rational(newA);
}
/** Negate the instance.
* @return a new polynomial
*/
public Polynomial negate() {
RationalNumber[] newA = new RationalNumber[a.length];
for (int i = 0; i < a.length; ++i) {
newA[i] = a[i].negate();
}
return new Rational(newA);
}
/** Multiply the instance by a polynomial.
* @param p polynomial to multiply by
* @return a new polynomial
*/
public Rational multiply(Rational p) {
RationalNumber[] newA = new RationalNumber[a.length + p.a.length - 1];
for (int i = 0; i < newA.length; ++i) {
newA[i] = RationalNumber.ZERO;
for (int j = Math.max(0, i + 1 - p.a.length);
j < Math.min(a.length, i + 1);
++j) {
newA[i] = newA[i].add(a[j].multiply(p.a[i-j]));
}
}
return new Rational(newA);
}
/** Multiply the instance by a constant.
* @param l constant to multiply by
* @return a new polynomial
*/
public Polynomial multiply(long l) {
return multiply(new RationalNumber(l));
}
/** Multiply the instance by a constant.
* @param r constant to multiply by
* @return a new polynomial
*/
public Polynomial multiply(RationalNumber r) {
if (r.isZero()) {
return new Rational(new RationalNumber[] { RationalNumber.ZERO });
}
if (r.isOne()) {
return this;
}
RationalNumber[] newA = new RationalNumber[a.length];
for (int i = 0; i < a.length; ++i) {
newA[i] = a[i].multiply(r);
}
return new Rational(newA);
}
/** Get the value of the polynomial for a specified unknown.
* @param x value of the unknown
* @return value of the polynomial
*/
public double valueAt(double x) {
double y = 0;
for (int i = a.length - 1; i >= 0; --i) {
y = y * x + a[i].doubleValue();
}
return y;
}
/** Get the derivative of the instance with respect to the unknown.
* The derivative of a n degree polynomial is a n-1 degree polynomial of
* the same type.
* @return a new polynomial which is the derivative of the instance
*/
public Polynomial getDerivative() {
if (a.length == 1) {
return new Rational();
}
RationalNumber[] newA = new RationalNumber[a.length - 1];
for (int i = 1; i < a.length; ++i) {
newA[i - 1] = a[i].multiply(i);
}
return new Rational(newA);
}
/** Perform the euclidian division of two polynomials.
* @param dividend numerator polynomial
* @param divisor denominator polynomial
* @return an object containing the quotient and the remainder of the division
*/
public static DivisionResult euclidianDivision(Rational dividend,
Rational divisor) {
Rational quotient = new Rational(0l);
Rational remainder = dividend;
int divisorDegree = divisor.getDegree();
int remainderDegree = remainder.getDegree();
while ((! remainder.isZero()) && (remainderDegree >= divisorDegree)) {
RationalNumber c =
remainder.a[remainderDegree].divide(divisor.a[divisorDegree]);
Rational monomial = new Rational(c, remainderDegree - divisorDegree);
remainder = remainder.subtract(monomial.multiply(divisor));
quotient = quotient.add(monomial);
remainderDegree = remainder.getDegree();
}
return new DivisionResult(quotient, remainder);
}
/** Get the Least Common Multiple of the coefficients denominators.
* This number is the smallest integer by which we should multiply
* the instance to get a polynomial whose coefficients are all integers.
* @return the Least Common Multiple of the coefficients denominators
*/
public BigInteger getDenominatorsLCM() {
BigInteger lcm = BigInteger.ONE;
for (int i = 0; i < a.length; ++i) {
RationalNumber newCoeff = a[i].multiply(lcm);
if (! newCoeff.isInteger()) {
lcm = lcm.multiply(newCoeff.getDenominator());
}
}
return lcm;
}
/** Returns a string representation of the polynomial.
* The representation is user oriented. Terms are displayed lowest
* degrees first. The multiplications signs, coefficients equals to
* one and null terms are not displayed (except if the polynomial is 0,
* in which case the 0 constant term is displayed). Addition of terms
* with negative coefficients are replaced by subtraction of terms
* with positive coefficients except for the first displayed term
* (i.e. we display -3 for a constant negative polynomial,
* but 1 - 3 x + x^2 if the negative coefficient is not
* the first one displayed).
* @return a string representation of the polynomial
*/
public String toString() {
StringBuffer s = new StringBuffer();
if (a[0].isZero()) {
if (a.length == 1) {
return "0";
}
} else {
s.append(a[0].toString());
}
for (int i = 1; i < a.length; ++i) {
if (! a[i].isZero()) {
if (s.length() > 0) {
if (a[i].isNegative()) {
s.append(" - ");
} else {
s.append(" + ");
}
} else {
if (a[i].isNegative()) {
s.append("-");
}
}
RationalNumber absAi = RationalNumber.abs(a[i]);
if (! absAi.isOne()) {
s.append(absAi.toString());
s.append(' ');
}
s.append("x");
if (i > 1) {
s.append('^');
s.append(Integer.toString(i));
}
}
}
return s.toString();
}
/** Coefficients array. */
protected RationalNumber[] a;
private static final long serialVersionUID = -794133890636181115L;
}
/** This class stores the result of the euclidian division of two polynomials.
* This class is a simple placeholder, it does not provide any
* processing method
* @see Polynomial.Rational#euclidianDivision
*/
public static class DivisionResult {
/** The quotient of the division. */
public final Rational quotient;
/** The remainder of the division. */
public final Rational remainder;
/** Simple constructor. */
public DivisionResult(Rational quotient, Rational remainder) {
this.quotient = quotient;
this.remainder = remainder;
}
}
/** This class implements polynomials with one unknown and real
* coefficients.
*/
public static class Double extends Polynomial {
/** Simple constructor.
* Build a null polynomial
*/
public Double() {
a = new double[] { 0.0 };
}
/** Simple constructor.
* Build a constant polynomial
* @param value constant value of the polynomial
*/
public Double(long value) {
this((double) value);
}
/** Simple constructor.
* Build a constant polynomial
* @param value constant value of the polynomial
*/
public Double(double value) {
a = new double[] { value };
}
/** Simple constructor.
* Build a first degree polynomial
* @param a1 leeding degree coefficient
* @param a0 constant term
*/
public Double(long a1, long a0) {
this((double) a1, (double) a0);
}
/** Simple constructor.
* Build a first degree polynomial
* @param a1 leeding degree coefficient
* @param a0 constant term
*/
public Double(double a1, double a0) {
if (a1 != 0) {
a = new double[] { a0, a1 };
} else {
a = new double[] { a0 };
}
}
/** Simple constructor.
* Build a second degree polynomial
* @param a2 leeding degree coefficient
* @param a1 first degree coefficient
* @param a0 constant term
*/
public Double(long a2, long a1, long a0) {
this((double) a2, (double) a1, (double) a0);
}
/** Simple constructor.
* Build a second degree polynomial
* @param a2 leeding degree coefficient
* @param a1 first degree coefficient
* @param a0 constant term
*/
public Double(double a2, double a1, double a0) {
if (a2 != 0) {
a = new double[] { a0, a1, a2 };
} else {
if (a1 != 0) {
a = new double[] { a0, a1 };
} else {
a = new double[] { a0 };
}
}
}
/** Simple constructor.
* Build a third degree polynomial
* @param a3 leeding degree coefficient
* @param a2 second degree coefficient
* @param a1 first degree coefficient
* @param a0 constant term
*/
public Double(long a3, long a2, long a1, long a0) {
this((double) a3, (double) a2, (double) a1, (double) a0);
}
/** Simple constructor.
* Build a third degree polynomial
* @param a3 leeding degree coefficient
* @param a2 second degree coefficient
* @param a1 first degree coefficient
* @param a0 constant term
*/
public Double(double a3, double a2, double a1, double a0) {
if (a3 != 0) {
a = new double[] { a0, a1, a2, a3 };
} else {
if (a2 != 0) {
a = new double[] { a0, a1, a2 };
} else {
if (a1 != 0) {
a = new double[] { a0, a1 };
} else {
a = new double[] { a0 };
}
}
}
}
/** Simple constructor.
* Build a polynomial from its coefficients
* @param a coefficients array, the a[0] array element is the
* constant term while the a[a.length-1] element is the leeding
* degree coefficient. The array is copied in a new array, so it
* can be changed once the constructor as returned.
*/
public Double(double[] a) {
// remove null high degree coefficients
int i = a.length - 1;
while ((i > 0) && (a[i] == 0)) {
--i;
}
// copy the remaining coefficients
this.a = new double[i + 1];
System.arraycopy(a, 0, this.a, 0, i + 1);
}
/** Simple constructor.
* Build a one term polynomial from one coefficient and the corresponding degree
* @param c coefficient
* @param degree degree associated with the coefficient
*/
public Double(double c, int degree) {
if ((c == 0) || degree < 0) {
a = new double[] { 0.0 };
} else {
a = new double[degree + 1];
Arrays.fill(a, 0, degree, 0.0);
a[degree] = c;
}
}
/** Simple constructor.
* Build a {@link Polynomial.Double Polynomial.Double} from a
* {@link Polynomial.Rational Polynomial.Rational}
* @param r a rational polynomial
*/
public Double(Rational r) {
// convert the coefficients
a = new double[r.a.length];
for (int i = 0; i < a.length; ++i) {
a[i] = r.a[i].doubleValue();
}
}
/** Check if the instance is the null polynomial.
* @return true if the polynomial is null
*/
public boolean isZero() {
return (a.length == 1) && (a[0] == 0);
}
/** Check if the instance is the constant unit polynomial.
* @return true if the polynomial is the constant unit polynomial
*/
public boolean isOne() {
return (a.length == 1) && ((a[0] - 1.0) == 0);
}
/** Check if the instance is the identity polynomial.
* @return true if the polynomial is the identity polynomial
*/
public boolean isIdentity() {
return (a.length == 2) && (a[0] == 0) && ((a[1] - 1.0) == 0);
}
/** Get the polynomial degree.
* @return degree
*/
public int getDegree() {
return a.length - 1;
}
/** Get the coefficients of the polynomial.
* @return a copy of the coefficients array, the array
* element at index 0 is the constant term while the element at
* index a.length-1 is the leading degree coefficient
*/
public double[] getCoefficients() {
return (double[]) a.clone();
}
/** Add a polynomial to the instance
* @param p polynomial to add
* @return a new polynomial which is the sum of the instance and p
*/
public Double add(Double p) {
// identify the lowest degree polynomial
int lowLength = Math.min(a.length, p.a.length);
int highLength = Math.max(a.length, p.a.length);
// build the coefficients array
double[] newA = new double[highLength];
for (int i = 0; i < lowLength; ++i) {
newA[i] = a[i] + p.a[i];
}
System.arraycopy((a.length < p.a.length) ? p.a : a,
lowLength, newA, lowLength, highLength - lowLength);
return new Double(newA);
}
/** Subtract a polynomial from the instance.
* @param p polynomial to subtract
* @return a new polynomial which is the difference the instance minus p
*/
public Double subtract(Double p) {
// identify the lowest degree polynomial
int lowLength = Math.min(a.length, p.a.length);
int highLength = Math.max(a.length, p.a.length);
// build the coefficients array
double[] newA = new double[highLength];
for (int i = 0; i < lowLength; ++i) {
newA[i] = a[i] - p.a[i];
}
if (a.length < p.a.length) {
for (int i = lowLength; i < highLength; ++i) {
newA[i] = -p.a[i];
}
} else {
System.arraycopy(a, lowLength, newA, lowLength, highLength - lowLength);
}
return new Double(newA);
}
/** Negate the instance.
* @return a new polynomial
*/
public Polynomial negate() {
double[] newA = new double[a.length];
for (int i = 0; i < a.length; ++i) {
newA[i] = -a[i];
}
return new Double(newA);
}
/** Multiply the instance by a polynomial.
* @param p polynomial to multiply by
* @return a new polynomial
*/
public Double multiply(Double p) {
double[] newA = new double[a.length + p.a.length - 1];
for (int i = 0; i < newA.length; ++i) {
newA[i] = 0.0;
for (int j = Math.max(0, i + 1 - p.a.length);
j < Math.min(a.length, i + 1);
++j) {
newA[i] += a[j] * p.a[i-j];
}
}
return new Double(newA);
}
/** Multiply the instance by a constant.
* @param l constant to multiply by
* @return a new polynomial
*/
public Polynomial multiply(long l) {
return multiply((double) l);
}
/** Multiply the instance by a constant.
* @param r constant to multiply by
* @return a new polynomial
*/
public Polynomial multiply(RationalNumber r) {
return multiply(r.doubleValue());
}
/** Multiply the instance by a constant.
* @param r constant to multiply by
* @return a new polynomial
*/
public Polynomial multiply(double r) {
if (r == 0) {
return new Double(new double[] { 0.0 });
}
double[] newA = new double[a.length];
for (int i = 0; i < a.length; ++i) {
newA[i] = a[i] * r;
}
return new Double(newA);
}
/** Get the value of the polynomial for a specified unknown.
* @param x value of the unknown
* @return value of the polynomial
*/
public double valueAt(double x) {
double y = 0;
for (int i = a.length - 1; i >= 0; --i) {
y = y * x + a[i];
}
return y;
}
/** Get the derivative of the instance with respect to the unknown.
* The derivative of a n degree polynomial is a n-1 degree polynomial of
* the same type.
* @return a new polynomial which is the derivative of the instance
*/
public Polynomial getDerivative() {
if (a.length == 1) {
return new Double();
}
double[] newA = new double[a.length - 1];
for (int i = 1; i < a.length; ++i) {
newA[i - 1] = a[i] * i;
}
return new Double(newA);
}
/** Returns a string representation of the polynomial.
* The representation is user oriented. Terms are displayed lowest
* degrees first. The multiplications signs, coefficients equals to
* one and null terms are not displayed (except if the polynomial is 0,
* in which case the 0 constant term is displayed). Addition of terms
* with negative coefficients are replaced by subtraction of terms
* with positive coefficients except for the first displayed term
* (i.e. we display -3 for a constant negative polynomial,
* but 1 - 3 x + x^2 if the negative coefficient is not
* the first one displayed).
* @return a string representation of the polynomial
*/
public String toString() {
StringBuffer s = new StringBuffer();
if (a[0] == 0.0) {
if (a.length == 1) {
return "0";
}
} else {
s.append(java.lang.Double.toString(a[0]));
}
for (int i = 1; i < a.length; ++i) {
if (a[i] != 0) {
if (s.length() > 0) {
if (a[i] < 0) {
s.append(" - ");
} else {
s.append(" + ");
}
} else {
if (a[i] < 0) {
s.append("-");
}
}
double absAi = Math.abs(a[i]);
if ((absAi - 1) != 0) {
s.append(java.lang.Double.toString(absAi));
s.append(' ');
}
s.append("x");
if (i > 1) {
s.append('^');
s.append(Integer.toString(i));
}
}
}
return s.toString();
}
/** Coefficients array. */
protected double[] a;
private static final long serialVersionUID = -4210522025715687648L;
}
}
Ads help maintain this website.