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.math.analysis.polynomials;
18
19 import java.io.Serializable;
20 import java.util.Arrays;
21
22 import org.apache.commons.math.MathRuntimeException;
23 import org.apache.commons.math.analysis.DifferentiableUnivariateRealFunction;
24 import org.apache.commons.math.analysis.UnivariateRealFunction;
25
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 * @version $Revision: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $
33 */
34 public class PolynomialFunction implements DifferentiableUnivariateRealFunction, Serializable {
35
36 /**
37 * Serializtion identifier
38 */
39 private static final long serialVersionUID = -7726511984200295583L;
40
41 /**
42 * The coefficients of the polynomial, ordered by degree -- i.e.,
43 * coefficients[0] is the constant term and coefficients[n] is the
44 * coefficient of x^n where n is the degree of the polynomial.
45 */
46 private final double coefficients[];
47
48 /**
49 * Construct a polynomial with the given coefficients. The first element
50 * of the coefficients array is the constant term. Higher degree
51 * coefficients follow in sequence. The degree of the resulting polynomial
52 * is the index of the last non-null element of the array, or 0 if all elements
53 * are null.
54 * <p>
55 * The constructor makes a copy of the input array and assigns the copy to
56 * the coefficients property.</p>
57 *
58 * @param c polynomial coefficients
59 * @throws NullPointerException if c is null
60 * @throws IllegalArgumentException if c is empty
61 */
62 public PolynomialFunction(double c[]) {
63 super();
64 if (c.length < 1) {
65 throw MathRuntimeException.createIllegalArgumentException("empty polynomials coefficients array");
66 }
67 int l = c.length;
68 while ((l > 1) && (c[l - 1] == 0)) {
69 --l;
70 }
71 this.coefficients = new double[l];
72 System.arraycopy(c, 0, this.coefficients, 0, l);
73 }
74
75 /**
76 * Compute the value of the function for the given argument.
77 * <p>
78 * The value returned is <br>
79 * <code>coefficients[n] * x^n + ... + coefficients[1] * x + coefficients[0]</code>
80 * </p>
81 *
82 * @param x the argument for which the function value should be computed
83 * @return the value of the polynomial at the given point
84 * @see UnivariateRealFunction#value(double)
85 */
86 public double value(double x) {
87 return evaluate(coefficients, x);
88 }
89
90
91 /**
92 * Returns the degree of the polynomial
93 *
94 * @return the degree of the polynomial
95 */
96 public int degree() {
97 return coefficients.length - 1;
98 }
99
100 /**
101 * Returns a copy of the coefficients array.
102 * <p>
103 * Changes made to the returned copy will not affect the coefficients of
104 * the polynomial.</p>
105 *
106 * @return a fresh copy of the coefficients array
107 */
108 public double[] getCoefficients() {
109 return coefficients.clone();
110 }
111
112 /**
113 * Uses Horner's Method to evaluate the polynomial with the given coefficients at
114 * the argument.
115 *
116 * @param coefficients the coefficients of the polynomial to evaluate
117 * @param argument the input value
118 * @return the value of the polynomial
119 * @throws IllegalArgumentException if coefficients is empty
120 * @throws NullPointerException if coefficients is null
121 */
122 protected static double evaluate(double[] coefficients, double argument) {
123 int n = coefficients.length;
124 if (n < 1) {
125 throw MathRuntimeException.createIllegalArgumentException("empty polynomials coefficients array");
126 }
127 double result = coefficients[n - 1];
128 for (int j = n -2; j >=0; j--) {
129 result = argument * result + coefficients[j];
130 }
131 return result;
132 }
133
134 /**
135 * Add a polynomial to the instance.
136 * @param p polynomial to add
137 * @return a new polynomial which is the sum of the instance and p
138 */
139 public PolynomialFunction add(final PolynomialFunction p) {
140
141 // identify the lowest degree polynomial
142 final int lowLength = Math.min(coefficients.length, p.coefficients.length);
143 final int highLength = Math.max(coefficients.length, p.coefficients.length);
144
145 // build the coefficients array
146 double[] newCoefficients = new double[highLength];
147 for (int i = 0; i < lowLength; ++i) {
148 newCoefficients[i] = coefficients[i] + p.coefficients[i];
149 }
150 System.arraycopy((coefficients.length < p.coefficients.length) ?
151 p.coefficients : coefficients,
152 lowLength,
153 newCoefficients, lowLength,
154 highLength - lowLength);
155
156 return new PolynomialFunction(newCoefficients);
157
158 }
159
160 /**
161 * Subtract a polynomial from the instance.
162 * @param p polynomial to subtract
163 * @return a new polynomial which is the difference the instance minus p
164 */
165 public PolynomialFunction subtract(final PolynomialFunction p) {
166
167 // identify the lowest degree polynomial
168 int lowLength = Math.min(coefficients.length, p.coefficients.length);
169 int highLength = Math.max(coefficients.length, p.coefficients.length);
170
171 // build the coefficients array
172 double[] newCoefficients = new double[highLength];
173 for (int i = 0; i < lowLength; ++i) {
174 newCoefficients[i] = coefficients[i] - p.coefficients[i];
175 }
176 if (coefficients.length < p.coefficients.length) {
177 for (int i = lowLength; i < highLength; ++i) {
178 newCoefficients[i] = -p.coefficients[i];
179 }
180 } else {
181 System.arraycopy(coefficients, lowLength, newCoefficients, lowLength,
182 highLength - lowLength);
183 }
184
185 return new PolynomialFunction(newCoefficients);
186
187 }
188
189 /**
190 * Negate the instance.
191 * @return a new polynomial
192 */
193 public PolynomialFunction negate() {
194 double[] newCoefficients = new double[coefficients.length];
195 for (int i = 0; i < coefficients.length; ++i) {
196 newCoefficients[i] = -coefficients[i];
197 }
198 return new PolynomialFunction(newCoefficients);
199 }
200
201 /**
202 * Multiply the instance by a polynomial.
203 * @param p polynomial to multiply by
204 * @return a new polynomial
205 */
206 public PolynomialFunction multiply(final PolynomialFunction p) {
207
208 double[] newCoefficients = new double[coefficients.length + p.coefficients.length - 1];
209
210 for (int i = 0; i < newCoefficients.length; ++i) {
211 newCoefficients[i] = 0.0;
212 for (int j = Math.max(0, i + 1 - p.coefficients.length);
213 j < Math.min(coefficients.length, i + 1);
214 ++j) {
215 newCoefficients[i] += coefficients[j] * p.coefficients[i-j];
216 }
217 }
218
219 return new PolynomialFunction(newCoefficients);
220
221 }
222
223 /**
224 * Returns the coefficients of the derivative of the polynomial with the given coefficients.
225 *
226 * @param coefficients the coefficients of the polynomial to differentiate
227 * @return the coefficients of the derivative or null if coefficients has length 1.
228 * @throws IllegalArgumentException if coefficients is empty
229 * @throws NullPointerException if coefficients is null
230 */
231 protected static double[] differentiate(double[] coefficients) {
232 int n = coefficients.length;
233 if (n < 1) {
234 throw MathRuntimeException.createIllegalArgumentException("empty polynomials coefficients array");
235 }
236 if (n == 1) {
237 return new double[]{0};
238 }
239 double[] result = new double[n - 1];
240 for (int i = n - 1; i > 0; i--) {
241 result[i - 1] = i * coefficients[i];
242 }
243 return result;
244 }
245
246 /**
247 * Returns the derivative as a PolynomialRealFunction
248 *
249 * @return the derivative polynomial
250 */
251 public PolynomialFunction polynomialDerivative() {
252 return new PolynomialFunction(differentiate(coefficients));
253 }
254
255 /**
256 * Returns the derivative as a UnivariateRealFunction
257 *
258 * @return the derivative function
259 */
260 public UnivariateRealFunction derivative() {
261 return polynomialDerivative();
262 }
263
264 /** Returns a string representation of the polynomial.
265
266 * <p>The representation is user oriented. Terms are displayed lowest
267 * degrees first. The multiplications signs, coefficients equals to
268 * one and null terms are not displayed (except if the polynomial is 0,
269 * in which case the 0 constant term is displayed). Addition of terms
270 * with negative coefficients are replaced by subtraction of terms
271 * with positive coefficients except for the first displayed term
272 * (i.e. we display <code>-3</code> for a constant negative polynomial,
273 * but <code>1 - 3 x + x^2</code> if the negative coefficient is not
274 * the first one displayed).</p>
275
276 * @return a string representation of the polynomial
277
278 */
279 @Override
280 public String toString() {
281
282 StringBuffer s = new StringBuffer();
283 if (coefficients[0] == 0.0) {
284 if (coefficients.length == 1) {
285 return "0";
286 }
287 } else {
288 s.append(Double.toString(coefficients[0]));
289 }
290
291 for (int i = 1; i < coefficients.length; ++i) {
292
293 if (coefficients[i] != 0) {
294
295 if (s.length() > 0) {
296 if (coefficients[i] < 0) {
297 s.append(" - ");
298 } else {
299 s.append(" + ");
300 }
301 } else {
302 if (coefficients[i] < 0) {
303 s.append("-");
304 }
305 }
306
307 double absAi = Math.abs(coefficients[i]);
308 if ((absAi - 1) != 0) {
309 s.append(Double.toString(absAi));
310 s.append(' ');
311 }
312
313 s.append("x");
314 if (i > 1) {
315 s.append('^');
316 s.append(Integer.toString(i));
317 }
318 }
319
320 }
321
322 return s.toString();
323
324 }
325
326 /** {@inheritDoc} */
327 @Override
328 public int hashCode() {
329 final int prime = 31;
330 int result = 1;
331 result = prime * result + Arrays.hashCode(coefficients);
332 return result;
333 }
334
335 /** {@inheritDoc} */
336 @Override
337 public boolean equals(Object obj) {
338 if (this == obj)
339 return true;
340 if (obj == null)
341 return false;
342 if (!(obj instanceof PolynomialFunction))
343 return false;
344 PolynomialFunction other = (PolynomialFunction) obj;
345 if (!Arrays.equals(coefficients, other.coefficients))
346 return false;
347 return true;
348 }
349
350 }