View Javadoc
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    *      https://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  
18  /*
19   * This is not the original file distributed by the Apache Software Foundation
20   * It has been modified by the Hipparchus project
21   */
22  package org.hipparchus.analysis.polynomials;
23  
24  import java.io.Serializable;
25  import java.util.Arrays;
26  
27  import org.hipparchus.CalculusFieldElement;
28  import org.hipparchus.analysis.FieldUnivariateFunction;
29  import org.hipparchus.analysis.ParametricUnivariateFunction;
30  import org.hipparchus.analysis.differentiation.Derivative;
31  import org.hipparchus.analysis.differentiation.UnivariateDifferentiableFunction;
32  import org.hipparchus.exception.LocalizedCoreFormats;
33  import org.hipparchus.exception.MathIllegalArgumentException;
34  import org.hipparchus.exception.NullArgumentException;
35  import org.hipparchus.util.FastMath;
36  import org.hipparchus.util.MathUtils;
37  
38  /**
39   * Immutable representation of a real polynomial function with real coefficients.
40   * <p>
41   * <a href="http://mathworld.wolfram.com/HornersMethod.html">Horner's Method</a>
42   * is used to evaluate the function.</p>
43   *
44   */
45  public class PolynomialFunction implements UnivariateDifferentiableFunction, FieldUnivariateFunction, Serializable {
46      /**
47       * Serialization identifier
48       */
49      private static final long serialVersionUID = -7726511984200295583L;
50      /**
51       * The coefficients of the polynomial, ordered by degree -- i.e.,
52       * coefficients[0] is the constant term and coefficients[n] is the
53       * coefficient of x^n where n is the degree of the polynomial.
54       */
55      private final double[] coefficients;
56  
57      /**
58       * Construct a polynomial with the given coefficients.  The first element
59       * of the coefficients array is the constant term.  Higher degree
60       * coefficients follow in sequence.  The degree of the resulting polynomial
61       * is the index of the last non-null element of the array, or 0 if all elements
62       * are null.
63       * <p>
64       * The constructor makes a copy of the input array and assigns the copy to
65       * the coefficients property.</p>
66       *
67       * @param c Polynomial coefficients.
68       * @throws NullArgumentException if {@code c} is {@code null}.
69       * @throws MathIllegalArgumentException if {@code c} is empty.
70       */
71      public PolynomialFunction(double... c)
72          throws MathIllegalArgumentException, NullArgumentException {
73          MathUtils.checkNotNull(c);
74          int n = c.length;
75          if (n == 0) {
76              throw new MathIllegalArgumentException(LocalizedCoreFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
77          }
78          while ((n > 1) && (c[n - 1] == 0)) {
79              --n;
80          }
81          this.coefficients = new double[n];
82          System.arraycopy(c, 0, this.coefficients, 0, n);
83      }
84  
85      /**
86       * Compute the value of the function for the given argument.
87       * <p>
88       *  The value returned is </p><p>
89       *  {@code coefficients[n] * x^n + ... + coefficients[1] * x  + coefficients[0]}
90       * </p>
91       *
92       * @param x Argument for which the function value should be computed.
93       * @return the value of the polynomial at the given point.
94       *
95       * @see org.hipparchus.analysis.UnivariateFunction#value(double)
96       */
97      @Override
98      public double value(double x) {
99         return evaluate(coefficients, x);
100     }
101 
102     /**
103      * Returns the degree of the polynomial.
104      *
105      * @return the degree of the polynomial.
106      */
107     public int degree() {
108         return coefficients.length - 1;
109     }
110 
111     /**
112      * Returns a copy of the coefficients array.
113      * <p>
114      * Changes made to the returned copy will not affect the coefficients of
115      * the polynomial.</p>
116      *
117      * @return a fresh copy of the coefficients array.
118      */
119     public double[] getCoefficients() {
120         return coefficients.clone();
121     }
122 
123     /**
124      * Uses Horner's Method to evaluate the polynomial with the given coefficients at
125      * the argument.
126      *
127      * @param coefficients Coefficients of the polynomial to evaluate.
128      * @param argument Input value.
129      * @return the value of the polynomial.
130      * @throws MathIllegalArgumentException if {@code coefficients} is empty.
131      * @throws NullArgumentException if {@code coefficients} is {@code null}.
132      */
133     protected static double evaluate(double[] coefficients, double argument)
134         throws MathIllegalArgumentException, NullArgumentException {
135         MathUtils.checkNotNull(coefficients);
136         int n = coefficients.length;
137         if (n == 0) {
138             throw new MathIllegalArgumentException(LocalizedCoreFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
139         }
140         double result = coefficients[n - 1];
141         for (int j = n - 2; j >= 0; j--) {
142             result = argument * result + coefficients[j];
143         }
144         return result;
145     }
146 
147 
148     /** {@inheritDoc}
149      * @throws MathIllegalArgumentException if {@code coefficients} is empty.
150      * @throws NullArgumentException if {@code coefficients} is {@code null}.
151      */
152     @Override
153     public <T extends Derivative<T>> T value(final T t)
154         throws MathIllegalArgumentException, NullArgumentException {
155         MathUtils.checkNotNull(coefficients);
156         int n = coefficients.length;
157         if (n == 0) {
158             throw new MathIllegalArgumentException(LocalizedCoreFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
159         }
160         T result = t.getField().getZero().add(coefficients[n - 1]);
161         for (int j = n - 2; j >= 0; j--) {
162             result = result.multiply(t).add(coefficients[j]);
163         }
164         return result;
165     }
166 
167     /** {@inheritDoc}
168      * @throws MathIllegalArgumentException if {@code coefficients} is empty.
169      * @throws NullArgumentException if {@code coefficients} is {@code null}.
170      * @since 1.3
171      */
172     @Override
173     public <T extends CalculusFieldElement<T>> T value(final T t)
174         throws MathIllegalArgumentException, NullArgumentException {
175         MathUtils.checkNotNull(coefficients);
176         int n = coefficients.length;
177         if (n == 0) {
178             throw new MathIllegalArgumentException(LocalizedCoreFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
179         }
180         T result = t.getField().getZero().add(coefficients[n - 1]);
181         for (int j = n - 2; j >= 0; j--) {
182             result = result.multiply(t).add(coefficients[j]);
183         }
184         return result;
185     }
186 
187     /**
188      * Add a polynomial to the instance.
189      *
190      * @param p Polynomial to add.
191      * @return a new polynomial which is the sum of the instance and {@code p}.
192      */
193     public PolynomialFunction add(final PolynomialFunction p) {
194         // identify the lowest degree polynomial
195         final int lowLength  = FastMath.min(coefficients.length, p.coefficients.length);
196         final int highLength = FastMath.max(coefficients.length, p.coefficients.length);
197 
198         // build the coefficients array
199         double[] newCoefficients = new double[highLength];
200         for (int i = 0; i < lowLength; ++i) {
201             newCoefficients[i] = coefficients[i] + p.coefficients[i];
202         }
203         System.arraycopy((coefficients.length < p.coefficients.length) ?
204                          p.coefficients : coefficients,
205                          lowLength,
206                          newCoefficients, lowLength,
207                          highLength - lowLength);
208 
209         return new PolynomialFunction(newCoefficients);
210     }
211 
212     /**
213      * Subtract a polynomial from the instance.
214      *
215      * @param p Polynomial to subtract.
216      * @return a new polynomial which is the instance minus {@code p}.
217      */
218     public PolynomialFunction subtract(final PolynomialFunction p) {
219         // identify the lowest degree polynomial
220         int lowLength  = FastMath.min(coefficients.length, p.coefficients.length);
221         int highLength = FastMath.max(coefficients.length, p.coefficients.length);
222 
223         // build the coefficients array
224         double[] newCoefficients = new double[highLength];
225         for (int i = 0; i < lowLength; ++i) {
226             newCoefficients[i] = coefficients[i] - p.coefficients[i];
227         }
228         if (coefficients.length < p.coefficients.length) {
229             for (int i = lowLength; i < highLength; ++i) {
230                 newCoefficients[i] = -p.coefficients[i];
231             }
232         } else {
233             System.arraycopy(coefficients, lowLength, newCoefficients, lowLength,
234                              highLength - lowLength);
235         }
236 
237         return new PolynomialFunction(newCoefficients);
238     }
239 
240     /**
241      * Negate the instance.
242      *
243      * @return a new polynomial with all coefficients negated
244      */
245     public PolynomialFunction negate() {
246         double[] newCoefficients = new double[coefficients.length];
247         for (int i = 0; i < coefficients.length; ++i) {
248             newCoefficients[i] = -coefficients[i];
249         }
250         return new PolynomialFunction(newCoefficients);
251     }
252 
253     /**
254      * Multiply the instance by a polynomial.
255      *
256      * @param p Polynomial to multiply by.
257      * @return a new polynomial equal to this times {@code p}
258      */
259     public PolynomialFunction multiply(final PolynomialFunction p) {
260         double[] newCoefficients = new double[coefficients.length + p.coefficients.length - 1];
261 
262         for (int i = 0; i < newCoefficients.length; ++i) {
263             newCoefficients[i] = 0.0;
264             for (int j = FastMath.max(0, i + 1 - p.coefficients.length);
265                  j < FastMath.min(coefficients.length, i + 1);
266                  ++j) {
267                 newCoefficients[i] += coefficients[j] * p.coefficients[i-j];
268             }
269         }
270 
271         return new PolynomialFunction(newCoefficients);
272     }
273 
274     /**
275      * Returns the coefficients of the derivative of the polynomial with the given coefficients.
276      *
277      * @param coefficients Coefficients of the polynomial to differentiate.
278      * @return the coefficients of the derivative or {@code null} if coefficients has length 1.
279      * @throws MathIllegalArgumentException if {@code coefficients} is empty.
280      * @throws NullArgumentException if {@code coefficients} is {@code null}.
281      */
282     protected static double[] differentiate(double[] coefficients)
283         throws MathIllegalArgumentException, NullArgumentException {
284         MathUtils.checkNotNull(coefficients);
285         int n = coefficients.length;
286         if (n == 0) {
287             throw new MathIllegalArgumentException(LocalizedCoreFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
288         }
289         if (n == 1) {
290             return new double[]{0};
291         }
292         double[] result = new double[n - 1];
293         for (int i = n - 1; i > 0; i--) {
294             result[i - 1] = i * coefficients[i];
295         }
296         return result;
297     }
298 
299     /**
300      * Returns an anti-derivative of this polynomial, with 0 constant term.
301      *
302      * @return a polynomial whose derivative has the same coefficients as this polynomial
303      */
304     public PolynomialFunction antiDerivative() {
305         final int d = degree();
306         final double[] anti = new double[d + 2];
307         anti[0] = 0d;
308         for (int i = 1; i <= d + 1; i++) {
309             anti[i] = coefficients[i - 1]  / i;
310         }
311         return new PolynomialFunction(anti);
312     }
313 
314     /**
315      * Returns the definite integral of this polymomial over the given interval.
316      * <p>
317      * [lower, upper] must describe a finite interval (neither can be infinite
318      * and lower must be less than or equal to upper).
319      *
320      * @param lower lower bound for the integration
321      * @param upper upper bound for the integration
322      * @return the integral of this polymomial over the given interval
323      * @throws MathIllegalArgumentException if the bounds do not describe a finite interval
324      */
325     public double integrate(final double lower, final double upper) {
326         if (Double.isInfinite(lower) || Double.isInfinite(upper)) {
327             throw new MathIllegalArgumentException(LocalizedCoreFormats.INFINITE_BOUND);
328         }
329         if (lower > upper) {
330             throw new MathIllegalArgumentException(LocalizedCoreFormats.LOWER_BOUND_NOT_BELOW_UPPER_BOUND);
331         }
332         final PolynomialFunction anti = antiDerivative();
333         return anti.value(upper) - anti.value(lower);
334     }
335 
336     /**
337      * Returns the derivative as a {@link PolynomialFunction}.
338      *
339      * @return the derivative polynomial.
340      */
341     public PolynomialFunction polynomialDerivative() {
342         return new PolynomialFunction(differentiate(coefficients));
343     }
344 
345     /**
346      * Returns a string representation of the polynomial.
347      *
348      * <p>The representation is user oriented. Terms are displayed lowest
349      * degrees first. The multiplications signs, coefficients equals to
350      * one and null terms are not displayed (except if the polynomial is 0,
351      * in which case the 0 constant term is displayed). Addition of terms
352      * with negative coefficients are replaced by subtraction of terms
353      * with positive coefficients except for the first displayed term
354      * (i.e. we display <code>-3</code> for a constant negative polynomial,
355      * but <code>1 - 3 x + x^2</code> if the negative coefficient is not
356      * the first one displayed).</p>
357      *
358      * @return a string representation of the polynomial.
359      */
360     @Override
361     public String toString() {
362         StringBuilder s = new StringBuilder();
363         if (coefficients[0] == 0.0) {
364             if (coefficients.length == 1) {
365                 return "0";
366             }
367         } else {
368             s.append(toString(coefficients[0]));
369         }
370 
371         for (int i = 1; i < coefficients.length; ++i) {
372             if (coefficients[i] != 0) {
373                 if (s.length() > 0) {
374                     if (coefficients[i] < 0) {
375                         s.append(" - ");
376                     } else {
377                         s.append(" + ");
378                     }
379                 } else {
380                     if (coefficients[i] < 0) {
381                         s.append('-');
382                     }
383                 }
384 
385                 double absAi = FastMath.abs(coefficients[i]);
386                 if ((absAi - 1) != 0) {
387                     s.append(toString(absAi)).append(' ');
388                 }
389 
390                 s.append('x');
391                 if (i > 1) {
392                     s.append('^').append(i);
393                 }
394             }
395         }
396 
397         return s.toString();
398     }
399 
400     /**
401      * Creates a string representing a coefficient, removing ".0" endings.
402      *
403      * @param coeff Coefficient.
404      * @return a string representation of {@code coeff}.
405      */
406     private static String toString(double coeff) {
407         final String c = Double.toString(coeff);
408         if (c.endsWith(".0")) {
409             return c.substring(0, c.length() - 2);
410         } else {
411             return c;
412         }
413     }
414 
415     /** {@inheritDoc} */
416     @Override
417     public int hashCode() {
418         final int prime = 31;
419         int result = 1;
420         result = prime * result + Arrays.hashCode(coefficients);
421         return result;
422     }
423 
424     /** {@inheritDoc} */
425     @Override
426     public boolean equals(Object obj) {
427         if (this == obj) {
428             return true;
429         }
430         if (!(obj instanceof PolynomialFunction)) {
431             return false;
432         }
433         PolynomialFunction other = (PolynomialFunction) obj;
434         return Arrays.equals(coefficients, other.coefficients);
435     }
436 
437     /**
438      * Dedicated parametric polynomial class.
439      *
440      */
441     public static class Parametric implements ParametricUnivariateFunction {
442 
443         /** Empty constructor.
444          * <p>
445          * This constructor is not strictly necessary, but it prevents spurious
446          * javadoc warnings with JDK 18 and later.
447          * </p>
448          * @since 3.0
449          */
450         public Parametric() { // NOPMD - unnecessary constructor added intentionally to make javadoc happy
451             // nothing to do
452         }
453 
454         /** {@inheritDoc} */
455         @Override
456         public double[] gradient(double x, double ... parameters) {
457             final double[] gradient = new double[parameters.length];
458             double xn = 1.0;
459             for (int i = 0; i < parameters.length; ++i) {
460                 gradient[i] = xn;
461                 xn *= x;
462             }
463             return gradient;
464         }
465 
466         /** {@inheritDoc} */
467         @Override
468         public double value(final double x, final double ... parameters)
469             throws MathIllegalArgumentException {
470             return evaluate(parameters, x);
471         }
472     }
473 }