PolynomialFunction.java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The ASF licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *      http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.apache.commons.math4.legacy.analysis.polynomials;

  18. import java.util.Arrays;

  19. import org.apache.commons.math4.legacy.analysis.ParametricUnivariateFunction;
  20. import org.apache.commons.math4.legacy.analysis.differentiation.DerivativeStructure;
  21. import org.apache.commons.math4.legacy.analysis.differentiation.UnivariateDifferentiableFunction;
  22. import org.apache.commons.math4.legacy.exception.NoDataException;
  23. import org.apache.commons.math4.legacy.exception.NullArgumentException;
  24. import org.apache.commons.math4.legacy.exception.util.LocalizedFormats;
  25. import org.apache.commons.math4.core.jdkmath.JdkMath;

  26. /**
  27.  * Immutable representation of a real polynomial function with real coefficients.
  28.  * <p>
  29.  * <a href="http://mathworld.wolfram.com/HornersMethod.html">Horner's Method</a>
  30.  * is used to evaluate the function.</p>
  31.  *
  32.  */
  33. public class PolynomialFunction implements UnivariateDifferentiableFunction {
  34.     /**
  35.      * The coefficients of the polynomial, ordered by degree -- i.e.,
  36.      * coefficients[0] is the constant term and coefficients[n] is the
  37.      * coefficient of x^n where n is the degree of the polynomial.
  38.      */
  39.     private final double[] coefficients;

  40.     /**
  41.      * Construct a polynomial with the given coefficients.  The first element
  42.      * of the coefficients array is the constant term.  Higher degree
  43.      * coefficients follow in sequence.  The degree of the resulting polynomial
  44.      * is the index of the last non-null element of the array, or 0 if all elements
  45.      * are null.
  46.      * <p>
  47.      * The constructor makes a copy of the input array and assigns the copy to
  48.      * the coefficients property.</p>
  49.      *
  50.      * @param c Polynomial coefficients.
  51.      * @throws NullArgumentException if {@code c} is {@code null}.
  52.      * @throws NoDataException if {@code c} is empty.
  53.      */
  54.     public PolynomialFunction(double[] c)
  55.         throws NullArgumentException, NoDataException {
  56.         super();
  57.         NullArgumentException.check(c);
  58.         int n = c.length;
  59.         if (n == 0) {
  60.             throw new NoDataException(LocalizedFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
  61.         }
  62.         while (n > 1 && c[n - 1] == 0) {
  63.             --n;
  64.         }
  65.         this.coefficients = new double[n];
  66.         System.arraycopy(c, 0, this.coefficients, 0, n);
  67.     }

  68.     /**
  69.      * Compute the value of the function for the given argument.
  70.      * <p>
  71.      *  The value returned is </p><p>
  72.      *  {@code coefficients[n] * x^n + ... + coefficients[1] * x  + coefficients[0]}
  73.      * </p>
  74.      *
  75.      * @param x Argument for which the function value should be computed.
  76.      * @return the value of the polynomial at the given point.
  77.      *
  78.      * @see org.apache.commons.math4.legacy.analysis.UnivariateFunction#value(double)
  79.      */
  80.     @Override
  81.     public double value(double x) {
  82.        return evaluate(coefficients, x);
  83.     }

  84.     /**
  85.      * Returns the degree of the polynomial.
  86.      *
  87.      * @return the degree of the polynomial.
  88.      */
  89.     public int degree() {
  90.         return coefficients.length - 1;
  91.     }

  92.     /**
  93.      * Returns a copy of the coefficients array.
  94.      * <p>
  95.      * Changes made to the returned copy will not affect the coefficients of
  96.      * the polynomial.</p>
  97.      *
  98.      * @return a fresh copy of the coefficients array.
  99.      */
  100.     public double[] getCoefficients() {
  101.         return coefficients.clone();
  102.     }

  103.     /**
  104.      * Uses Horner's Method to evaluate the polynomial with the given coefficients at
  105.      * the argument.
  106.      *
  107.      * @param coefficients Coefficients of the polynomial to evaluate.
  108.      * @param argument Input value.
  109.      * @return the value of the polynomial.
  110.      * @throws NoDataException if {@code coefficients} is empty.
  111.      * @throws NullArgumentException if {@code coefficients} is {@code null}.
  112.      */
  113.     protected static double evaluate(double[] coefficients, double argument)
  114.         throws NullArgumentException, NoDataException {
  115.         NullArgumentException.check(coefficients);
  116.         int n = coefficients.length;
  117.         if (n == 0) {
  118.             throw new NoDataException(LocalizedFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
  119.         }
  120.         double result = coefficients[n - 1];
  121.         for (int j = n - 2; j >= 0; j--) {
  122.             result = argument * result + coefficients[j];
  123.         }
  124.         return result;
  125.     }


  126.     /** {@inheritDoc}
  127.      * @since 3.1
  128.      * @throws NoDataException if {@code coefficients} is empty.
  129.      * @throws NullArgumentException if {@code coefficients} is {@code null}.
  130.      */
  131.     @Override
  132.     public DerivativeStructure value(final DerivativeStructure t)
  133.         throws NullArgumentException, NoDataException {
  134.         NullArgumentException.check(coefficients);
  135.         int n = coefficients.length;
  136.         if (n == 0) {
  137.             throw new NoDataException(LocalizedFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
  138.         }
  139.         DerivativeStructure result =
  140.                 new DerivativeStructure(t.getFreeParameters(), t.getOrder(), coefficients[n - 1]);
  141.         for (int j = n - 2; j >= 0; j--) {
  142.             result = result.multiply(t).add(coefficients[j]);
  143.         }
  144.         return result;
  145.     }

  146.     /**
  147.      * Add a polynomial to the instance.
  148.      *
  149.      * @param p Polynomial to add.
  150.      * @return a new polynomial which is the sum of the instance and {@code p}.
  151.      */
  152.     public PolynomialFunction add(final PolynomialFunction p) {
  153.         // identify the lowest degree polynomial
  154.         final int lowLength  = JdkMath.min(coefficients.length, p.coefficients.length);
  155.         final int highLength = JdkMath.max(coefficients.length, p.coefficients.length);

  156.         // build the coefficients array
  157.         double[] newCoefficients = new double[highLength];
  158.         for (int i = 0; i < lowLength; ++i) {
  159.             newCoefficients[i] = coefficients[i] + p.coefficients[i];
  160.         }
  161.         System.arraycopy((coefficients.length < p.coefficients.length) ?
  162.                          p.coefficients : coefficients,
  163.                          lowLength,
  164.                          newCoefficients, lowLength,
  165.                          highLength - lowLength);

  166.         return new PolynomialFunction(newCoefficients);
  167.     }

  168.     /**
  169.      * Subtract a polynomial from the instance.
  170.      *
  171.      * @param p Polynomial to subtract.
  172.      * @return a new polynomial which is the instance minus {@code p}.
  173.      */
  174.     public PolynomialFunction subtract(final PolynomialFunction p) {
  175.         // identify the lowest degree polynomial
  176.         int lowLength  = JdkMath.min(coefficients.length, p.coefficients.length);
  177.         int highLength = JdkMath.max(coefficients.length, p.coefficients.length);

  178.         // build the coefficients array
  179.         double[] newCoefficients = new double[highLength];
  180.         for (int i = 0; i < lowLength; ++i) {
  181.             newCoefficients[i] = coefficients[i] - p.coefficients[i];
  182.         }
  183.         if (coefficients.length < p.coefficients.length) {
  184.             for (int i = lowLength; i < highLength; ++i) {
  185.                 newCoefficients[i] = -p.coefficients[i];
  186.             }
  187.         } else {
  188.             System.arraycopy(coefficients, lowLength, newCoefficients, lowLength,
  189.                              highLength - lowLength);
  190.         }

  191.         return new PolynomialFunction(newCoefficients);
  192.     }

  193.     /**
  194.      * Negate the instance.
  195.      *
  196.      * @return a new polynomial with all coefficients negated
  197.      */
  198.     public PolynomialFunction negate() {
  199.         double[] newCoefficients = new double[coefficients.length];
  200.         for (int i = 0; i < coefficients.length; ++i) {
  201.             newCoefficients[i] = -coefficients[i];
  202.         }
  203.         return new PolynomialFunction(newCoefficients);
  204.     }

  205.     /**
  206.      * Multiply the instance by a polynomial.
  207.      *
  208.      * @param p Polynomial to multiply by.
  209.      * @return a new polynomial equal to this times {@code p}
  210.      */
  211.     public PolynomialFunction multiply(final PolynomialFunction p) {
  212.         double[] newCoefficients = new double[coefficients.length + p.coefficients.length - 1];

  213.         for (int i = 0; i < newCoefficients.length; ++i) {
  214.             newCoefficients[i] = 0.0;
  215.             for (int j = JdkMath.max(0, i + 1 - p.coefficients.length);
  216.                  j < JdkMath.min(coefficients.length, i + 1);
  217.                  ++j) {
  218.                 newCoefficients[i] += coefficients[j] * p.coefficients[i-j];
  219.             }
  220.         }

  221.         return new PolynomialFunction(newCoefficients);
  222.     }

  223.     /**
  224.      * Returns the coefficients of the derivative of the polynomial with the given coefficients.
  225.      *
  226.      * @param coefficients Coefficients of the polynomial to differentiate.
  227.      * @return the coefficients of the derivative or {@code null} if coefficients has length 1.
  228.      * @throws NoDataException if {@code coefficients} is empty.
  229.      * @throws NullArgumentException if {@code coefficients} is {@code null}.
  230.      */
  231.     protected static double[] differentiate(double[] coefficients)
  232.         throws NullArgumentException, NoDataException {
  233.         NullArgumentException.check(coefficients);
  234.         int n = coefficients.length;
  235.         if (n == 0) {
  236.             throw new NoDataException(LocalizedFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
  237.         }
  238.         if (n == 1) {
  239.             return new double[]{0};
  240.         }
  241.         double[] result = new double[n - 1];
  242.         for (int i = n - 1; i > 0; i--) {
  243.             result[i - 1] = i * coefficients[i];
  244.         }
  245.         return result;
  246.     }

  247.     /**
  248.      * Returns the derivative as a {@link PolynomialFunction}.
  249.      *
  250.      * @return the derivative polynomial.
  251.      */
  252.     public PolynomialFunction polynomialDerivative() {
  253.         return new PolynomialFunction(differentiate(coefficients));
  254.     }

  255.     /**
  256.      * Returns a string representation of the polynomial.
  257.      *
  258.      * <p>The representation is user oriented. Terms are displayed lowest
  259.      * degrees first. The multiplications signs, coefficients equals to
  260.      * one and null terms are not displayed (except if the polynomial is 0,
  261.      * in which case the 0 constant term is displayed). Addition of terms
  262.      * with negative coefficients are replaced by subtraction of terms
  263.      * with positive coefficients except for the first displayed term
  264.      * (i.e. we display <code>-3</code> for a constant negative polynomial,
  265.      * but <code>1 - 3 x + x^2</code> if the negative coefficient is not
  266.      * the first one displayed).</p>
  267.      *
  268.      * @return a string representation of the polynomial.
  269.      */
  270.     @Override
  271.     public String toString() {
  272.         StringBuilder s = new StringBuilder();
  273.         if (coefficients[0] == 0.0) {
  274.             if (coefficients.length == 1) {
  275.                 return "0";
  276.             }
  277.         } else {
  278.             s.append(toString(coefficients[0]));
  279.         }

  280.         for (int i = 1; i < coefficients.length; ++i) {
  281.             if (coefficients[i] != 0) {
  282.                 if (s.length() > 0) {
  283.                     if (coefficients[i] < 0) {
  284.                         s.append(" - ");
  285.                     } else {
  286.                         s.append(" + ");
  287.                     }
  288.                 } else {
  289.                     if (coefficients[i] < 0) {
  290.                         s.append("-");
  291.                     }
  292.                 }

  293.                 double absAi = JdkMath.abs(coefficients[i]);
  294.                 if ((absAi - 1) != 0) {
  295.                     s.append(toString(absAi));
  296.                     s.append(' ');
  297.                 }

  298.                 s.append("x");
  299.                 if (i > 1) {
  300.                     s.append('^');
  301.                     s.append(Integer.toString(i));
  302.                 }
  303.             }
  304.         }

  305.         return s.toString();
  306.     }

  307.     /**
  308.      * Creates a string representing a coefficient, removing ".0" endings.
  309.      *
  310.      * @param coeff Coefficient.
  311.      * @return a string representation of {@code coeff}.
  312.      */
  313.     private static String toString(double coeff) {
  314.         final String c = Double.toString(coeff);
  315.         if (c.endsWith(".0")) {
  316.             return c.substring(0, c.length() - 2);
  317.         } else {
  318.             return c;
  319.         }
  320.     }

  321.     /** {@inheritDoc} */
  322.     @Override
  323.     public int hashCode() {
  324.         final int prime = 31;
  325.         int result = 1;
  326.         result = prime * result + Arrays.hashCode(coefficients);
  327.         return result;
  328.     }

  329.     /** {@inheritDoc} */
  330.     @Override
  331.     public boolean equals(Object obj) {
  332.         if (this == obj) {
  333.             return true;
  334.         }
  335.         if (!(obj instanceof PolynomialFunction)) {
  336.             return false;
  337.         }
  338.         PolynomialFunction other = (PolynomialFunction) obj;
  339.         return Arrays.equals(coefficients, other.coefficients);
  340.     }

  341.     /**
  342.      * Dedicated parametric polynomial class.
  343.      *
  344.      * @since 3.0
  345.      */
  346.     public static class Parametric implements ParametricUnivariateFunction {
  347.         /** {@inheritDoc} */
  348.         @Override
  349.         public double[] gradient(double x, double ... parameters) {
  350.             final double[] gradient = new double[parameters.length];
  351.             double xn = 1.0;
  352.             for (int i = 0; i < parameters.length; ++i) {
  353.                 gradient[i] = xn;
  354.                 xn *= x;
  355.             }
  356.             return gradient;
  357.         }

  358.         /** {@inheritDoc} */
  359.         @Override
  360.         public double value(final double x, final double ... parameters)
  361.             throws NoDataException {
  362.             return PolynomialFunction.evaluate(parameters, x);
  363.         }
  364.     }
  365. }