View Javadoc

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 }