/** * PointedEars' JSX: Math Library: Integer arithmetics * @requires object.js * @requires types.js * * @section Copyright & Disclaimer * * @author * (C) 2000-2011 Thomas Lahn <math.js@PointedEars.de> * * @partof PointedEars' JavaScript Extensions (JSX) * * JSX is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * JSX is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with JSX. If not, see . */ if (typeof jsx == "undefined") { var jsx = {}; } if (typeof jsx.math == "undefined") { jsx.math = {}; } jsx.math.integer = { /** * Returns the greatest common divisor (GCD) of two integers * a and b, implementing (the optimized form of) the * Euclidean algorithm (also called Euclid's algorithm). The * GCD of two integer arguments is the largest positive integer * that both arguments are integer multiples of, i.e. by which * either argument can be divided without remainder. Since * integers are required, the floor of a and b will * be used for computation. * * @memberOf jsx.math.integer * @param a : number * @param b : number * @return type number * The GCD of a and b; * NaN if an argument is not a number. * @see Math#floor(number) */ gcd: function (a, b) { if (isNaN(a) || isNaN(b)) { return Number.NaN; } a = Math.floor(a); b = Math.floor(b); var c; while (b != 0) { c = a % b; a = b; b = c; } return Math.abs(a); } }; if (jsx.options.augmentBuiltins) { jsx.object.extend(Math, { /** * @memberOf Math */ gcd: jsx.math.integer.gcd }); } /** * Returns the greatest common divisor (GCD) of two or more * integers, implementing (the optimized form of) the Euclidean * algorithm (also called Euclid's algorithm). The GCD of * integer arguments is the largest positive integer that all * arguments are integer multiples of, i.e. by which either * argument can be divided without remainder. Since integers * are required, the floor of the arguments will be used for * computation. * * @return number * The GCD of the arguments; * NaN if one or more arguments are not a number. * @see Math#floor(number) */ Math.gcdN = function(a, b) { /* Currently supports only 2 integers */ return Math.gcd(a, b); }; /** * Returns the least common multiple (LCM) of two integers * a and b. The LCM of two integer arguments is * the smallest positive integer that is a multiple of the * arguments. If there is no such positive integer, i.e., * if either argument is zero, then lcm(a, b) * is defined to be zero. Since integers are required, the * floor of a and b will be used for computation. * * @param a : number * @param b : number * @return number * The LCM of a and b; * 0 if an argument is 0; * NaN if an argument is not a number. * @see Math#floor(number) * @see Math#gcd(number, number) */ Math.lcm = function(a, b) { if (isNaN(a) || isNaN(b)) { return Number.NaN; } if (!a || !b) { return 0; } a = Math.floor(a); b = Math.floor(b); return ((a * b) / Math.gcd(a, b)); }; /** * @author (c) 2000 Thomas Lahn <math.js@PointedEars.de> * @param n : number * If n is not an integer, Math.floor(n) is used. * @return number * The factorial of n (n!) * which is (for practical reasons) implemented here as follows: * @ifdef{MathML2} * * * * * * n * * * * 1 * n 2 * * * * n * * * * * n 1 * * * * n 1 * * * * * @else * * * * 1; (strict: 0! = 1! := 1) * * * n * (n - 1)! * *
n!n < 2:
n > 1:
* @endif * * Unlike common recursive implementations, the algorithm is * implemented iterative here, saving stack space and thus * allowing larger factorials to be computed. * * @throws Math#OverflowError */ Math.fac = function(n) { if (n % 1 != 0) { n = Math.floor(n); } var result = 1; for (var i = 2; i <= n; result *= i++) { if (result == Number.POSITIVE_INFINITY) { result = 0; // [Exception] <- [MathErrorException] <- [OverflowException] } jsx.throwThis(new Math.OverflowError("fac")); break; } } return result; }; /** * @author (c) 2000 Thomas Lahn <math.js@PointedEars.de> * @param nBase : number * @param iExponent : number * @return number * nBase to the power of iExponent */ Math.powInt = function(nBase, iExponent) { var i = iExponent; var result = 1.0; while (i > 0) { if (i % 2) { result *= nBase; } i = Math.floor(i / 2); nBase *= nBase; } return result; }; /** * Computes the base nBase powered * by the exponent nExponent * (nBase^nExponent). * Uses the Math.exp() and Math.log() methods to * workaround the bug in Math.pow() that positive * roots of certain negative values, like root(-9, * 1/3) cannot be computed (results in NaN there) * but should be. * * @author * (c) 2000-2004 Thomas Lahn <math.js@PointedEars.de> * @param nBase : number * @param nExponent : number * @throws Math#InvalidArgumentError * @return type number * NaN if computation result lies beyond real numbers, * the result (as double-precision floating-point number) * otherwise. */ Math.power = function(nBase, nExponent) { var result; if (nBase != 0) { /* e^(Exponent * ln(|Base|)) */ result = Math.exp(nExponent * Math.log(Math.abs(nBase))); if (nBase < 0) { if (nExponent % 1 == 0) { if (Math.floor(nExponent) % 2) { result = -result; } } else { result = Number.NaN; /* [Exception]<- [Math.MathError] <- [Math.InvalidArgumentError] */ jsx.throwThis(new Math.InvalidArgumentError( "power(" + nBase + ", " + nExponent + ")")); } } else if (nBase == 0 && nExponent == 0) { result = 0; jsx.throwThis(new Math.InvalidArgumentError( "power(" + nBase + ", " + nExponent + ")")); } } return result; }; /** * @return type number * The logarithm of x to the base nBase. * * @author (c) 2000 Thomas Lahn <math.js@PointedEars.de> * @param x : number * @param nBase : number */ Math.logN = function(x, nBase) { return Math.log(x) / Math.log(nBase); }; /** * @author * (c) 2000 Thomas Lahn <math.js@PointedEars.de> * * @param x : number * @return type number * The logarithm digitalis (ld) of x * (the logarithm of x to the base 2). */ Math.log2 = function(x) { return Math.logN(x, 2); }; /** * Computes the decimal logarithm (lg) of * x (the log. of x to the base 10). * * @author (c) 2000 Thomas Lahn <math.js@PointedEars.de> * @param x : number * @return number * The logarithm of x to the base 10 */ Math.log10 = function(x) { return Math.logN(x, 10); }; /** * @author * (c) 2000 Thomas Lahn <math.js@PointedEars.de> * @param x : number * @return type number * the reciprocal of x (1/x). */ Math.rec = function(x) { return (1 / x); }; /** * Finds prime numbers within a range * * @param {int} upperBounds * The upper bounds of the half-open interval [2, ceil(upperBounds)), * that is, the smallest integer that should not be considered * in the search. * @return {Object} * An object whose property names are the primes within range. * Use {@link Object#keys()} to get an {@link Array} of * string values; use * {@link Array.prototype#map} to get an Array * of {@link Number} values. * NOTE: As of ECMAScript Edition 5.1, an Array * is limited to 2^32-1 elements. Use {@link jsx.array.BigArray} * to process this Object efficiently. */ Math.primes = function (upperBounds) { var not_prime = Object.create(null); var prime = Object.create(null); var i = 2; var upperLimit = Math.sqrt(upperBounds); while (i < upperLimit) { prime[i] = true; for (var mult = i * i; mult < upperBounds; mult += i) { not_prime[mult] = true; } while (not_prime[++i]); } for (; i < upperBounds; ++i) { if (!not_prime[i]) { prime[i] = true; } delete not_prime[i]; } return prime; };