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 }