      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      * @namespace
     55      */
     56     Mat.Poly = {};
     57
     58     /**
     59      * Define a polynomial ring over R.
     60      * @class
     61      * @name JXG.Math.Poly.Ring
     62      * @param {Array} variables List of indeterminates.
     63      */
     64     Mat.Poly.Ring = function (variables) {
     65         /**
     66          * A list of variables in this polynomial ring.
     67          * @type Array
     68          */
     69         this.vars = variables;
     70     };
     71
     72     JXG.extend(Mat.Poly.Ring.prototype, /** @lends JXG.Math.Poly.Ring.prototype */ {
     73         // nothing yet.
     74     });
     75
     76
     77     /**
     78      * Define a monomial over the polynomial ring <tt>ring</tt>.
     79      * @class
     80      * @name JXG.Math.Poly.Monomial
     81      * @param {JXG.Math.Poly.Ring} ring
     82      * @param {Number} coefficient
     83      * @param {Array} exponents An array of exponents, corresponding to ring
     84      */
     85     Mat.Poly.Monomial = function (ring, coefficient, exponents) {
     86         var i;
     87
     88         if (!Type.exists(ring)) {
     89             throw new Error('JSXGraph error: In JXG.Math.Poly.monomial missing parameter \'ring\'.');
     90         }
     91
     92         if (!Type.isArray(exponents)) {
     93             exponents = [];
     94         }
     95
     96         exponents = exponents.slice(0, ring.vars.length);
     97
     98         for (i = exponents.length; i < ring.vars.length; i++) {
     99             exponents.push(0);
    100         }
    101
    102         /**
    103          * A polynomial ring.
    104          * @type JXG.Math.Poly.Ring
    105          */
    106         this.ring = ring;
    107
    108         /**
    109          * The monomial's coefficient
    110          * @type Number
    111          */
    112         this.coefficient = coefficient || 0;
    113
    114         /**
    115          * Exponent vector, the order depends on the order of the variables
    116          * in the ring definition.
    117          * @type Array
    118          */
    119         this.exponents = Type.deepCopy(exponents);
    120     };
    121
    122     JXG.extend(Mat.Poly.Monomial.prototype, /** @lends JXG.Math.Poly.Monomial.prototype */ {
    123
    124         /**
    125          * Creates a deep copy of the monomial.
    126          * @returns {JXG.Math.Poly.Monomial}
    127          */
    128         copy: function () {
    129             return new Mat.Poly.Monomial(this.ring, this.coefficient, this.exponents);
    130         },
    131
    132         /**
    133          * Print the monomial.
    134          * @returns {String} String representation of the monomial
    135          */
    136         print: function () {
    137             var s = [],
    138                 i;
    139
    140             for (i = 0; i < this.ring.vars.length; i++) {
    141                 s.push(this.ring.vars[i] + '^' + this.exponents[i]);
    142             }
    143
    144             return this.coefficient + '*' + s.join('*');
    145         }
    146     });
    147
    148
    149     /**
    150      * A polynomial is a sum of monomials.
    151      * @class
    152      * @name JXG.Math.Poly.Polynomial
    153      * @param {JXG.Math.Poly.Ring} ring A polynomial ring.
    154      * @param {String} str TODO String representation of the polynomial, will be parsed.
    155      */
    156     Mat.Poly.Polynomial = function (ring, str) {
    157         var parse = function () {
    158
    159             },
    160             mons;
    161
    162         if (!Type.exists(ring)) {
    163             throw new Error('JSXGraph error: In JXG.Math.Poly.polynomial missing parameter \'ring\'.');
    164         }
    165
    166         if (Type.exists(str) && typeof str === 'string') {
    167             mons = parse(str);
    168         } else {
    169             mons = [];
    170         }
    171
    172         /**
    173          * A polynomial ring.
    174          * @type JXG.Math.Poly.Ring
    175          */
    176         this.ring = ring;
    177
    178         /**
    179          * List of monomials.
    180          * @type Array
    181          */
    182         this.monomials = mons;
    183     };
    184
    185     JXG.extend(Mat.Poly.Polynomial.prototype, /** @lends JXG.Math.Poly.Polynomial.prototype */ {
    186         /**
    187          * Find a monomial with the given signature, i.e. exponent vector.
    188          * @param {Array} sig An array of numbers
    189          * @returns {Number} The index of the first monomial with the given signature, or -1
    190          * if no monomial could be found.
    191          */
    192         findSignature: function (sig) {
    193             var i;
    194
    195             for (i = 0; i < this.monomials.length; i++) {
    196                 if (Type.cmpArrays(this.monomials[i].exponents, sig)) {
    197                     return i;
    198                 }
    199             }
    200
    201             return -1;
    202         },
    203
    204         /**
    205          * Adds a monomial to the polynomial. Checks the existing monomials for the added
    206          * monomial's signature and just adds the coefficient if one is found.
    207          * @param {JXG.Math.Poly.Monomial} m
    208          * @param {Number} factor Either <tt>1</tt> or <tt>-1</tt>.
    209          */
    210         addSubMonomial: function (m, factor) {
    211             var i;
    212
    213             i = this.findSignature(m.exponents);
    214             if (i > -1) {
    215                 this.monomials[i].coefficient += factor * m.coefficient;
    216             } else {
    217                 m.coefficient *= factor;
    218                 this.monomials.push(m);
    219             }
    220         },
    221
    222         /**
    223          * Adds another polynomial or monomial to 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         add: function (mp) {
    228             var i;
    229
    230             if (Type.exists(mp) && mp.ring === this.ring) {
    231                 if (Type.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.add either summand is undefined or rings don\'t match.');
    242             }
    243         },
    244
    245         /**
    246          * Subtracts another polynomial or monomial from this one and merges them by checking for the
    247          * signature of each new monomial in the existing monomials.
    248          * @param {JXG.Math.Poly.Polynomial|JXG.Math.Poly.Monomial} mp
    249          */
    250         sub: function (mp) {
    251             var i;
    252
    253             if (Type.exists(mp) && mp.ring === this.ring) {
    254                 if (Type.isArray(mp.exponents)) {
    255                     // mp is a monomial
    256                     this.addSubMonomial(mp, -1);
    257                 } else {
    258                     // mp is a polynomial
    259                     for (i = 0; i < mp.monomials.length; i++) {
    260                         this.addSubMonomial(mp.monomials[i], -1);
    261                     }
    262                 }
    263             } else {
    264                 throw new Error('JSXGraph error: In JXG.Math.Poly.polynomial.sub either summand is undefined or rings don\'t match.');
    265             }
    266         },
    267
    268         /**
    269          * Creates a deep copy of the polynomial.
    270          * @returns {JXG.Math.Poly.Polynomial}
    271          */
    272         copy: function () {
    273             var i, p;
    274
    275             p = new Mat.Poly.Polynomial(this.ring);
    276
    277             for (i = 0; i < this.monomials.length; i++) {
    278                 p.monomials.push(this.monomials[i].copy());
    279             }
    280             return p;
    281         },
    282
    283         /**
    284          * Prints the polynomial.
    285          * @returns {String} A string representation of the polynomial.
    286          */
    287         print: function () {
    288             var s = [],
    289                 i;
    290
    291             for (i = 0; i < this.monomials.length; i++) {
    292                 s.push('(' + this.monomials[i].print() + ')');
    293             }
    294
    295             return s.join('+');
    296         }
    297     });
    298
    299     return Mat.Poly;
    300 });
    301