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 });