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.math.analysis.polynomials;
018
019 import java.io.Serializable;
020 import java.util.Arrays;
021
022 import org.apache.commons.math.MathRuntimeException;
023 import org.apache.commons.math.analysis.DifferentiableUnivariateRealFunction;
024 import org.apache.commons.math.analysis.UnivariateRealFunction;
025
026 /**
027 * Immutable representation of a real polynomial function with real coefficients.
028 * <p>
029 * <a href="http://mathworld.wolfram.com/HornersMethod.html">Horner's Method</a>
030 * is used to evaluate the function.</p>
031 *
032 * @version $Revision: 922714 $ $Date: 2010-03-13 20:35:14 -0500 (Sat, 13 Mar 2010) $
033 */
034 public class PolynomialFunction implements DifferentiableUnivariateRealFunction, Serializable {
035
036 /** Message for empty coefficients array. */
037 private static final String EMPTY_ARRAY_MESSAGE =
038 "empty polynomials coefficients array";
039
040 /**
041 * Serialization identifier
042 */
043 private static final long serialVersionUID = -7726511984200295583L;
044
045 /**
046 * The coefficients of the polynomial, ordered by degree -- i.e.,
047 * coefficients[0] is the constant term and coefficients[n] is the
048 * coefficient of x^n where n is the degree of the polynomial.
049 */
050 private final double coefficients[];
051
052 /**
053 * Construct a polynomial with the given coefficients. The first element
054 * of the coefficients array is the constant term. Higher degree
055 * coefficients follow in sequence. The degree of the resulting polynomial
056 * is the index of the last non-null element of the array, or 0 if all elements
057 * are null.
058 * <p>
059 * The constructor makes a copy of the input array and assigns the copy to
060 * the coefficients property.</p>
061 *
062 * @param c polynomial coefficients
063 * @throws NullPointerException if c is null
064 * @throws IllegalArgumentException if c is empty
065 */
066 public PolynomialFunction(double c[]) {
067 super();
068 if (c.length < 1) {
069 throw MathRuntimeException.createIllegalArgumentException(EMPTY_ARRAY_MESSAGE);
070 }
071 int l = c.length;
072 while ((l > 1) && (c[l - 1] == 0)) {
073 --l;
074 }
075 this.coefficients = new double[l];
076 System.arraycopy(c, 0, this.coefficients, 0, l);
077 }
078
079 /**
080 * Compute the value of the function for the given argument.
081 * <p>
082 * The value returned is <br>
083 * <code>coefficients[n] * x^n + ... + coefficients[1] * x + coefficients[0]</code>
084 * </p>
085 *
086 * @param x the argument for which the function value should be computed
087 * @return the value of the polynomial at the given point
088 * @see UnivariateRealFunction#value(double)
089 */
090 public double value(double x) {
091 return evaluate(coefficients, x);
092 }
093
094
095 /**
096 * Returns the degree of the polynomial
097 *
098 * @return the degree of the polynomial
099 */
100 public int degree() {
101 return coefficients.length - 1;
102 }
103
104 /**
105 * Returns a copy of the coefficients array.
106 * <p>
107 * Changes made to the returned copy will not affect the coefficients of
108 * the polynomial.</p>
109 *
110 * @return a fresh copy of the coefficients array
111 */
112 public double[] getCoefficients() {
113 return coefficients.clone();
114 }
115
116 /**
117 * Uses Horner's Method to evaluate the polynomial with the given coefficients at
118 * the argument.
119 *
120 * @param coefficients the coefficients of the polynomial to evaluate
121 * @param argument the input value
122 * @return the value of the polynomial
123 * @throws IllegalArgumentException if coefficients is empty
124 * @throws NullPointerException if coefficients is null
125 */
126 protected static double evaluate(double[] coefficients, double argument) {
127 int n = coefficients.length;
128 if (n < 1) {
129 throw MathRuntimeException.createIllegalArgumentException(EMPTY_ARRAY_MESSAGE);
130 }
131 double result = coefficients[n - 1];
132 for (int j = n -2; j >=0; j--) {
133 result = argument * result + coefficients[j];
134 }
135 return result;
136 }
137
138 /**
139 * Add a polynomial to the instance.
140 * @param p polynomial to add
141 * @return a new polynomial which is the sum of the instance and p
142 */
143 public PolynomialFunction add(final PolynomialFunction p) {
144
145 // identify the lowest degree polynomial
146 final int lowLength = Math.min(coefficients.length, p.coefficients.length);
147 final int highLength = Math.max(coefficients.length, p.coefficients.length);
148
149 // build the coefficients array
150 double[] newCoefficients = new double[highLength];
151 for (int i = 0; i < lowLength; ++i) {
152 newCoefficients[i] = coefficients[i] + p.coefficients[i];
153 }
154 System.arraycopy((coefficients.length < p.coefficients.length) ?
155 p.coefficients : coefficients,
156 lowLength,
157 newCoefficients, lowLength,
158 highLength - lowLength);
159
160 return new PolynomialFunction(newCoefficients);
161
162 }
163
164 /**
165 * Subtract a polynomial from the instance.
166 * @param p polynomial to subtract
167 * @return a new polynomial which is the difference the instance minus p
168 */
169 public PolynomialFunction subtract(final PolynomialFunction p) {
170
171 // identify the lowest degree polynomial
172 int lowLength = Math.min(coefficients.length, p.coefficients.length);
173 int highLength = Math.max(coefficients.length, p.coefficients.length);
174
175 // build the coefficients array
176 double[] newCoefficients = new double[highLength];
177 for (int i = 0; i < lowLength; ++i) {
178 newCoefficients[i] = coefficients[i] - p.coefficients[i];
179 }
180 if (coefficients.length < p.coefficients.length) {
181 for (int i = lowLength; i < highLength; ++i) {
182 newCoefficients[i] = -p.coefficients[i];
183 }
184 } else {
185 System.arraycopy(coefficients, lowLength, newCoefficients, lowLength,
186 highLength - lowLength);
187 }
188
189 return new PolynomialFunction(newCoefficients);
190
191 }
192
193 /**
194 * Negate the instance.
195 * @return a new polynomial
196 */
197 public PolynomialFunction negate() {
198 double[] newCoefficients = new double[coefficients.length];
199 for (int i = 0; i < coefficients.length; ++i) {
200 newCoefficients[i] = -coefficients[i];
201 }
202 return new PolynomialFunction(newCoefficients);
203 }
204
205 /**
206 * Multiply the instance by a polynomial.
207 * @param p polynomial to multiply by
208 * @return a new polynomial
209 */
210 public PolynomialFunction multiply(final PolynomialFunction p) {
211
212 double[] newCoefficients = new double[coefficients.length + p.coefficients.length - 1];
213
214 for (int i = 0; i < newCoefficients.length; ++i) {
215 newCoefficients[i] = 0.0;
216 for (int j = Math.max(0, i + 1 - p.coefficients.length);
217 j < Math.min(coefficients.length, i + 1);
218 ++j) {
219 newCoefficients[i] += coefficients[j] * p.coefficients[i-j];
220 }
221 }
222
223 return new PolynomialFunction(newCoefficients);
224
225 }
226
227 /**
228 * Returns the coefficients of the derivative of the polynomial with the given coefficients.
229 *
230 * @param coefficients the coefficients of the polynomial to differentiate
231 * @return the coefficients of the derivative or null if coefficients has length 1.
232 * @throws IllegalArgumentException if coefficients is empty
233 * @throws NullPointerException if coefficients is null
234 */
235 protected static double[] differentiate(double[] coefficients) {
236 int n = coefficients.length;
237 if (n < 1) {
238 throw MathRuntimeException.createIllegalArgumentException(EMPTY_ARRAY_MESSAGE);
239 }
240 if (n == 1) {
241 return new double[]{0};
242 }
243 double[] result = new double[n - 1];
244 for (int i = n - 1; i > 0; i--) {
245 result[i - 1] = i * coefficients[i];
246 }
247 return result;
248 }
249
250 /**
251 * Returns the derivative as a PolynomialRealFunction
252 *
253 * @return the derivative polynomial
254 */
255 public PolynomialFunction polynomialDerivative() {
256 return new PolynomialFunction(differentiate(coefficients));
257 }
258
259 /**
260 * Returns the derivative as a UnivariateRealFunction
261 *
262 * @return the derivative function
263 */
264 public UnivariateRealFunction derivative() {
265 return polynomialDerivative();
266 }
267
268 /** Returns a string representation of the polynomial.
269
270 * <p>The representation is user oriented. Terms are displayed lowest
271 * degrees first. The multiplications signs, coefficients equals to
272 * one and null terms are not displayed (except if the polynomial is 0,
273 * in which case the 0 constant term is displayed). Addition of terms
274 * with negative coefficients are replaced by subtraction of terms
275 * with positive coefficients except for the first displayed term
276 * (i.e. we display <code>-3</code> for a constant negative polynomial,
277 * but <code>1 - 3 x + x^2</code> if the negative coefficient is not
278 * the first one displayed).</p>
279
280 * @return a string representation of the polynomial
281
282 */
283 @Override
284 public String toString() {
285
286 StringBuffer s = new StringBuffer();
287 if (coefficients[0] == 0.0) {
288 if (coefficients.length == 1) {
289 return "0";
290 }
291 } else {
292 s.append(Double.toString(coefficients[0]));
293 }
294
295 for (int i = 1; i < coefficients.length; ++i) {
296
297 if (coefficients[i] != 0) {
298
299 if (s.length() > 0) {
300 if (coefficients[i] < 0) {
301 s.append(" - ");
302 } else {
303 s.append(" + ");
304 }
305 } else {
306 if (coefficients[i] < 0) {
307 s.append("-");
308 }
309 }
310
311 double absAi = Math.abs(coefficients[i]);
312 if ((absAi - 1) != 0) {
313 s.append(Double.toString(absAi));
314 s.append(' ');
315 }
316
317 s.append("x");
318 if (i > 1) {
319 s.append('^');
320 s.append(Integer.toString(i));
321 }
322 }
323
324 }
325
326 return s.toString();
327
328 }
329
330 /** {@inheritDoc} */
331 @Override
332 public int hashCode() {
333 final int prime = 31;
334 int result = 1;
335 result = prime * result + Arrays.hashCode(coefficients);
336 return result;
337 }
338
339 /** {@inheritDoc} */
340 @Override
341 public boolean equals(Object obj) {
342 if (this == obj)
343 return true;
344 if (!(obj instanceof PolynomialFunction))
345 return false;
346 PolynomialFunction other = (PolynomialFunction) obj;
347 if (!Arrays.equals(coefficients, other.coefficients))
348 return false;
349 return true;
350 }
351
352 }