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