[javascript]clear big integer implementation

bigint.js

// clear Big Integer implementation of JavaScript/ECMAScript5

// BigDecimal(10**n base): for string conversion
// - BigInt and BigDecimal are basically same.
var BigDecimal = this.BigDecimal = function (ints, sign) {
    var ctor = BigDecimal;
    ints = ints || [];
    sign = ctor.normalize(ints, sign || 1);
    return Object.freeze(Object.create(ctor.prototype, {
        ints: {value: Object.freeze(ints), enumerable: true},
        sign: {value: sign, writable: true, enumerable: true},
    }));
};

BigDecimal.UNIT = 10;
BigDecimal.LOG = 6;
BigDecimal.BASE = 0| Math.pow(BigDecimal.UNIT, BigDecimal.LOG);
// BigDecimal.BASE must be BigDecimal.UNIT ** BigDecimal.LOG and
//assert BigDecimal.BASE <= Math.pow(2, 26); // for element calc: e*e < 2^53

// normalize: it makes calcs clean
// - ints elems to everything positive
// - truncate upper 0 of ints
BigDecimal.normalize = function (ints, sign) {
    if (ints.length === 0) return 0;
    var i = 0;
    // ints get positives
    for (var i = 0, last = ints.length; i < last; i++) {
        if (ints[i] < 0) {
            ints[i + 1] = (ints[i + 1] || 0) - 1;
            ints[i] += this.BASE;
        }
    }
    // data invert if negative
    if (ints[ints.length - 1] === -1) {
        sign = sign * -1;
        ints.pop();
        ints[0] = this.BASE - ints[0];
        for (var i = 1; i < ints.length; i++) {
            ints[i] = this.BASE - 1 - ints[i];
        }
    }
    // remove extended 0
    while (ints[ints.length - 1] === 0) ints.pop();
    
    if (ints.length === 0) return 0;
    return sign;
};

BigDecimal.fromNumber = function (number) {
    number = 0| number;
    if (number === 0) return this.ZERO;
    var sign = 1;
    var ints = [];
    if (number < 0) {
        sign = -1;
        number = -number;
    }
    while (number > 0) {
        ints.push(number % this.BASE);
        number = 0| number / this.BASE;
    }
    return new this(ints, sign);
};

BigDecimal.fromString = function (text) {
    // BigInt.BASE should be 10^n
    var sign = 1;
    var ints = [];
    switch (text[0]) {
    case "-":
        sign = -1;
        text = text.substring(1);
        break;
    case "+":
        sign = 1;
        text = text.substring(1);
        break;
    }
    while (text.length > 0) {
        var lastIndex = text.length - this.LOG;
        var last = text.substring(lastIndex);
        text = text.substring(0, lastIndex);
        ints.push(1* last);
    }
    return new this(ints, sign);
};
BigDecimal.from = function (obj) {
    if (obj instanceof this) return obj;
    if (typeof obj === "number") return this.fromNumber(obj);
    if (typeof obj === "string") return this.fromString(obj);
    return this.ZERO;
};

BigDecimal.ZERO = new BigDecimal([], 0);
BigDecimal.ONE = new BigDecimal([1], 1);
BigDecimal.TWO = new BigDecimal([2], 1);
BigDecimal.MINUS = new BigDecimal([1], -1);
BigDecimal.prototype.toString = function () {
    // BigInt.BASE should be 10^n
    var pad = "";
    for (var i = 0; i < this.constructor.LOG; i++) pad += "0";
    
    var buf = "";
    for (var i = 0; i < this.ints.length - 1; i++) {
        var unit = (pad + this.ints[i]).slice(-this.constructor.LOG);
        buf = unit + buf;
    }
    buf = (this.ints[this.ints.length - 1] || "0") + buf;
    if (this.sign < 0) buf = "-" + buf;
    return buf;
};
BigDecimal.prototype.valueOf = function () {
    return this.toString() + "L";
};
BigDecimal.prototype.equals = function (other) {
    if (this.sign !== other.sign) return false;
    if (this.ints.length !== other.ints.length) return false;
    for (var i = 0; i < this.ints.length; i++) {
        if (this.ints[i] !== other.ints[i]) return false;
    }
    return true;
};
BigDecimal.prototype.lessThan = function (other) {
    if (this.sign < other.sign) return true;
    if (this.sign > other.sign) return false;
    if (this.ints.length < other.ints.length) return true;
    if (this.ints.length > other.ints.length) return false;
    for (var i = this.ints.length - 1; i >= 0; i--) {
        if (this.ints[i] < other.ints[i]) return true;
        if (this.ints[i] > other.ints[i]) return false;
    }
    return false; // equal
};

