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    }