// BigInt.js - Arbitrary size integer math package for JavaScript
// Copyright (C) 2000 Masanao Izumo <iz@onicos.co.jp>
// Version: 1.0.1
// Licence: GPL
//
// This program 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 2 of the License, or
// (at your option) any later version.
//
// This program 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.
//
//
// Interfaces:
// x = new BigInt("1234567890123456789012345678901234567890");
// y = new BigInt("0x123456789abcdef0123456789abcdef0");
// z = x.clone();
// z = bigint_uminus(x);
// z = bigint_plus(x, y);
// z = bigint_minus(x, y);
// z = bigint_mul(x, y);
// z = bigint_div(x, y);
// z = bigint_mod(x, y);
// cmp = bigint_cmp(x, y);	/* return -1, 0, or 1 */
// num = bigint_number(x);	/* convert normal number (may be floating) */
//

function _BigInt_toString() {
    return this.toStringBase(10);
}
function _BigInt_toStringBase(base) {
    var i, j, hbase;
    var t;
    var ds;
    var c;

    i = this.len;
    if (i == 0)
        return "0";
    if (i == 1 && !this.digits[0])
        return "0";

    switch (base) {
        default:
        case 10:
            j = Math.floor((2 * 8 * i * 241) / 800) + 2;
            hbase = 10000;
            break;

        case 16:
            j = Math.floor((2 * 8 * i) / 4) + 2;
            hbase = 0x10000;
            break;

        case 8:
            j = (2 * 8 * i) + 2;
            hbase = 010000;
            break;

        case 2:
            j = (2 * 8 * i) + 2;
            hbase = 020;
            break;
    }

    t = this.clone();
    ds = t.digits;
    s = "";

    while (i && j) {
        var k = i;
        var num = 0;

        while (k--) {
            num = (num << 16) + ds[k];
            if (num < 0) num += 4294967296;
            ds[k] = Math.floor(num / hbase);
            num %= hbase;
        }

        if (ds[i - 1] == 0)
            i--;
        k = 4;
        while (k--) {
            c = (num % base);
            s = "0123456789abcdef".charAt(c) + s;
            --j;
            num = Math.floor(num / base);
            if (i == 0 && num == 0) {
                break;
            }
        }
    }

    i = 0;
    while (i < s.length && s.charAt(i) == "0")
        i++;
    if (i)
        s = s.substring(i, s.length);
    if (!this.sign)
        s = "-" + s;
    return s;
}
function _BigInt_clone() {
    var x, i;

    x = new BigInt(this.len, this.sign);
    for (i = 0; i < this.len; i++)
        x.digits[i] = this.digits[i];
    return x;
}

function BigInt(len, sign) {
    var i, x, need_init;

    // Setup member functions.
    // Note: There is G.C. bug of function() in Netscape!
    //       Don't use anonymous function.
    this.toString = _BigInt_toString;
    this.toStringBase = _BigInt_toStringBase;
    this.clone = _BigInt_clone;

    if (BigInt.arguments.length == 0) {
        this.sign = true;
        this.len = len = 1;
        this.digits = new Array(1);
        need_init = true;
    } else if (BigInt.arguments.length == 1) {
        x = bigint_from_any(BigInt.arguments[0]);
        if (x == BigInt.arguments[0])
            x = x.clone();
        this.sign = x.sign;
        this.len = x.len;
        this.digits = x.digits;
        need_init = false;
    } else {
        this.sign = (sign ? true : false);
        this.len = len;
        this.digits = new Array(len);
        need_init = true;
    }

    if (need_init) {
        for (i = 0; i < len; i++)
            this.digits[i] = 0;
    }
}

function bigint_norm(x) {
    var len = x.len;
    var ds = x.digits;

    while (len-- && !ds[len])
        ;
    x.len = ++len;
    return x;
}

function bigint_from_int(n) {
    var sign, big, i;

    if (n < 0) {
        n = -n;
        sign = false;
    } else
        sign = true;
    n &= 0x7fffffff;

    if (n <= 0xffff) {
        big = new BigInt(1, 1);
        big.digits[0] = n;
    } else {
        big = new BigInt(2, 1);
        big.digits[0] = (n & 0xffff);
        big.digits[1] = ((n >> 16) & 0xffff);
    }
    return big;
}

