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.exception.util.LocalizedFormats; 23 import org.apache.commons.math.exception.NoDataException; 24 import org.apache.commons.math.analysis.DifferentiableUnivariateRealFunction; 25 import org.apache.commons.math.analysis.UnivariateRealFunction; 26 import org.apache.commons.math.util.FastMath; 27 28 /** 29 * Immutable representation of a real polynomial function with real coefficients. 30 * <p> 31 * <a href="http://mathworld.wolfram.com/HornersMethod.html">Horner's Method</a> 32 * is used to evaluate the function.</p> 33 * 34 * @version $Revision: 1042376 $ $Date: 2010-12-05 16:54:55 +0100 (dim. 05 dc. 2010) $ 35 */ 36 public class PolynomialFunction implements DifferentiableUnivariateRealFunction, Serializable { 37 38 /** 39 * Serialization identifier 40 */ 41 private static final long serialVersionUID = -7726511984200295583L; 42 43 /** 44 * The coefficients of the polynomial, ordered by degree -- i.e., 45 * coefficients[0] is the constant term and coefficients[n] is the 46 * coefficient of x^n where n is the degree of the polynomial. 47 */ 48 private final double coefficients[]; 49 50 /** 51 * Construct a polynomial with the given coefficients. The first element 52 * of the coefficients array is the constant term. Higher degree 53 * coefficients follow in sequence. The degree of the resulting polynomial 54 * is the index of the last non-null element of the array, or 0 if all elements 55 * are null. 56 * <p> 57 * The constructor makes a copy of the input array and assigns the copy to 58 * the coefficients property.</p> 59 * 60 * @param c polynomial coefficients 61 * @throws NullPointerException if c is null 62 * @throws NoDataException if c is empty 63 */ 64 public PolynomialFunction(double c[]) { 65 super(); 66 int n = c.length; 67 if (n == 0) { 68 throw new NoDataException(LocalizedFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY); 69 } 70 while ((n > 1) && (c[n - 1] == 0)) { 71 --n; 72 } 73 this.coefficients = new double[n]; 74 System.arraycopy(c, 0, this.coefficients, 0, n); 75 } 76 77 /** 78 * Compute the value of the function for the given argument. 79 * <p> 80 * The value returned is <br> 81 * <code>coefficients[n] * x^n + ... + coefficients[1] * x + coefficients[0]</code> 82 * </p> 83 * 84 * @param x the argument for which the function value should be computed 85 * @return the value of the polynomial at the given point 86 * @see UnivariateRealFunction#value(double) 87 */ 88 public double value(double x) { 89 return evaluate(coefficients, x); 90 } 91 92 93 /** 94 * Returns the degree of the polynomial 95 * 96 * @return the degree of the polynomial 97 */ 98 public int degree() { 99 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 } 351