/**
*
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}
*
* @else
*
*
* n! |
* n < 2: | 1; (strict: 0! = 1! := 1)
*
*
* n > 1: | n * (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;
};