1 /* 2 Copyright 2008-2011 3 Matthias Ehmann, 4 Michael Gerhaeuser, 5 Carsten Miller, 6 Bianca Valentin, 7 Alfred Wassermann, 8 Peter Wilfahrt 9 10 This file is part of JSXGraph. 11 12 JSXGraph is free software: you can redistribute it and/or modify 13 it under the terms of the GNU Lesser General Public License as published by 14 the Free Software Foundation, either version 3 of the License, or 15 (at your option) any later version. 16 17 JSXGraph is distributed in the hope that it will be useful, 18 but WITHOUT ANY WARRANTY; without even the implied warranty of 19 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 20 GNU Lesser General Public License for more details. 21 22 You should have received a copy of the GNU Lesser General Public License 23 along with JSXGraph. If not, see <http://www.gnu.org/licenses/>. 24 */ 25 26 /** 27 * @fileoverview In this file the namespace Math.Poly is defined, which holds algorithms to create and 28 * manipulate polynomials. 29 */ 30 31 32 /** 33 * The JXG.Math.Poly namespace holds algorithms to create and manipulate polynomials. 34 * @namespace 35 */ 36 JXG.Math.Poly = {}; 37 38 /** 39 * Define a polynomial ring over R. 40 * @class 41 * @param {Array} variables List of indeterminates. 42 */ 43 JXG.Math.Poly.Ring = function (variables) { 44 /** 45 * A list of variables in this polynomial ring. 46 * @type Array 47 */ 48 this.vars = variables; 49 }; 50 51 JXG.extend(JXG.Math.Poly.Ring.prototype, /** @lends JXG.Math.Poly.Ring.prototype */ { 52 // nothing yet. 53 }); 54 55 56 /** 57 * Define a monomial over the polynomial ring <tt>ring</tt>. 58 * @class 59 * @param {JXG.Math.Poly.Ring} ring 60 * @param {Number} coefficient 61 * @param {Array} exponents An array of exponents, corresponding to ring 62 */ 63 JXG.Math.Poly.Monomial = function (ring, coefficient, exponents) { 64 var i; 65 66 if (!JXG.exists(ring)) { 67 throw new Error('JSXGraph error: In JXG.Math.Poly.monomial missing parameter \'ring\'.'); 68 } 69 70 if (!JXG.isArray(exponents)) { 71 exponents = []; 72 } 73 74 exponents = exponents.slice(0, ring.vars.length); 75 76 for (i = exponents.length; i < ring.vars.length; i++) { 77 exponents.push(0); 78 } 79 80 /** 81 * A polynomial ring. 82 * @type JXG.Math.Poly.Ring 83 */ 84 this.ring = ring; 85 86 /** 87 * The monomial's coefficient 88 * @type Number 89 */ 90 this.coefficient = coefficient || 0; 91 92 /** 93 * Exponent vector, the order depends on the order of the variables 94 * in the ring definition. 95 * @type Array 96 */ 97 this.exponents = JXG.deepCopy(exponents); 98 }; 99 100 JXG.extend(JXG.Math.Poly.Monomial.prototype, /** @lends JXG.Math.Poly.Monomial.prototype */ { 101 102 /** 103 * Creates a deep copy of the monomial. 104 * @returns {JXG.Math.Poly.Monomial} 105 */ 106 copy: function () { 107 return new JXG.Math.Poly.Monomial(this.ring, this.coefficient, this.exponents); 108 }, 109 110 /** 111 * Print the monomial. 112 * @returns {String} String representation of the monomial 113 */ 114 print: function () { 115 var s = [], 116 i; 117 118 for (i = 0; i < this.ring.vars.length; i++) { 119 s.push(this.ring.vars[i] + '^' + this.exponents[i]); 120 } 121 122 return this.coefficient + '*' + s.join('*'); 123 } 124 }); 125 126 127 /** 128 * A polynomial is a sum of monomials. 129 * @class 130 * @param {JXG.Math.Poly.Ring} ring A polynomial ring. 131 * @param {String} str TODO String representation of the polynomial, will be parsed. 132 */ 133 JXG.Math.Poly.Polynomial = function (ring, str) { 134 var parse = function () { 135 136 }, 137 mons; 138 139 if (!JXG.exists(ring)) { 140 throw new Error('JSXGraph error: In JXG.Math.Poly.polynomial missing parameter \'ring\'.'); 141 } 142 143 if (JXG.exists(str) && typeof str === 'string') { 144 mons = parse(str); 145 } else { 146 mons = []; 147 } 148 149 /** 150 * A polynomial ring. 151 * @type JXG.Math.Poly.Ring 152 */ 153 this.ring = ring; 154 155 /** 156 * List of monomials. 157 * @type Array 158 */ 159 this.monomials = mons; 160 }; 161 162 JXG.extend(JXG.Math.Poly.Polynomial.prototype, /** @lends JXG.Math.Poly.Polynomial.prototype */ { 163 /** 164 * Find a monomial with the given signature, i.e. exponent vector. 165 * @param {Array} sig An array of numbers 166 * @returns {Number} The index of the first monomial with the given signature, or -1 167 * if no monomial could be found. 168 */ 169 findSignature: function (sig) { 170 var i; 171 172 for (i = 0; i < this.monomials.length; i++) { 173 if (JXG.cmpArrays(this.monomials[i].exponents, sig)) { 174 return i; 175 } 176 } 177 178 return -1; 179 }, 180 181 /** 182 * Adds a monomial to the polynomial. Checks the existing monomials for the added 183 * monomial's signature and just adds the coefficient if one is found. 184 * @param {JXG.Math.Poly.Monomial} m 185 * @param {Number} factor Either <tt>1</tt> or <tt>-1</tt>. 186 */ 187 addSubMonomial: function (m, factor) { 188 var i; 189 190 i = this.findSignature(m.exponents); 191 if (i > -1) { 192 this.monomials[i].coefficient += factor*m.coefficient; 193 } else { 194 m.coefficient *= factor; 195 this.monomials.push(m); 196 } 197 }, 198 199 /** 200 * Adds another polynomial or monomial to this one and merges them by checking for the 201 * signature of each new monomial in the existing monomials. 202 * @param {JXG.Math.Poly.Polynomial|JXG.Math.Poly.Monomial} mp 203 */ 204 add: function (mp) { 205 var i; 206 207 if (JXG.exists(mp) && mp.ring === this.ring) { 208 if (JXG.isArray(mp.exponents)) { 209 // mp is a monomial 210 this.addSubMonomial(mp, 1); 211 } else { 212 // mp is a polynomial 213 for (i = 0; i < mp.monomials.length; i++) { 214 this.addSubMonomial(mp.monomials[i], 1); 215 } 216 } 217 } else { 218 throw new Error('JSXGraph error: In JXG.Math.Poly.polynomial.add either summand is undefined or rings don\'t match.'); 219 } 220 }, 221 222 /** 223 * Subtracts another polynomial or monomial from this one and merges them by checking for the 224 * signature of each new monomial in the existing monomials. 225 * @param {JXG.Math.Poly.Polynomial|JXG.Math.Poly.Monomial} mp 226 */ 227 sub: function (mp) { 228 var i; 229 230 if (JXG.exists(mp) && mp.ring === this.ring) { 231 if (JXG.isArray(mp.exponents)) { 232 // mp is a monomial 233 this.addSubMonomial(mp, -1); 234 } else { 235 // mp is a polynomial 236 for (i = 0; i < mp.monomials.length; i++) { 237 this.addSubMonomial(mp.monomials[i], -1); 238 } 239 } 240 } else { 241 throw new Error('JSXGraph error: In JXG.Math.Poly.polynomial.sub either summand is undefined or rings don\'t match.'); 242 } 243 }, 244 245 /** 246 * Creates a deep copy of the polynomial. 247 * @returns {JXG.Math.Poly.Polynomial} 248 */ 249 copy: function () { 250 var i, p; 251 252 p = new JXG.Math.Poly.Polynomial(this.ring); 253 254 for (i = 0; i < this.monomials.length; i++) { 255 p.monomials.push(this.monomials[i].copy()); 256 } 257 return p; 258 }, 259 260 /** 261 * Prints the polynomial. 262 * @returns {String} A string representation of the polynomial. 263 */ 264 print: function () { 265 var s = [], 266 i; 267 268 for (i = 0; i < this.monomials.length; i++) { 269 s.push('(' + this.monomials[i].print() + ')'); 270 } 271 272 return s.join('+'); 273 } 274 });