BigDecimal.prototype.negate = function () {
    return new this.constructor(this.ints.slice(), this.sign * -1);
};

BigDecimal.prototype.add = function (other) {
    if (other.sign === 0) return this;
    if (this.sign === 0) return other;
    if (this.sign !== other.sign) return this.sub(other.negate());
    
    var sign = this.sign;
    var tints = this.ints;
    var oints = other.ints;
    var length = oints.length > tints.length ? oints.length : tints.length;
    var ints = [];
    for (var i = 0; i < length; i++) {
        var sum = (tints[i] || 0) + (oints[i] || 0) + (ints[i] || 0);
        ints[i] = sum % this.constructor.BASE;
        ints[i + 1] = 0| sum / this.constructor.BASE;
    }
    return new this.constructor(ints, sign);
};

BigDecimal.prototype.sub = function (other) {
    if (other.sign === 0) return this;
    if (this.sign === 0) return other.negate();
    if (this.sign !== other.sign) return this.add(other.negate());
    
    var sign = this.sign;
    var tints = this.ints;
    var oints = other.ints;
    var length = oints.length > tints.length ? oints.length : tints.length;
    var ints = [];
    for (var i = 0; i < length; i++) {
        var sub = (tints[i] || 0) - (oints[i] || 0) + (ints[i] || 0);
        ints[i] = sub % this.constructor.BASE;
        ints[i + 1] = 0| sub / this.constructor.BASE;
    }
    return new this.constructor(ints, sign);
};

BigDecimal.prototype.mul = function (other) {
    var ints = [];
    var sign = this.sign * other.sign;
    for (var i = 0; i < this.ints.length; i++) {
        for (var j = 0; j < other.ints.length; j++) {
            var mul = this.ints[i] * other.ints[j] + (ints[i + j] || 0);
            ints[i + j] = mul % this.constructor.BASE;
            ints[i + j + 1] = 
                (0| mul / this.constructor.BASE) + (ints[i + j + 1] || 0);
        }
    }
    return new this.constructor(ints, sign);
};

BigDecimal.DivRem = function (quot, rem) {
    return Object.freeze(Object.create(BigDecimal.DivRem.prototype, {
        quot: {value: quot, enumerable: true},
        rem: {value: rem, enumerable: true},
    }));
};
BigDecimal.DivRem.prototype.toString = function () {
    return "{quot: " + this.quot.toString() + 
        ", rem: " + this.rem.toString() + "}";
};
BigDecimal.prototype.divrem = function (other) {
    if (other.sign === 0) return null; // zero div
    if (this.sign === 0) return new this.constructor.DivRem(
        this.constructor.ZERO, this.constructor.ZERO);
    
    var quotSign = this.sign * other.sign;
    var remSign = this.sign;
    // calc as positives
    var divider = other.sign < 0 ? other.negate() : other;
    var rem = this.sign < 0 ? this.negate() : this;
    var quot = this.constructor.ZERO;
    
    while (!rem.lessThan(divider)) {
        var base = divider;
        var pow2 = this.constructor.ONE;
        while (true) {
            var doubled = base.mul(this.constructor.TWO);
            if (rem.lessThan(doubled)) break;
            base = doubled;
            pow2 = pow2.mul(this.constructor.TWO);
        }
        rem = rem.sub(base);
        quot = quot.add(pow2);
    }
    return new this.constructor.DivRem(
        new this.constructor(quot.ints.slice(), quotSign), 
        new this.constructor(rem.ints.slice(), remSign));
};

BigDecimal.prototype.pow = function (other) {
    if (other.sign < 0) return null; // not supported
    if (other.sign === 0) return this.constructor.ONE;
    var ret = this.constructor.ONE;
    var pow = this;
    var exp = other;
    
    while (!exp.lessThan(this.constructor.ONE)) {
        var divrem = exp.divrem(this.constructor.TWO);
        if (divrem.rem.equals(this.constructor.ONE)) {
            ret = ret.mul(pow);
        }
        pow = pow.mul(pow);
        exp = divrem.quot;
    }
    return ret;
};

