PolynomialFunction.java
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* https://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/*
* This is not the original file distributed by the Apache Software Foundation
* It has been modified by the Hipparchus project
*/
package org.hipparchus.analysis.polynomials;
import java.io.Serializable;
import java.util.Arrays;
import org.hipparchus.CalculusFieldElement;
import org.hipparchus.analysis.FieldUnivariateFunction;
import org.hipparchus.analysis.ParametricUnivariateFunction;
import org.hipparchus.analysis.differentiation.Derivative;
import org.hipparchus.analysis.differentiation.UnivariateDifferentiableFunction;
import org.hipparchus.exception.LocalizedCoreFormats;
import org.hipparchus.exception.MathIllegalArgumentException;
import org.hipparchus.exception.NullArgumentException;
import org.hipparchus.util.FastMath;
import org.hipparchus.util.MathUtils;
/**
* Immutable representation of a real polynomial function with real coefficients.
* <p>
* <a href="http://mathworld.wolfram.com/HornersMethod.html">Horner's Method</a>
* is used to evaluate the function.</p>
*
*/
public class PolynomialFunction implements UnivariateDifferentiableFunction, FieldUnivariateFunction, Serializable {
/**
* Serialization identifier
*/
private static final long serialVersionUID = -7726511984200295583L;
/**
* The coefficients of the polynomial, ordered by degree -- i.e.,
* coefficients[0] is the constant term and coefficients[n] is the
* coefficient of x^n where n is the degree of the polynomial.
*/
private final double[] coefficients;
/**
* Construct a polynomial with the given coefficients. The first element
* of the coefficients array is the constant term. Higher degree
* coefficients follow in sequence. The degree of the resulting polynomial
* is the index of the last non-null element of the array, or 0 if all elements
* are null.
* <p>
* The constructor makes a copy of the input array and assigns the copy to
* the coefficients property.</p>
*
* @param c Polynomial coefficients.
* @throws NullArgumentException if {@code c} is {@code null}.
* @throws MathIllegalArgumentException if {@code c} is empty.
*/
public PolynomialFunction(double... c)
throws MathIllegalArgumentException, NullArgumentException {
super();
MathUtils.checkNotNull(c);
int n = c.length;
if (n == 0) {
throw new MathIllegalArgumentException(LocalizedCoreFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
}
while ((n > 1) && (c[n - 1] == 0)) {
--n;
}
this.coefficients = new double[n];
System.arraycopy(c, 0, this.coefficients, 0, n);
}
/**
* Compute the value of the function for the given argument.
* <p>
* The value returned is </p><p>
* {@code coefficients[n] * x^n + ... + coefficients[1] * x + coefficients[0]}
* </p>
*
* @param x Argument for which the function value should be computed.
* @return the value of the polynomial at the given point.
*
* @see org.hipparchus.analysis.UnivariateFunction#value(double)
*/
@Override
public double value(double x) {
return evaluate(coefficients, x);
}
/**
* Returns the degree of the polynomial.
*
* @return the degree of the polynomial.
*/
public int degree() {
return coefficients.length - 1;
}
/**
* Returns a copy of the coefficients array.
* <p>
* Changes made to the returned copy will not affect the coefficients of
* the polynomial.</p>
*
* @return a fresh copy of the coefficients array.
*/
public double[] getCoefficients() {
return coefficients.clone();
}
/**
* Uses Horner's Method to evaluate the polynomial with the given coefficients at
* the argument.
*
* @param coefficients Coefficients of the polynomial to evaluate.
* @param argument Input value.
* @return the value of the polynomial.
* @throws MathIllegalArgumentException if {@code coefficients} is empty.
* @throws NullArgumentException if {@code coefficients} is {@code null}.
*/
protected static double evaluate(double[] coefficients, double argument)
throws MathIllegalArgumentException, NullArgumentException {
MathUtils.checkNotNull(coefficients);
int n = coefficients.length;
if (n == 0) {
throw new MathIllegalArgumentException(LocalizedCoreFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
}
double result = coefficients[n - 1];
for (int j = n - 2; j >= 0; j--) {
result = argument * result + coefficients[j];
}
return result;
}
/** {@inheritDoc}
* @throws MathIllegalArgumentException if {@code coefficients} is empty.
* @throws NullArgumentException if {@code coefficients} is {@code null}.
*/
@Override
public <T extends Derivative<T>> T value(final T t)
throws MathIllegalArgumentException, NullArgumentException {
MathUtils.checkNotNull(coefficients);
int n = coefficients.length;
if (n == 0) {
throw new MathIllegalArgumentException(LocalizedCoreFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
}
T result = t.getField().getZero().add(coefficients[n - 1]);
for (int j = n - 2; j >= 0; j--) {
result = result.multiply(t).add(coefficients[j]);
}
return result;
}
/** {@inheritDoc}
* @throws MathIllegalArgumentException if {@code coefficients} is empty.
* @throws NullArgumentException if {@code coefficients} is {@code null}.
* @since 1.3
*/
@Override
public <T extends CalculusFieldElement<T>> T value(final T t)
throws MathIllegalArgumentException, NullArgumentException {
MathUtils.checkNotNull(coefficients);
int n = coefficients.length;
if (n == 0) {
throw new MathIllegalArgumentException(LocalizedCoreFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
}
T result = t.getField().getZero().add(coefficients[n - 1]);
for (int j = n - 2; j >= 0; j--) {
result = result.multiply(t).add(coefficients[j]);
}
return result;
}
/**
* Add a polynomial to the instance.
*
* @param p Polynomial to add.
* @return a new polynomial which is the sum of the instance and {@code p}.
*/
public PolynomialFunction add(final PolynomialFunction p) {
// identify the lowest degree polynomial
final int lowLength = FastMath.min(coefficients.length, p.coefficients.length);
final int highLength = FastMath.max(coefficients.length, p.coefficients.length);
// build the coefficients array
double[] newCoefficients = new double[highLength];
for (int i = 0; i < lowLength; ++i) {
newCoefficients[i] = coefficients[i] + p.coefficients[i];
}
System.arraycopy((coefficients.length < p.coefficients.length) ?
p.coefficients : coefficients,
lowLength,
newCoefficients, lowLength,
highLength - lowLength);
return new PolynomialFunction(newCoefficients);
}
/**
* Subtract a polynomial from the instance.
*
* @param p Polynomial to subtract.
* @return a new polynomial which is the instance minus {@code p}.
*/
public PolynomialFunction subtract(final PolynomialFunction p) {
// identify the lowest degree polynomial
int lowLength = FastMath.min(coefficients.length, p.coefficients.length);
int highLength = FastMath.max(coefficients.length, p.coefficients.length);
// build the coefficients array
double[] newCoefficients = new double[highLength];
for (int i = 0; i < lowLength; ++i) {
newCoefficients[i] = coefficients[i] - p.coefficients[i];
}
if (coefficients.length < p.coefficients.length) {
for (int i = lowLength; i < highLength; ++i) {
newCoefficients[i] = -p.coefficients[i];
}
} else {
System.arraycopy(coefficients, lowLength, newCoefficients, lowLength,
highLength - lowLength);
}
return new PolynomialFunction(newCoefficients);
}
/**
* Negate the instance.
*
* @return a new polynomial with all coefficients negated
*/
public PolynomialFunction negate() {
double[] newCoefficients = new double[coefficients.length];
for (int i = 0; i < coefficients.length; ++i) {
newCoefficients[i] = -coefficients[i];
}
return new PolynomialFunction(newCoefficients);
}
/**
* Multiply the instance by a polynomial.
*
* @param p Polynomial to multiply by.
* @return a new polynomial equal to this times {@code p}
*/
public PolynomialFunction multiply(final PolynomialFunction p) {
double[] newCoefficients = new double[coefficients.length + p.coefficients.length - 1];
for (int i = 0; i < newCoefficients.length; ++i) {
newCoefficients[i] = 0.0;
for (int j = FastMath.max(0, i + 1 - p.coefficients.length);
j < FastMath.min(coefficients.length, i + 1);
++j) {
newCoefficients[i] += coefficients[j] * p.coefficients[i-j];
}
}
return new PolynomialFunction(newCoefficients);
}
/**
* Returns the coefficients of the derivative of the polynomial with the given coefficients.
*
* @param coefficients Coefficients of the polynomial to differentiate.
* @return the coefficients of the derivative or {@code null} if coefficients has length 1.
* @throws MathIllegalArgumentException if {@code coefficients} is empty.
* @throws NullArgumentException if {@code coefficients} is {@code null}.
*/
protected static double[] differentiate(double[] coefficients)
throws MathIllegalArgumentException, NullArgumentException {
MathUtils.checkNotNull(coefficients);
int n = coefficients.length;
if (n == 0) {
throw new MathIllegalArgumentException(LocalizedCoreFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
}
if (n == 1) {
return new double[]{0};
}
double[] result = new double[n - 1];
for (int i = n - 1; i > 0; i--) {
result[i - 1] = i * coefficients[i];
}
return result;
}
/**
* Returns an anti-derivative of this polynomial, with 0 constant term.
*
* @return a polynomial whose derivative has the same coefficients as this polynomial
*/
public PolynomialFunction antiDerivative() {
final int d = degree();
final double[] anti = new double[d + 2];
anti[0] = 0d;
for (int i = 1; i <= d + 1; i++) {
anti[i] = coefficients[i - 1] / i;
}
return new PolynomialFunction(anti);
}
/**
* Returns the definite integral of this polymomial over the given interval.
* <p>
* [lower, upper] must describe a finite interval (neither can be infinite
* and lower must be less than or equal to upper).
*
* @param lower lower bound for the integration
* @param upper upper bound for the integration
* @return the integral of this polymomial over the given interval
* @throws MathIllegalArgumentException if the bounds do not describe a finite interval
*/
public double integrate(final double lower, final double upper) {
if (Double.isInfinite(lower) || Double.isInfinite(upper)) {
throw new MathIllegalArgumentException(LocalizedCoreFormats.INFINITE_BOUND);
}
if (lower > upper) {
throw new MathIllegalArgumentException(LocalizedCoreFormats.LOWER_BOUND_NOT_BELOW_UPPER_BOUND);
}
final PolynomialFunction anti = antiDerivative();
return anti.value(upper) - anti.value(lower);
}
/**
* Returns the derivative as a {@link PolynomialFunction}.
*
* @return the derivative polynomial.
*/
public PolynomialFunction polynomialDerivative() {
return new PolynomialFunction(differentiate(coefficients));
}
/**
* Returns a string representation of the polynomial.
*
* <p>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 <code>-3</code> for a constant negative polynomial,
* but <code>1 - 3 x + x^2</code> if the negative coefficient is not
* the first one displayed).</p>
*
* @return a string representation of the polynomial.
*/
@Override
public String toString() {
StringBuilder s = new StringBuilder();
if (coefficients[0] == 0.0) {
if (coefficients.length == 1) {
return "0";
}
} else {
s.append(toString(coefficients[0]));
}
for (int i = 1; i < coefficients.length; ++i) {
if (coefficients[i] != 0) {
if (s.length() > 0) {
if (coefficients[i] < 0) {
s.append(" - ");
} else {
s.append(" + ");
}
} else {
if (coefficients[i] < 0) {
s.append('-');
}
}
double absAi = FastMath.abs(coefficients[i]);
if ((absAi - 1) != 0) {
s.append(toString(absAi));
s.append(' ');
}
s.append('x');
if (i > 1) {
s.append('^');
s.append(i);
}
}
}
return s.toString();
}
/**
* Creates a string representing a coefficient, removing ".0" endings.
*
* @param coeff Coefficient.
* @return a string representation of {@code coeff}.
*/
private static String toString(double coeff) {
final String c = Double.toString(coeff);
if (c.endsWith(".0")) {
return c.substring(0, c.length() - 2);
} else {
return c;
}
}
/** {@inheritDoc} */
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + Arrays.hashCode(coefficients);
return result;
}
/** {@inheritDoc} */
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (!(obj instanceof PolynomialFunction)) {
return false;
}
PolynomialFunction other = (PolynomialFunction) obj;
return Arrays.equals(coefficients, other.coefficients);
}
/**
* Dedicated parametric polynomial class.
*
*/
public static class Parametric implements ParametricUnivariateFunction {
/** Empty constructor.
* <p>
* This constructor is not strictly necessary, but it prevents spurious
* javadoc warnings with JDK 18 and later.
* </p>
* @since 3.0
*/
public Parametric() { // NOPMD - unnecessary constructor added intentionally to make javadoc happy
// nothing to do
}
/** {@inheritDoc} */
@Override
public double[] gradient(double x, double ... parameters) {
final double[] gradient = new double[parameters.length];
double xn = 1.0;
for (int i = 0; i < parameters.length; ++i) {
gradient[i] = xn;
xn *= x;
}
return gradient;
}
/** {@inheritDoc} */
@Override
public double value(final double x, final double ... parameters)
throws MathIllegalArgumentException {
return PolynomialFunction.evaluate(parameters, x);
}
}
}