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 }