BigDecimal.prototype.mod = function (other) {
    var rem = this.divrem(other).rem;
    return rem.sign !== other.sign ? other.add(rem) : rem;
};
BigDecimal.prototype.mulmod = function (other, r) {
    return this.mod(r).mul(other.mod(r)).mod(r);
};
BigDecimal.prototype.powmod = function (other, r) {
    if (other.sign < 0) return null; // not supported
    if (other.sign === 0) return this.constructor.ONE;
    var ret = this.constructor.ONE;
    var pow = this.mod(r);
    var exp = other;
    
    while (!exp.lessThan(this.constructor.ONE)) {
        var divrem = exp.divrem(this.constructor.TWO);
        if (divrem.rem.equals(this.constructor.ONE)) {
            ret = ret.mulmod(pow, r);
        }
        pow = pow.mulmod(pow, r);
        exp = divrem.quot;
    }
    return ret;
};


// BigInt: 2**n base for calc
// Difference is String conversion: String <=> BigDecimal <=> BigInt
var BigInt = this.BigInt = function (ints, sign) {
    var ctor = BigInt;
    ints = ints || [];
    sign = ctor.normalize(ints, sign || 1);
    // max 10*9 - 1 int array (the lowest as the first) and negative sign
    return Object.freeze(Object.create(ctor.prototype, {
        ints: {value: Object.freeze(ints), enumerable: true},
        sign: {value: sign, writable: true, enumerable: true},
    }));
};
BigInt.prototype = Object.create(BigDecimal.prototype, {
    constructor: {value: BigInt},
});

BigInt.UNIT = 2;
BigInt.LOG = 26;
BigInt.BASE = 0| Math.pow(BigInt.UNIT, BigInt.LOG);
// BigInt.BASE must be BigInt.UNIT ** BigInt.LOG and
//assert BigInt.BASE <= Math.pow(2, 26); // for element calc: e*e < 2^53

BigInt.normalize = BigDecimal.normalize;
BigInt.fromNumber = BigDecimal.fromNumber;

BigInt.fromString = function (text) {
    var num = BigDecimal.fromString(text);
    var unit = this.fromNumber(BigDecimal.BASE);
    var base = this.ONE;
    var ret = this.ZERO;
    for (var i = 0; i < num.ints.length; i++) {
        var n = this.fromNumber(num.ints[i]);
        ret = ret.add(n.mul(base));
        base = base.mul(unit);
    }
    return new this(ret.ints.slice(), num.sign);
};

BigInt.from = BigDecimal.from;

BigInt.ZERO = new BigInt([], 0);
BigInt.ONE = new BigInt([1], 1);
BigInt.TWO = new BigInt([2], 1);
BigInt.MINUS = new BigInt([1], -1);

BigInt.prototype.toString = function () {
    var unit = BigDecimal.fromNumber(this.constructor.BASE);
    var ret = BigDecimal.ZERO;
    var base = BigDecimal.ONE;
    for (var i = 0; i < this.ints.length; i++) {
        var n = BigDecimal.fromNumber(this.ints[i]);
        ret = ret.add(n.mul(base));
        base = base.mul(unit);
    }
    return new BigDecimal(ret.ints.slice(), this.sign).toString();
};
BigInt.DivRem = BigDecimal.DivRem;


/*
// examples
console.log(BigInt.from(210).add(BigInt.from(291)).toString())
console.log(BigInt.from(210).sub(BigInt.from(291)).toString())
console.log(BigInt.from(999).mul(BigInt.from(999)).toString())
console.log(BigInt.from(99999).divrem(BigInt.from(771)).toString())
console.log(BigInt.from(3).pow(BigInt.from(16)).toString())
console.log(BigInt.from(10).mod(BigInt.from(-3)).toString())
console.log(BigInt.from(101).mulmod(BigInt.from(26), BigInt.from(3)).toString())

console.log(BigInt.from(101).powmod(BigInt.from(26), BigInt.from(3)).toString())

console.log(BigInt.from(2).pow(BigInt.from(129)).toString())
*/

bigint0.js

// clear Big Integer implementation of JavaScript/ECMAScript5

var BigInt = this.BigInt = function (ints, sign) {
    ints = ints || [];
    sign = BigInt.normalize(ints, sign || 1);
    // max 10*n - 1 int array (the lowest as the first) and negative sign
    return Object.freeze(Object.create(BigInt.prototype, {
        ints: {value: Object.freeze(ints), enumerable: true},
        sign: {value: sign, writable: true, enumerable: true},
    }));
};

BigInt.UNIT = 10;
//assert BigInt.UNIT === 10; // for easy decimal converter
BigInt.LOG = 1;
//BigInt.LOG = 6;
BigInt.BASE = 0| Math.pow(BigInt.UNIT, BigInt.LOG);
// BigInt.BASE must be BigInt.UNIT ** BigInt.LOG and
//assert BigInt.BASE <= Math.pow(2, 26); // for element calc: e*e < 2^53