function bigint_from_string(str, base) {
    var str_i;
    var sign = true;
    var c;
    var len;
    var z;
    var zds;
    var num;
    var i;
    var blen = 1;

    str += "@"; // Terminator;

    str_i = 0;
    // TODO: skip white spaces

    if (str.charAt(str_i) == "+") {
        str_i++;
    }
    else if (str.charAt(str_i) == "-") {
        str_i++;
        sign = false;
    }

    if (str.charAt(str_i) == "@")
        return null;

    if (!base) {
        if (str.charAt(str_i) == "0") {
            c = str.charAt(str_i + 1);
            if (c == "x" || c == "X") {
                base = 16;
            }
            else if (c == "b" || c == "B") {
                base = 2;
            }
            else {
                base = 8;
            }
        }
        else {
            base = 10;
        }
    }

    if (base == 8) {
        while (str.charAt(str_i) == "0")
            str_i++;
        len = 3 * (str.length - str_i);
    }
    else {			// base == 10, 2 or 16
        if (base == 16 && str.charAt(str_i) == '0' && (str.charAt(str_i + 1) == "x" || str.charAt(str_i + 1) == "X")) {
            str_i += 2;
        }
        if (base == 2 && str.charAt(str_i) == '0' && (str.charAt(str_i + 1) == "b" || str.charAt(str_i + 1) == "B")) {
            str_i += 2;
        }
        while (str.charAt(str_i) == "0")
            str_i++;
        if (str.charAt(str_i) == "@") str_i--;
        len = 4 * (str.length - str_i);
    }

    len = (len >> 4) + 1;
    z = new BigInt(len, sign);
    zds = z.digits;

    while (true) {
        c = str.charAt(str_i++);
        if (c == "@")
            break;
        switch (c) {
            case '0': c = 0; break;
            case '1': c = 1; break;
            case '2': c = 2; break;
            case '3': c = 3; break;
            case '4': c = 4; break;
            case '5': c = 5; break;
            case '6': c = 6; break;
            case '7': c = 7; break;
            case '8': c = 8; break;
            case '9': c = 9; break;
            case 'a': case 'A': c = 10; break;
            case 'b': case 'B': c = 11; break;
            case 'c': case 'C': c = 12; break;
            case 'd': case 'D': c = 13; break;
            case 'e': case 'E': c = 14; break;
            case 'f': case 'F': c = 15; break;
            default:
                c = base;
                break;
        }
        if (c >= base)
            break;

        i = 0;
        num = c;
        while (true) {
            while (i < blen) {
                num += zds[i] * base;
                zds[i++] = (num & 0xffff);
                num >>>= 16;
            }
            if (num) {
                blen++;
                continue;
            }
            break;
        }
    }
    return bigint_norm(z);
}

function bigint_from_any(x) {
    if (typeof (x) == "object") {
        if (x.constructor == BigInt)
            return x;
        return BigInt(1, 1);
    }

    if (typeof (x) == "string") {
        return bigint_from_string(x);
    }

    if (typeof (x) == "number") {
        var i, x1, x2, fpt, np;

        if (-2147483647 <= x && x <= 2147483647) {
            return bigint_from_int(x);
        }
        x = x + "";
        i = x.indexOf("e", 0);
        if (i == -1)
            return bigint_from_string(x);
        x1 = x.substr(0, i);
        x2 = x.substr(i + 2, x.length - (i + 2));

        fpt = x1.indexOf(".", 0);
        if (fpt != -1) {
            np = x1.length - (fpt + 1);
            x1 = x1.substr(0, fpt) + x1.substr(fpt + 1, np);
            x2 = parseInt(x2) - np;
        } else {
            x2 = parseInt(x2);
        }
        while (x2-- > 0) {
            x1 += "0";
        }
        return bigint_from_string(x1);
    }
    return BigInt(1, 1);
}

function bigint_uminus(x) {
    var z = x.clone();
    z.sign = !z.sign;
    return bigint_norm(z);
}

