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