// 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;
}