function bigint_add_internal(x, y, sign) {
    var z;
    var num;
    var i, len;

    sign = (sign == y.sign);
    if (x.sign != sign) {
        if (sign)
            return bigint_sub_internal(y, x);
        return bigint_sub_internal(x, y);
    }

    if (x.len > y.len) {
        len = x.len + 1;
        z = x; x = y; y = z;
    } else {
        len = y.len + 1;
    }
    z = new BigInt(len, sign);

    len = x.len;
    for (i = 0, num = 0; i < len; i++) {
        num += x.digits[i] + y.digits[i];
        z.digits[i] = (num & 0xffff);
        num >>>= 16;
    }
    len = y.len;
    while (num && i < len) {
        num += y.digits[i];
        z.digits[i++] = (num & 0xffff);
        num >>>= 16;
    }
    while (i < len) {
        z.digits[i] = y.digits[i];
        i++;
    }
    z.digits[i] = (num & 0xffff);
    return bigint_norm(z);
    //  return z;
}

function bigint_sub_internal(x, y) {
    var z = 0;
    var zds;
    var num;
    var i;

    i = x.len;
    // if x is larger than y, swap
    if (x.len < y.len) {
        z = x; x = y; y = z; // swap x y
    }
    else if (x.len == y.len) {
        while (i > 0) {
            i--;
            if (x.digits[i] > y.digits[i]) {
                break;
            }
            if (x.digits[i] < y.digits[i]) {
                z = x; x = y; y = z; // swap x y
                break;
            }
        }
    }

    z = new BigInt(x.len, (z == 0) ? 1 : 0);
    zds = z.digits;

    for (i = 0, num = 0; i < y.len; i++) {
        num += x.digits[i] - y.digits[i];
        zds[i] = (num & 0xffff);
        num >>>= 16;
    }
    while (num && i < x.len) {
        num += x.digits[i];
        zds[i++] = (num & 0xffff);
        num >>>= 16;
    }
    while (i < x.len) {
        zds[i] = x.digits[i];
        i++;
    }

    return bigint_norm(z);
}

function bigint_plus(x, y) {
    x = bigint_from_any(x);
    y = bigint_from_any(y);
    return bigint_add_internal(x, y, 1);
}

function bigint_minus(x, y) {
    x = bigint_from_any(x);
    y = bigint_from_any(y);
    return bigint_add_internal(x, y, 0);
}

function bigint_mul(x, y) {
    var i, j;
    var n = 0;
    var z;
    var zds, xds, yds;
    var dd, ee;
    var ylen;

    x = bigint_from_any(x);
    y = bigint_from_any(y);

    j = x.len + y.len + 1;
    z = new BigInt(j, x.sign == y.sign);

    xds = x.digits;
    yds = y.digits;
    zds = z.digits;
    ylen = y.len;
    while (j--)
        zds[j] = 0;
    for (i = 0; i < x.len; i++) {
        dd = xds[i];
        if (dd == 0)
            continue;
        n = 0;
        for (j = 0; j < ylen; j++) {
            ee = n + dd * yds[j];
            n = zds[i + j] + ee;
            if (ee)
                zds[i + j] = (n & 0xffff);
            n >>>= 16;
        }
        if (n) {
            zds[i + j] = n;
        }
    }

    return bigint_norm(z);
}

