001 /*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements. See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License. You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017 package org.apache.commons.math3.analysis.polynomials;
018
019 import java.io.Serializable;
020 import java.util.Arrays;
021
022 import org.apache.commons.math3.exception.util.LocalizedFormats;
023 import org.apache.commons.math3.exception.NoDataException;
024 import org.apache.commons.math3.exception.NullArgumentException;
025 import org.apache.commons.math3.analysis.DifferentiableUnivariateFunction;
026 import org.apache.commons.math3.analysis.UnivariateFunction;
027 import org.apache.commons.math3.analysis.ParametricUnivariateFunction;
028 import org.apache.commons.math3.analysis.differentiation.DerivativeStructure;
029 import org.apache.commons.math3.analysis.differentiation.UnivariateDifferentiableFunction;
030 import org.apache.commons.math3.util.FastMath;
031 import org.apache.commons.math3.util.MathUtils;
032
033 /**
034 * Immutable representation of a real polynomial function with real coefficients.
035 * <p>
036 * <a href="http://mathworld.wolfram.com/HornersMethod.html">Horner's Method</a>
037 * is used to evaluate the function.</p>
038 *
039 * @version $Id: PolynomialFunction.java 1383441 2012-09-11 14:56:39Z luc $
040 */
041 public class PolynomialFunction implements UnivariateDifferentiableFunction, DifferentiableUnivariateFunction, Serializable {
042 /**
043 * Serialization identifier
044 */
045 private static final long serialVersionUID = -7726511984200295583L;
046 /**
047 * The coefficients of the polynomial, ordered by degree -- i.e.,
048 * coefficients[0] is the constant term and coefficients[n] is the
049 * coefficient of x^n where n is the degree of the polynomial.
050 */
051 private final double coefficients[];
052
053 /**
054 * Construct a polynomial with the given coefficients. The first element
055 * of the coefficients array is the constant term. Higher degree
056 * coefficients follow in sequence. The degree of the resulting polynomial
057 * is the index of the last non-null element of the array, or 0 if all elements
058 * are null.
059 * <p>
060 * The constructor makes a copy of the input array and assigns the copy to
061 * the coefficients property.</p>
062 *
063 * @param c Polynomial coefficients.
064 * @throws NullArgumentException if {@code c} is {@code null}.
065 * @throws NoDataException if {@code c} is empty.
066 */
067 public PolynomialFunction(double c[])
068 throws NullArgumentException, NoDataException {
069 super();
070 MathUtils.checkNotNull(c);
071 int n = c.length;
072 if (n == 0) {
073 throw new NoDataException(LocalizedFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
074 }
075 while ((n > 1) && (c[n - 1] == 0)) {
076 --n;
077 }
078 this.coefficients = new double[n];
079 System.arraycopy(c, 0, this.coefficients, 0, n);
080 }
081
082 /**
083 * Compute the value of the function for the given argument.
084 * <p>
085 * The value returned is <br/>
086 * <code>coefficients[n] * x^n + ... + coefficients[1] * x + coefficients[0]</code>
087 * </p>
088 *
089 * @param x Argument for which the function value should be computed.
090 * @return the value of the polynomial at the given point.
091 * @see UnivariateFunction#value(double)
092 */
093 public double value(double x) {
094 return evaluate(coefficients, x);
095 }
096
097 /**
098 * Returns the degree of the polynomial.
099 *
100 * @return the degree of the polynomial.
101 */
102 public int degree() {
103 return coefficients.length - 1;
104 }
105
106 /**
107 * Returns a copy of the coefficients array.
108 * <p>
109 * Changes made to the returned copy will not affect the coefficients of
110 * the polynomial.</p>
111 *
112 * @return a fresh copy of the coefficients array.
113 */
114 public double[] getCoefficients() {
115 return coefficients.clone();
116 }
117
118 /**
119 * Uses Horner's Method to evaluate the polynomial with the given coefficients at
120 * the argument.
121 *
122 * @param coefficients Coefficients of the polynomial to evaluate.
123 * @param argument Input value.
124 * @return the value of the polynomial.
125 * @throws NoDataException if {@code coefficients} is empty.
126 * @throws NullArgumentException if {@code coefficients} is {@code null}.
127 */
128 protected static double evaluate(double[] coefficients, double argument)
129 throws NullArgumentException, NoDataException {
130 MathUtils.checkNotNull(coefficients);
131 int n = coefficients.length;
132 if (n == 0) {
133 throw new NoDataException(LocalizedFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
134 }
135 double result = coefficients[n - 1];
136 for (int j = n - 2; j >= 0; j--) {
137 result = argument * result + coefficients[j];
138 }
139 return result;
140 }
141
142
143 /** {@inheritDoc}
144 * @since 3.1
145 * @throws NoDataException if {@code coefficients} is empty.
146 * @throws NullArgumentException if {@code coefficients} is {@code null}.
147 */
148 public DerivativeStructure value(final DerivativeStructure t)
149 throws NullArgumentException, NoDataException {
150 MathUtils.checkNotNull(coefficients);
151 int n = coefficients.length;
152 if (n == 0) {
153 throw new NoDataException(LocalizedFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
154 }
155 DerivativeStructure result =
156 new DerivativeStructure(t.getFreeParameters(), t.getOrder(), coefficients[n - 1]);
157 for (int j = n - 2; j >= 0; j--) {
158 result = result.multiply(t).add(coefficients[j]);
159 }
160 return result;
161 }
162
163 /**
164 * Add a polynomial to the instance.
165 *
166 * @param p Polynomial to add.
167 * @return a new polynomial which is the sum of the instance and {@code p}.
168 */
169 public PolynomialFunction add(final PolynomialFunction p) {
170 // identify the lowest degree polynomial
171 final int lowLength = FastMath.min(coefficients.length, p.coefficients.length);
172 final int highLength = FastMath.max(coefficients.length, p.coefficients.length);
173
174 // build the coefficients array
175 double[] newCoefficients = new double[highLength];
176 for (int i = 0; i < lowLength; ++i) {
177 newCoefficients[i] = coefficients[i] + p.coefficients[i];
178 }
179 System.arraycopy((coefficients.length < p.coefficients.length) ?
180 p.coefficients : coefficients,
181 lowLength,
182 newCoefficients, lowLength,
183 highLength - lowLength);
184
185 return new PolynomialFunction(newCoefficients);
186 }
187
188 /**
189 * Subtract a polynomial from the instance.
190 *
191 * @param p Polynomial to subtract.
192 * @return a new polynomial which is the difference the instance minus {@code p}.
193 */
194 public PolynomialFunction subtract(final PolynomialFunction p) {
195 // identify the lowest degree polynomial
196 int lowLength = FastMath.min(coefficients.length, p.coefficients.length);
197 int highLength = FastMath.max(coefficients.length, p.coefficients.length);
198
199 // build the coefficients array
200 double[] newCoefficients = new double[highLength];
201 for (int i = 0; i < lowLength; ++i) {
202 newCoefficients[i] = coefficients[i] - p.coefficients[i];
203 }
204 if (coefficients.length < p.coefficients.length) {
205 for (int i = lowLength; i < highLength; ++i) {
206 newCoefficients[i] = -p.coefficients[i];
207 }
208 } else {
209 System.arraycopy(coefficients, lowLength, newCoefficients, lowLength,
210 highLength - lowLength);
211 }
212
213 return new PolynomialFunction(newCoefficients);
214 }
215
216 /**
217 * Negate the instance.
218 *
219 * @return a new polynomial.
220 */
221 public PolynomialFunction negate() {
222 double[] newCoefficients = new double[coefficients.length];
223 for (int i = 0; i < coefficients.length; ++i) {
224 newCoefficients[i] = -coefficients[i];
225 }
226 return new PolynomialFunction(newCoefficients);
227 }
228
229 /**
230 * Multiply the instance by a polynomial.
231 *
232 * @param p Polynomial to multiply by.
233 * @return a new polynomial.
234 */
235 public PolynomialFunction multiply(final PolynomialFunction p) {
236 double[] newCoefficients = new double[coefficients.length + p.coefficients.length - 1];
237
238 for (int i = 0; i < newCoefficients.length; ++i) {
239 newCoefficients[i] = 0.0;
240 for (int j = FastMath.max(0, i + 1 - p.coefficients.length);
241 j < FastMath.min(coefficients.length, i + 1);
242 ++j) {
243 newCoefficients[i] += coefficients[j] * p.coefficients[i-j];
244 }
245 }
246
247 return new PolynomialFunction(newCoefficients);
248 }
249
250 /**
251 * Returns the coefficients of the derivative of the polynomial with the given coefficients.
252 *
253 * @param coefficients Coefficients of the polynomial to differentiate.
254 * @return the coefficients of the derivative or {@code null} if coefficients has length 1.
255 * @throws NoDataException if {@code coefficients} is empty.
256 * @throws NullArgumentException if {@code coefficients} is {@code null}.
257 */
258 protected static double[] differentiate(double[] coefficients)
259 throws NullArgumentException, NoDataException {
260 MathUtils.checkNotNull(coefficients);
261 int n = coefficients.length;
262 if (n == 0) {
263 throw new NoDataException(LocalizedFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
264 }
265 if (n == 1) {
266 return new double[]{0};
267 }
268 double[] result = new double[n - 1];
269 for (int i = n - 1; i > 0; i--) {
270 result[i - 1] = i * coefficients[i];
271 }
272 return result;
273 }
274
275 /**
276 * Returns the derivative as a {@link PolynomialFunction}.
277 *
278 * @return the derivative polynomial.
279 */
280 public PolynomialFunction polynomialDerivative() {
281 return new PolynomialFunction(differentiate(coefficients));
282 }
283
284 /**
285 * Returns the derivative as a {@link UnivariateFunction}.
286 *
287 * @return the derivative function.
288 */
289 public UnivariateFunction derivative() {
290 return polynomialDerivative();
291 }
292
293 /**
294 * Returns a string representation of the polynomial.
295 *
296 * <p>The representation is user oriented. Terms are displayed lowest
297 * degrees first. The multiplications signs, coefficients equals to
298 * one and null terms are not displayed (except if the polynomial is 0,
299 * in which case the 0 constant term is displayed). Addition of terms
300 * with negative coefficients are replaced by subtraction of terms
301 * with positive coefficients except for the first displayed term
302 * (i.e. we display <code>-3</code> for a constant negative polynomial,
303 * but <code>1 - 3 x + x^2</code> if the negative coefficient is not
304 * the first one displayed).</p>
305 *
306 * @return a string representation of the polynomial.
307 */
308 @Override
309 public String toString() {
310 StringBuilder s = new StringBuilder();
311 if (coefficients[0] == 0.0) {
312 if (coefficients.length == 1) {
313 return "0";
314 }
315 } else {
316 s.append(toString(coefficients[0]));
317 }
318
319 for (int i = 1; i < coefficients.length; ++i) {
320 if (coefficients[i] != 0) {
321 if (s.length() > 0) {
322 if (coefficients[i] < 0) {
323 s.append(" - ");
324 } else {
325 s.append(" + ");
326 }
327 } else {
328 if (coefficients[i] < 0) {
329 s.append("-");
330 }
331 }
332
333 double absAi = FastMath.abs(coefficients[i]);
334 if ((absAi - 1) != 0) {
335 s.append(toString(absAi));
336 s.append(' ');
337 }
338
339 s.append("x");
340 if (i > 1) {
341 s.append('^');
342 s.append(Integer.toString(i));
343 }
344 }
345 }
346
347 return s.toString();
348 }
349
350 /**
351 * Creates a string representing a coefficient, removing ".0" endings.
352 *
353 * @param coeff Coefficient.
354 * @return a string representation of {@code coeff}.
355 */
356 private static String toString(double coeff) {
357 final String c = Double.toString(coeff);
358 if (c.endsWith(".0")) {
359 return c.substring(0, c.length() - 2);
360 } else {
361 return c;
362 }
363 }
364
365 /** {@inheritDoc} */
366 @Override
367 public int hashCode() {
368 final int prime = 31;
369 int result = 1;
370 result = prime * result + Arrays.hashCode(coefficients);
371 return result;
372 }
373
374 /** {@inheritDoc} */
375 @Override
376 public boolean equals(Object obj) {
377 if (this == obj) {
378 return true;
379 }
380 if (!(obj instanceof PolynomialFunction)) {
381 return false;
382 }
383 PolynomialFunction other = (PolynomialFunction) obj;
384 if (!Arrays.equals(coefficients, other.coefficients)) {
385 return false;
386 }
387 return true;
388 }
389
390 /**
391 * Dedicated parametric polynomial class.
392 *
393 * @since 3.0
394 */
395 public static class Parametric implements ParametricUnivariateFunction {
396 /** {@inheritDoc} */
397 public double[] gradient(double x, double ... parameters) {
398 final double[] gradient = new double[parameters.length];
399 double xn = 1.0;
400 for (int i = 0; i < parameters.length; ++i) {
401 gradient[i] = xn;
402 xn *= x;
403 }
404 return gradient;
405 }
406
407 /** {@inheritDoc} */
408 public double value(final double x, final double ... parameters) {
409 return PolynomialFunction.evaluate(parameters, x);
410 }
411 }
412 }