biginteger.java

俄罗斯高人Mamaich的Pocket gcc编译器（运行在PocketPC上）的全部源代码。

      y_ext--;
    result.words[i] = (int) (carry + y_ext);
    result.ival = i+1;
    return result.canonicalize();
  }

  public BigInteger add(BigInteger val)
  {
    return add(this, val, 1);
  }

  public BigInteger subtract(BigInteger val)
  {
    return add(this, val, -1);
  }

  private static final BigInteger times(BigInteger x, int y)
  {
    if (y == 0)
      return ZERO;
    if (y == 1)
      return x;
    int[] xwords = x.words;
    int xlen = x.ival;
    if (xwords == null)
      return valueOf((long) xlen * (long) y);
    boolean negative;
    BigInteger result = BigInteger.alloc(xlen + 1);
    if (xwords[xlen - 1] < 0)
      {
	negative = true;
	negate(result.words, xwords, xlen);
	xwords = result.words;
      }
    else
      negative = false;
    if (y < 0)
      {
	negative = !negative;
	y = -y;
      }
    result.words[xlen] = MPN.mul_1(result.words, xwords, xlen, y);
    result.ival = xlen + 1;
    if (negative)
      result.setNegative();
    return result.canonicalize();
  }

  private static final BigInteger times(BigInteger x, BigInteger y)
  {
    if (y.words == null)
      return times(x, y.ival);
    if (x.words == null)
      return times(y, x.ival);
    boolean negative = false;
    int[] xwords;
    int[] ywords;
    int xlen = x.ival;
    int ylen = y.ival;
    if (x.isNegative())
      {
	negative = true;
	xwords = new int[xlen];
	negate(xwords, x.words, xlen);
      }
    else
      {
	negative = false;
	xwords = x.words;
      }
    if (y.isNegative())
      {
	negative = !negative;
	ywords = new int[ylen];
	negate(ywords, y.words, ylen);
      }
    else
      ywords = y.words;
    // Swap if x is shorter then y.
    if (xlen < ylen)
      {
	int[] twords = xwords;  xwords = ywords;  ywords = twords;
	int tlen = xlen;  xlen = ylen;  ylen = tlen;
      }
    BigInteger result = BigInteger.alloc(xlen+ylen);
    MPN.mul(result.words, xwords, xlen, ywords, ylen);
    result.ival = xlen+ylen;
    if (negative)
      result.setNegative();
    return result.canonicalize();
  }

  public BigInteger multiply(BigInteger y)
  {
    return times(this, y);
  }

  private static void divide(long x, long y,
			     BigInteger quotient, BigInteger remainder,
			     int rounding_mode)
  {
    boolean xNegative, yNegative;
    if (x < 0)
      {
	xNegative = true;
	if (x == Long.MIN_VALUE)
	  {
	    divide(valueOf(x), valueOf(y),
		   quotient, remainder, rounding_mode);
	    return;
	  }
	x = -x;
      }
    else
      xNegative = false;

    if (y < 0)
      {
	yNegative = true;
	if (y == Long.MIN_VALUE)
	  {
	    if (rounding_mode == TRUNCATE)
	      { // x != Long.Min_VALUE implies abs(x) < abs(y)
		if (quotient != null)
		  quotient.set(0);
		if (remainder != null)
		  remainder.set(x);
	      }
	    else
	      divide(valueOf(x), valueOf(y),
		      quotient, remainder, rounding_mode);
	    return;
	  }
	y = -y;
      }
    else
      yNegative = false;

    long q = x / y;
    long r = x % y;
    boolean qNegative = xNegative ^ yNegative;

    boolean add_one = false;
    if (r != 0)
      {
	switch (rounding_mode)
	  {
	  case TRUNCATE:
	    break;
	  case CEILING:
	  case FLOOR:
	    if (qNegative == (rounding_mode == FLOOR))
	      add_one = true;
	    break;
	  case ROUND:
	    add_one = r > ((y - (q & 1)) >> 1);
	    break;
	  }
      }
    if (quotient != null)
      {
	if (add_one)
	  q++;
	if (qNegative)
	  q = -q;
	quotient.set(q);
      }
    if (remainder != null)
      {
	// The remainder is by definition: X-Q*Y
	if (add_one)
	  {
	    // Subtract the remainder from Y.
	    r = y - r;
	    // In this case, abs(Q*Y) > abs(X).
	    // So sign(remainder) = -sign(X).
	    xNegative = ! xNegative;
	  }
	else
	  {
	    // If !add_one, then: abs(Q*Y) <= abs(X).
	    // So sign(remainder) = sign(X).
	  }
	if (xNegative)
	  r = -r;
	remainder.set(r);
      }
  }

  /** Divide two integers, yielding quotient and remainder.
   * @param x the numerator in the division
   * @param y the denominator in the division
   * @param quotient is set to the quotient of the result (iff quotient!=null)
   * @param remainder is set to the remainder of the result
   *  (iff remainder!=null)
   * @param rounding_mode one of FLOOR, CEILING, TRUNCATE, or ROUND.
   */
  private static void divide(BigInteger x, BigInteger y,
			     BigInteger quotient, BigInteger remainder,
			     int rounding_mode)
  {
    if ((x.words == null || x.ival <= 2)
	&& (y.words == null || y.ival <= 2))
      {
	long x_l = x.longValue();
	long y_l = y.longValue();
	if (x_l != Long.MIN_VALUE && y_l != Long.MIN_VALUE)
	  {
	    divide(x_l, y_l, quotient, remainder, rounding_mode);
	    return;
	  }
      }

    boolean xNegative = x.isNegative();
    boolean yNegative = y.isNegative();
    boolean qNegative = xNegative ^ yNegative;

    int ylen = y.words == null ? 1 : y.ival;
    int[] ywords = new int[ylen];
    y.getAbsolute(ywords);
    while (ylen > 1 && ywords[ylen - 1] == 0)  ylen--;

    int xlen = x.words == null ? 1 : x.ival;
    int[] xwords = new int[xlen+2];
    x.getAbsolute(xwords);
    while (xlen > 1 && xwords[xlen-1] == 0)  xlen--;

    int qlen, rlen;

    int cmpval = MPN.cmp(xwords, xlen, ywords, ylen);
    if (cmpval < 0)  // abs(x) < abs(y)
      { // quotient = 0;  remainder = num.
	int[] rwords = xwords;  xwords = ywords;  ywords = rwords;
	rlen = xlen;  qlen = 1;  xwords[0] = 0;
      }
    else if (cmpval == 0)  // abs(x) == abs(y)
      {
	xwords[0] = 1;  qlen = 1;  // quotient = 1
	ywords[0] = 0;  rlen = 1;  // remainder = 0;
      }
    else if (ylen == 1)
      {
	qlen = xlen;
	// Need to leave room for a word of leading zeros if dividing by 1
	// and the dividend has the high bit set.  It might be safe to
	// increment qlen in all cases, but it certainly is only necessary
	// in the following case.
	if (ywords[0] == 1 && xwords[xlen-1] < 0)
	  qlen++;
	rlen = 1;
	ywords[0] = MPN.divmod_1(xwords, xwords, xlen, ywords[0]);
      }
    else  // abs(x) > abs(y)
      {
	// Normalize the denominator, i.e. make its most significant bit set by
	// shifting it normalization_steps bits to the left.  Also shift the
	// numerator the same number of steps (to keep the quotient the same!).

	int nshift = MPN.count_leading_zeros(ywords[ylen - 1]);
	if (nshift != 0)
	  {
	    // Shift up the denominator setting the most significant bit of
	    // the most significant word.
	    MPN.lshift(ywords, 0, ywords, ylen, nshift);

	    // Shift up the numerator, possibly introducing a new most
	    // significant word.
	    int x_high = MPN.lshift(xwords, 0, xwords, xlen, nshift);
	    xwords[xlen++] = x_high;
	  }

	if (xlen == ylen)
	  xwords[xlen++] = 0;
	MPN.divide(xwords, xlen, ywords, ylen);
	rlen = ylen;
	MPN.rshift0 (ywords, xwords, 0, rlen, nshift);

	qlen = xlen + 1 - ylen;
	if (quotient != null)
	  {
	    for (int i = 0;  i < qlen;  i++)
	      xwords[i] = xwords[i+ylen];
	  }
      }

    if (ywords[rlen-1] < 0)
      {
        ywords[rlen] = 0;
        rlen++;
      }

    // Now the quotient is in xwords, and the remainder is in ywords.

    boolean add_one = false;
    if (rlen > 1 || ywords[0] != 0)
      { // Non-zero remainder i.e. in-exact quotient.
	switch (rounding_mode)
	  {
	  case TRUNCATE:
	    break;
	  case CEILING:
	  case FLOOR:
	    if (qNegative == (rounding_mode == FLOOR))
	      add_one = true;
	    break;
	  case ROUND:
	    // int cmp = compareTo(remainder<<1, abs(y));
	    BigInteger tmp = remainder == null ? new BigInteger() : remainder;
	    tmp.set(ywords, rlen);
	    tmp = shift(tmp, 1);
	    if (yNegative)
	      tmp.setNegative();
	    int cmp = compareTo(tmp, y);
	    // Now cmp == compareTo(sign(y)*(remainder<<1), y)
	    if (yNegative)
	      cmp = -cmp;
	    add_one = (cmp == 1) || (cmp == 0 && (xwords[0]&1) != 0);
	  }
      }
    if (quotient != null)
      {
	quotient.set(xwords, qlen);
	if (qNegative)
	  {
	    if (add_one)  // -(quotient + 1) == ~(quotient)
	      quotient.setInvert();
	    else
	      quotient.setNegative();
	  }
	else if (add_one)
	  quotient.setAdd(1);
      }
    if (remainder != null)
      {
	// The remainder is by definition: X-Q*Y
	remainder.set(ywords, rlen);
	if (add_one)
	  {
	    // Subtract the remainder from Y:
	    // abs(R) = abs(Y) - abs(orig_rem) = -(abs(orig_rem) - abs(Y)).
	    BigInteger tmp;
	    if (y.words == null)
	      {
		tmp = remainder;
		tmp.set(yNegative ? ywords[0] + y.ival : ywords[0] - y.ival);
	      }
	    else
	      tmp = BigInteger.add(remainder, y, yNegative ? 1 : -1);
	    // Now tmp <= 0.
	    // In this case, abs(Q) = 1 + floor(abs(X)/abs(Y)).
	    // Hence, abs(Q*Y) > abs(X).
	    // So sign(remainder) = -sign(X).
	    if (xNegative)
	      remainder.setNegative(tmp);
	    else
	      remainder.set(tmp);
	  }
	else
	  {
	    // If !add_one, then: abs(Q*Y) <= abs(X).
	    // So sign(remainder) = sign(X).
	    if (xNegative)
	      remainder.setNegative();
	  }
      }
  }

  public BigInteger divide(BigInteger val)
  {
    if (val.isZero())
      throw new ArithmeticException("divisor is zero");

    BigInteger quot = new BigInteger();
    divide(this, val, quot, null, TRUNCATE);
    return quot.canonicalize();
  }

  public BigInteger remainder(BigInteger val)
  {
    if (val.isZero())
      throw new ArithmeticException("divisor is zero");

    BigInteger rem = new BigInteger();
    divide(this, val, null, rem, TRUNCATE);
    return rem.canonicalize();
  }

  public BigInteger[] divideAndRemainder(BigInteger val)
  {
    if (val.isZero())
      throw new ArithmeticException("divisor is zero");

    BigInteger[] result = new BigInteger[2];
    result[0] = new BigInteger();
    result[1] = new BigInteger();
    divide(this, val, result[0], result[1], TRUNCATE);
    result[0].canonicalize();
    result[1].canonicalize();
    return result;
  }

  public BigInteger mod(BigInteger m)
  {
    if (m.isNegative() || m.isZero())
      throw new ArithmeticException("non-positive modulus");

    BigInteger rem = new BigInteger();
    divide(this, m, null, rem, FLOOR);
    return rem.canonicalize();
  }

  /** Calculate the integral power of a BigInteger.
   * @param exponent the exponent (must be non-negative)
   */
  public BigInteger pow(int exponent)
  {
    if (exponent <= 0)
      {
	if (exponent == 0)
	  return ONE;
	  throw new ArithmeticException("negative exponent");
      }
    if (isZero())
      return this;
    int plen = words == null ? 1 : ival;  // Length of pow2.
    int blen = ((bitLength() * exponent) >> 5) + 2 * plen;
    boolean negative = isNegative() && (exponent & 1) != 0;
    int[] pow2 = new int [blen];
    int[] rwords = new int [blen];
    int[] work = new int [blen];
    getAbsolute(pow2);	// pow2 = abs(this);
    int rlen = 1;
    rwords[0] = 1; // rwords = 1;
    for (;;)  // for (i = 0;  ; i++)
      {
	// pow2 == this**(2**i)
	// prod = this**(sum(j=0..i-1, (exponent>>j)&1))
	if ((exponent & 1) != 0)
	  { // r *= pow2
	    MPN.mul(work, pow2, plen, rwords, rlen);
	    int[] temp = work;  work = rwords;  rwords = temp;
	    rlen += plen;
	    while (rwords[rlen - 1] == 0)  rlen--;
	  }
	exponent >>= 1;
	if (exponent == 0)
	  break;
	// pow2 *= pow2;
	MPN.mul(work, pow2, plen, pow2, plen);
	int[] temp = work;  work = pow2;  pow2 = temp;  // swap to avoid a copy
	plen *= 2;
	while (pow2[plen - 1] == 0)  plen--;
      }
    if (rwords[rlen - 1] < 0)
      rlen++;
    if (negative)
      negate(rwords, rwords, rlen);
    return BigInteger.make(rwords, rlen);
  }

  private static final int[] euclidInv(int a, int b, int prevDiv)
  {
    if (b == 0)
      throw new ArithmeticException("not invertible");

    if (b == 1)
	// Success:  values are indeed invertible!
	// Bottom of the recursion reached; start unwinding.
	return new int[] { -prevDiv, 1 };

    int[] xy = euclidInv(b, a % b, a / b);	// Recursion happens here.
    a = xy[0]; // use our local copy of 'a' as a work var
    xy[0] = a * -prevDiv + xy[1];
    xy[1] = a;
    return xy;
  }

  private static final void euclidInv(BigInteger a, BigInteger b,
                                      BigInteger prevDiv, BigInteger[] xy)
  {
    if (b.isZero())
      throw new ArithmeticException("not invertible");

    if (b.isOne())
      {
	// Success:  values are indeed invertible!
	// Bottom of the recursion reached; start unwinding.
	xy[0] = neg(prevDiv);
        xy[1] = ONE;
	return;
      }

    // Recursion happens in the following conditional!

    // If a just contains an int, then use integer math for the rest.
    if (a.words == null)
      {
        int[] xyInt = euclidInv(b.ival, a.ival % b.ival, a.ival / b.ival);
	xy[0] = new BigInteger(xyInt[0]);
        xy[1] = new BigInteger(xyInt[1]);
      }
    else
      {
	BigInteger rem = new BigInteger();
	BigInteger quot = new BigInteger();
	divide(a, b, quot, rem, FLOOR);
        // quot and rem may not be in canonical form. ensure
        rem.canonicalize();
        quot.canonicalize();
	euclidInv(b, rem, quot, xy);
      }

    BigInteger t = xy[0];
    xy[0] = add(xy[1], times(t, prevDiv), -1);
    xy[1] = t;
  }

  public BigInteger modInverse(BigInteger y)
  {
    if (y.isNegative() || y.isZero())
      throw new ArithmeticException("non-positive modulo");

    // Degenerate cases.
    if (y.isOne())
      return ZERO;
    if (isOne())
      return ONE;

    // Use Euclid's algorithm as in gcd() but do this recursively
    // rather than in a loop so we can use the intermediate results as we
    // unwind from the recursion.
    // Used http://www.math.nmsu.edu/~crypto/EuclideanAlgo.html as reference.
    BigInteger result = new BigInteger();
    boolean swapped = false;

    if (y.words == null)
      {
	// The result is guaranteed to be less than the modulus, y (which is
	// an int), so simplify this by working with the int result of this
	// modulo y.  Also, if this is negative, make it positive via modulo
	// math.  Note that BigInteger.mod() must be used even if this is
	// already an int as the % operator would provide a negative result if
	// this is negative, BigInteger.mod() never returns negative values.
        int xval = (words != null || isNegative()) ? mod(y).ival : ival;
        int yval = y.ival;

	// Swap values so x > y.
	if (yval > xval)
	  {
	    int tmp = xval; xval = yval; yval = tmp;
	    swapped = true;
	  }
	// Normally, the result is in the 2nd element of the array, but
	// if originally x < y, then x and y were swapped and the result
	// is in the 1st element of the array.
	result.ival =
	  euclidInv(yval, xval % yval, xval / yval)[swapped ? 0 : 1];

	// Result can't be negative, so make it positive by adding the