function bigint_divmod(x, y, modulo) {
    var nx = x.len;
    var ny = y.len;
    var i, j;
    var yy, z;
    var xds, yds, zds, tds;
    var t2;
    var num;
    var dd, q;
    var ee;
    var mod, div;

    yds = y.digits;
    if (ny == 0 && yds[0] == 0)
        return null; // Division by zero

    if (nx < ny || nx == ny && x.digits[nx - 1] < y.digits[ny - 1]) {
        if (modulo)
            return bigint_norm(x);
        return BigInt(1, 1);
    }

    xds = x.digits;
    if (ny == 1) {
        dd = yds[0];
        z = x.clone();
        zds = z.digits;
        t2 = 0;
        i = nx;
        while (i--) {
            t2 = t2 * 65536 + zds[i];
            zds[i] = (t2 / dd) & 0xffff;
            t2 %= dd;
        }
        z.sign = (x.sign == y.sign);
        if (modulo) {
            if (!x.sign)
                t2 = -t2;
            if (x.sign != y.sign) {
                t2 = t2 + yds[0] * (y.sign ? 1 : -1);
            }
            return bigint_from_int(t2);
        }
        return bigint_norm(z);
    }

    z = new BigInt(nx == ny ? nx + 2 : nx + 1,
		 x.sign == y.sign);
    zds = z.digits;
    if (nx == ny)
        zds[nx + 1] = 0;
    while (!yds[ny - 1])
        ny--;
    if ((dd = ((65536 / (yds[ny - 1] + 1)) & 0xffff)) != 1) {
        yy = y.clone();
        tds = yy.digits;
        j = 0;
        num = 0;
        while (j < ny) {
            num += yds[j] * dd;
            tds[j++] = num & 0xffff;
            num >>= 16;
        }
        yds = tds;
        j = 0;
        num = 0;
        while (j < nx) {
            num += xds[j] * dd;
            zds[j++] = num & 0xffff;
            num >>= 16;
        }
        zds[j] = num & 0xffff;
    }
    else {
        zds[nx] = 0;
        j = nx;
        while (j--) zds[j] = xds[j];
    }
    j = nx == ny ? nx + 1 : nx;
    do {
        if (zds[j] == yds[ny - 1]) q = 65535;
        else q = ((zds[j] * 65536 + zds[j - 1]) / yds[ny - 1]) & 0xffff;
        if (q) {
            i = 0; num = 0; t2 = 0;
            do {			// multiply and subtract
                t2 += yds[i] * q;
                ee = num - (t2 & 0xffff);
                num = zds[j - ny + i] + ee;
                if (ee) zds[j - ny + i] = num & 0xffff;
                num >>= 16;
                t2 >>>= 16;
            } while (++i < ny);
            num += zds[j - ny + i] - t2; // borrow from high digit; don't update
            while (num) {		// "add back" required
                i = 0; num = 0; q--;
                do {
                    ee = num + yds[i];
                    num = zds[j - ny + i] + ee;
                    if (ee) zds[j - ny + i] = num & 0xffff;
                    num >>= 16;
                } while (++i < ny);
                num--;
            }
        }
        zds[j] = q;
    } while (--j >= ny);

    if (modulo) {			// just normalize remainder
        mod = z.clone();
        if (dd) {
            zds = mod.digits;
            t2 = 0; i = ny;
            while (i--) {
                t2 = (t2 * 65536) + zds[i];
                zds[i] = (t2 / dd) & 0xffff;
                t2 %= dd;
            }
        }
        mod.len = ny;
        mod.sign = x.sign;
        if (x.sign != y.sign) {
            return bigint_add_internal(mod, y, 1);
        }
        return bigint_norm(mod);
    }

    div = z.clone();
    zds = div.digits;
    j = (nx == ny ? nx + 2 : nx + 1) - ny;
    for (i = 0; i < j; i++) zds[i] = zds[i + ny];
    div.len = i;
    return bigint_norm(div);
}

function bigint_div(x, y) {
    x = bigint_from_any(x);
    y = bigint_from_any(y);
    return bigint_divmod(x, y, 0);
}

function bigint_mod(x, y) {
    x = bigint_from_any(x);
    y = bigint_from_any(y);
    return bigint_divmod(x, y, 1);
}

function bigint_cmp(x, y) {
    var xlen;

    if (x == y)
        return 0; // Same object

    x = bigint_from_any(x);
    y = bigint_from_any(y);
    xlen = x.len;

    if (x.sign != y.sign) {
        if (x.sign)
            return 1;
        return -1;
    }

    if (xlen < y.len)
        return (x.sign) ? -1 : 1;
    if (xlen > y.len)
        return (x.sign) ? 1 : -1;

    while (xlen-- && (x.digits[xlen] == y.digits[xlen]))
        ;
    if (-1 == xlen)
        return 0;
    return (x.digits[xlen] > y.digits[xlen]) ?
    (x.sign ? 1 : -1) :
    (x.sign ? -1 : 1);
}

function bigint_number(x) {
    var d = 0.0;
    var i = x.len;
    var ds = x.digits;

    while (i--) {
        d = ds[i] + 65536.0 * d;
    }
    if (!x.sign) d = -d;
    return d;
}