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: 799857 $ $Date: 2009-08-01 09:07:12 -0400 (Sat, 01 Aug 2009) $
033 */
034 public class PolynomialFunction implements DifferentiableUnivariateRealFunction, Serializable {
035
036 /**
037 * Serializtion identifier
038 */
039 private static final long serialVersionUID = -7726511984200295583L;
040
041 /**
042 * The coefficients of the polynomial, ordered by degree -- i.e.,
043 * coefficients[0] is the constant term and coefficients[n] is the
044 * coefficient of x^n where n is the degree of the polynomial.
045 */
046 private final double coefficients[];
047
048 /**
049 * Construct a polynomial with the given coefficients. The first element
050 * of the coefficients array is the constant term. Higher degree
051 * coefficients follow in sequence. The degree of the resulting polynomial
052 * is the index of the last non-null element of the array, or 0 if all elements
053 * are null.
054 * <p>
055 * The constructor makes a copy of the input array and assigns the copy to
056 * the coefficients property.</p>
057 *
058 * @param c polynomial coefficients
059 * @throws NullPointerException if c is null
060 * @throws IllegalArgumentException if c is empty
061 */
062 public PolynomialFunction(double c[]) {
063 super();
064 if (c.length < 1) {
065 throw MathRuntimeException.createIllegalArgumentException("empty polynomials coefficients array");
066 }
067 int l = c.length;
068 while ((l > 1) && (c[l - 1] == 0)) {
069 --l;
070 }
071 this.coefficients = new double[l];
072 System.arraycopy(c, 0, this.coefficients, 0, l);
073 }
074
075 /**
076 * Compute the value of the function for the given argument.
077 * <p>
078 * The value returned is <br>
079 * <code>coefficients[n] * x^n + ... + coefficients[1] * x + coefficients[0]</code>
080 * </p>
081 *
082 * @param x the argument for which the function value should be computed
083 * @return the value of the polynomial at the given point
084 * @see UnivariateRealFunction#value(double)
085 */
086 public double value(double x) {
087 return evaluate(coefficients, x);
088 }
089
090
091 /**
092 * Returns the degree of the polynomial
093 *
094 * @return the degree of the polynomial
095 */
096 public int degree() {
097 return coefficients.length - 1;
098 }
099
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 }