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