biginteger.java

来自「纯java操作系统jnode,安装简单和操作简单的个人使用的Java操作系统」· Java 代码 · 共 2,274 行 · 第 1/4 页

  {
    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 BigInteger.make((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(BigInteger.make(x), BigInteger.make(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(BigInteger.make(x), BigInteger.make(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 power for BigInteger exponents.
   * @param y exponent assumed to be non-negative. */
  /*private BigInteger pow(BigInteger y)
  {
    if (isOne())
      return this;
    if (isMinusOne())
      return y.isOdd () ? this : ONE;
    if (y.words == null && y.ival >= 0)
      return pow(y.ival);

    // Assume exponent is non-negative.
    if (isZero())
      return this;

    // Implemented by repeated squaring and multiplication.
    BigInteger pow2 = this;
    BigInteger r = null;
    for (;;)  // for (i = 0;  ; i++)
      {
        // pow2 == x**(2**i)
        // prod = x**(sum(j=0..i-1, (y>>j)&1))
        if (y.isOdd())
          r = r == null ? pow2 : times(r, pow2);  // r *= pow2
        y = BigInteger.shift(y, -1);
        if (y.isZero())
          break;
        // pow2 *= pow2;
        pow2 = times(pow2, pow2);
      }
    return r == null ? ONE : r;
  }*/

  /** 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;
	else
	  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)
  {
    // Storage for return values, plus one slot for a temp int (see below).
    int[] xy;

    if (b == 0)
      throw new ArithmeticException("not invertible");
    else if (b == 1)
      {
	// Success:  values are indeed invertible!
	// Bottom of the recursion reached; start unwinding.
        xy = new int[3];
	xy[0] = -prevDiv;
	xy[1] = 1;
	return xy;
      }

    xy = euclidInv(b, a % b, a / b);	// Recursion happens here.

    // xy[2] is just temp storage for intermediate results in the following
    // calculation.  This saves us a bit of space over having an int
    // allocated at every level of this recursive method.
    xy[2] = xy[0];
    xy[0] = xy[2] * -prevDiv + xy[1];
    xy[1] = xy[2];
    return xy;
  }

  private static final BigInteger[]
    euclidInv(BigInteger a, BigInteger b, BigInteger prevDiv)
  {
    // FIXME: This method could be more efficient memory-wise and should be
    // modified as such since it is recursive.

    // Storage for return values, plus one slot for a temp int (see below).
    BigInteger[] xy;

    if (b.isZero())
      throw new ArithmeticException("not invertible");
    else if (b.isOne())
      {
	// Success:  values are indeed invertible!
	// Bottom of the recursion reached; start unwinding.
        xy = new BigInteger[3];
	xy[0] = neg(prevDiv);
	xy[1] = ONE;
	return xy;
      }

    // 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 = new BigInteger[3];
	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();
        xy = euclidInv(b, rem, quot);
      }

    // xy[2] is just temp storage for intermediate results in the following
    // calculation.  This saves us a bit of space over having a BigInteger
    // allocated at every level of this recursive method.
    xy[2] = xy[0];
    xy[0] = add(xy[1], times(xy[2], prevDiv), -1);
    xy[1] = xy[2];
    return xy;
  }

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

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