The script uses BigInts and a bit array to run the sieve of Eratosthenes with very large numbers. The bit array is actually a Uint8Array with methods to access individual bits:
function newBitArray(minimumBitLength) {
var len = Math.ceil(minimumBitLength/8);
var bitArray = new Uint8Array(len);
bitArray.bitLength = len*8;
bitArray.getPosition = function(bit) {
return [Math.floor(bit/8), bit % 8]; // [Uint8Array element number, bit number in the element]
}
bitArray.getBit = function(bit) {
var p = this.getPosition(bit);
return (this[p[0]] & 2**p[1]) >> p[1];
}
bitArray.setBit = function(bit) {
var p = this.getPosition(bit);
this[p[0]] |= 2**p[1];
}
bitArray.unsetBit = function(bit) {
var p = this.getPosition(bit);
this[p[0]] &= 255 - 2**p[1];
}
bitArray.flipBit = function(bit) {
var p = this.getPosition(bit);
this[p[0]] ^= 2**p[1];
}
bitArray.testBit = function(bit) {
if ((bit < 0) || (bit > this.bitLength - 1))
throw RangeError("bit number (" + bit.toString() + ") out of range (0-" + (this.bitLength - 1).toString() + ")");
}
return bitArray;
}
var a = newBitArray(1000000000); // 125 MB of memory; an array of 1,000,000,000 numbers would be 8 GB
a.setBit(27); // 1
a.unsetBit(27); // 0
a.flipBit(27); // 1
console.log(a.getBit(27));
Square root of a BigInt:
function BigSqrt(b) { // returns the ⌈square root⌉ of b (as a BigInt)
if (b < 0)
return NaN;
if (b <= Number.MAX_SAFE_INTEGER)
return BigInt(Math.ceil(Math.sqrt(Number(b)))); // duh
var bts = b.toString();
var x0 = BigInt(bts.substr(0, Math.ceil(bts.length/2))); // first approximation
var x1 = f(x0);
var cnt = 0;
while (((x1 < x0) || (x1 > x0 + 1n)) && (cnt < 100)) { // 1,000,000 digits takes about 20 iterations
x0 = x1;
x1 = f(x0);
cnt++;
}
if (x1*x1 < b) // it's the truncated square root
x1++;
return x1;
function f(x0) {
return (x0 + b/x0)/2n; // Newton's method
}
}
Natural logarithm of a BigInt:
function BigLog(b) { // returns the natural logarithm of b (as a Number, to floating point precision)
if (b <= 0)
return NaN;
if (b <= Number.MAX_SAFE_INTEGER)
return Math.log(Number(b));
var bts = b.toString();
return (bts.length + Math.log10(parseFloat("0." + bts)))/Math.LOG10E;
}