// normalize: it makes calcs clean
// - ints elems to everything positive
// - truncate upper 0 of ints
BigInt.normalize = function (ints, sign) {
    if (ints.length === 0) return 0;
    var i = 0;
    // ints get positives
    for (var i = 0, last = ints.length; i < last; i++) {
        if (ints[i] < 0) {
            ints[i + 1] = (ints[i + 1] || 0) - 1;
            ints[i] += BigInt.BASE;
        }
    }
    // data invert if negative
    if (ints[ints.length - 1] === -1) {
        sign = sign * -1;
        ints.pop();
        ints[0] = BigInt.BASE - ints[0];
        for (var i = 1; i < ints.length; i++) {
            ints[i] = BigInt.BASE - 1 - ints[i];
        }
    }
    // remove extended 0
    while (ints[ints.length - 1] === 0) ints.pop();
    
    if (ints.length === 0) return 0;
    return sign;
};
BigInt.fromNumber = function (number) {
    number = 0| number;
    if (number === 0) return BigInt.ZERO;
    var sign = 1;
    var ints = [];
    if (number < 0) {
        sign = -1;
        number = -number;
    }
    while (number > 0) {
        ints.push(number % BigInt.BASE);
        number = 0| number / BigInt.BASE;
    }
    return new BigInt(ints, sign);
};

BigInt.fromString = function (text) {
    // BigInt.BASE should be 10^n
    var sign = 1;
    var ints = [];
    switch (text[0]) {
    case "-":
        sign = -1;
        text = text.substring(1);
        break;
    case "+":
        sign = 1;
        text = text.substring(1);
        break;
    }
    while (text.length > 0) {
        var lastIndex = text.length - BigInt.LOG;
        var last = text.substring(lastIndex);
        text = text.substring(0, lastIndex);
        ints.push(0|1* last);
    }
    return new BigInt(ints, sign);
};
BigInt.from = function (obj) {
    if (obj instanceof BigInt) return obj;
    if (typeof obj === "number") return BigInt.fromNumber(obj);
    if (typeof obj === "string") return BigInt.fromString(obj);
    return BigInt.ZERO;
};

BigInt.ZERO = new BigInt([], 0);
BigInt.ONE = new BigInt([1], 1);
BigInt.TWO = new BigInt([2], 1);
BigInt.MINUS = new BigInt([1], -1);

BigInt.prototype.toString = function () {
    // BigInt.BASE should be 10^n
    var pad = "";
    for (var i = 0; i < BigInt.LOG; i++) pad += "0";
    var buf = "";
    for (var i = 0; i < this.ints.length; i++) {
        var unit = (pad + this.ints[i]).slice(-BigInt.LOG);
        buf = unit + buf;
    }
    buf = (this.ints[this.ints.length - 1] || 0) + buf;
    if (this.sign < 0) buf = "-" + buf;
    return buf;
};

BigInt.prototype.equals = function (other) {
    if (this.sign !== other.sign) return false;
    if (this.ints.length !== other.ints.length) return false;
    for (var i = 0; i < this.ints.length; i++) {
        if (this.ints[i] !== other.ints[i]) return false;
    }
    return true;
};
BigInt.prototype.lessThan = function (other) {
    if (this.sign < other.sign) return true;
    if (this.sign > other.sign) return false;
    if (this.ints.length < other.ints.length) return true;
    if (this.ints.length > other.ints.length) return false;
    for (var i = this.ints.length - 1; i >= 0; i--) {
        if (this.ints[i] < other.ints[i]) return true;
        if (this.ints[i] > other.ints[i]) return false;
    }
    return false; // equal
};

BigInt.prototype.negate = function () {
    return new BigInt(this.ints.slice(), this.sign * -1);
};

BigInt.prototype.add = function (other) {
    if (other.sign === 0) return this;
    if (this.sign === 0) return other;
    if (this.sign !== other.sign) return this.sub(other.negate());
    
    var sign = this.sign;
    var tints = this.ints;
    var oints = other.ints;
    var length = oints.length > tints.length ? oints.length : tints.length;
    var ints = [];
    for (var i = 0; i < length; i++) {
        var sum = (tints[i] || 0) + (oints[i] || 0) + (ints[i] || 0);
        ints[i] = sum % BigInt.BASE;
        ints[i + 1] = 0| sum / BigInt.BASE;
    }
    return new BigInt(ints, sign);
};

BigInt.prototype.sub = function (other) {
    if (other.sign === 0) return this;
    if (this.sign === 0) return other.negate();
    if (this.sign !== other.sign) return this.add(other.negate());
    
    var sign = this.sign;
    var tints = this.ints;
    var oints = other.ints;
    var length = oints.length > tints.length ? oints.length : tints.length;
    var ints = [];
    for (var i = 0; i < length; i++) {
        var sub = (tints[i] || 0) - (oints[i] || 0) + (ints[i] || 0);
        ints[i] = sub % BigInt.BASE;
        ints[i + 1] = 0| sub / BigInt.BASE;
    }
    return new BigInt(ints, sign);
};

BigInt.prototype.mul = function (other) {
    var ints = [];
    var sign = this.sign * other.sign;
    for (var i = 0; i < this.ints.length; i++) {
        for (var j = 0; j < other.ints.length; j++) {
            var mul = this.ints[i] * other.ints[j] + (ints[i + j] || 0);
            ints[i + j] = mul % BigInt.BASE;
            ints[i + j + 1] = (0| mul / BigInt.BASE) + (ints[i + j + 1] || 0);
        }
    }
    return new BigInt(ints, sign);
};

BigInt.DivRem = function (quot, rem) {
    return Object.freeze(Object.create(BigInt.DivRem.prototype, {
        quot: {value: quot, enumerable: true},
        rem: {value: rem, enumerable: true},
    }));
};
BigInt.DivRem.prototype.toString = function () {
    return "{quot: " + this.quot.toString() + 
        ", rem: " + this.rem.toString() + "}";
};
BigInt.prototype.divrem = function (other) {
    if (other.sign === 0) return null; // zero div
    if (this.sign === 0) return new BigInt.DivRem(BigInt.ZERO, BigInt.ZERO);
    
    var quotSign = this.sign * other.sign;
    var remSign = this.sign;
    // calc as positives
    var divider = other.sign < 0 ? other.negate() : other;
    var rem = this.sign < 0 ? this.negate() : this;
    var quot = BigInt.ZERO;
    
    while (!rem.lessThan(divider)) {
        var base = divider;
        var pow2 = BigInt.ONE;
        while (true) {
            var doubled = base.mul(BigInt.TWO);
            if (rem.lessThan(doubled)) break;
            base = doubled;
            pow2 = pow2.mul(BigInt.TWO);
        }
        rem = rem.sub(base);
        quot = quot.add(pow2);
    }
    return new BigInt.DivRem(new BigInt(quot.ints.slice(), quotSign), 
                             new BigInt(rem.ints.slice(), remSign));
};

BigInt.prototype.pow = function (other) {
    if (other.sign < 0) return null; // not supported
    if (other.sign === 0) return BigInt.ONE; 
    var ret = BigInt.ONE;
    var pow = this;
    var exp = other;
    
    while (!exp.lessThan(BigInt.ONE)) {
        var divrem = exp.divrem(BigInt.TWO);
        if (divrem.rem.equals(BigInt.ONE)) {
            ret = ret.mul(pow);
        }
        pow = pow.mul(pow);
        exp = divrem.quot;
    }
    return ret;
};

BigInt.prototype.mod = function (other) {
    var rem = this.divrem(other).rem;
    return rem.sign !== other.sign ? other.add(rem) : rem;
};
BigInt.prototype.mulmod = function (other, r) {
    return this.mod(r).mul(other.mod(r)).mod(r);
};
BigInt.prototype.powmod = function (other, r) {
    if (other.sign < 0) return null; // not supported
    if (other.sign === 0) return BigInt.ONE;
    var ret = BigInt.ONE;
    var pow = this.mod(r);
    var exp = other;
    
    while (!exp.lessThan(BigInt.ONE)) {
        var divrem = exp.divrem(BigInt.TWO);
        if (divrem.rem.equals(BigInt.ONE)) {
            ret = ret.mulmod(pow, r);
        }
        pow = pow.mulmod(pow, r);
        exp = divrem.quot;
    }
    return ret;
};

/*
// examples
console.log(BigInt.from(210).add(BigInt.from(291)).toString())
console.log(BigInt.from(210).sub(BigInt.from(291)).toString())
console.log(BigInt.from(999).mul(BigInt.from(999)).toString())
console.log(BigInt.from(99999).divrem(BigInt.from(771)).toString())
console.log(BigInt.from(3).pow(BigInt.from(16)).toString())
console.log(BigInt.from(10).mod(BigInt.from(-3)).toString())
console.log(BigInt.from(101).mulmod(BigInt.from(26), BigInt.from(3)).toString())
console.log(BigInt.from(101).powmod(BigInt.from(26), BigInt.from(3)).toString())
*/