biginteger.java

《移动Agent技术》一书的所有章节源代码。

	if (val.signum == 0)
	    throw new ArithmeticException("BigInteger divide by zero");
	else if (this.signum == 0)
	    return ZERO;
	else
	    return new BigInteger(plumbDivide(magnitude, val.magnitude),
				  signum * val.signum);
    }

    /**
     * Returns a BigInteger whose value is (this % val).  Throws an
     * ArithmeticException if val == 0.
     */
    public BigInteger remainder(BigInteger val) throws ArithmeticException {

	if (val.signum == 0)
	    throw new ArithmeticException("BigInteger divide by zero");
	else if (this.signum == 0)
	    return ZERO;
	else if (this.magnitude.length < val.magnitude.length)
	    return this; /*** WORKAROUND FOR BUG IN R1.1 OF PLUMB'S PKG ***/
	else
	    return new BigInteger(plumbRemainder(magnitude,val.magnitude),
				  signum);
    }

    /**
     * Returns an array of two BigIntegers. The first ([0]) element of
     * the return value is the quotient (this / val), and the second ([1])
     * element is the remainder (this % val).  Throws an ArithmeticException
     * if val == 0.
     */
    public BigInteger[] divideAndRemainder(BigInteger val)
    throws ArithmeticException {
	BigInteger result[] = new BigInteger[2];

	if (val.signum == 0) {
	    throw new ArithmeticException("BigInteger divide by zero");
	} else if (this.signum == 0) {
	    result[0] = result[1] = ZERO;
	} else if (this.magnitude.length < val.magnitude.length) {
	    /*** WORKAROUND FOR A BUG IN R1.1 OF PLUMB'S PACKAGE ***/
	    result[0] = ZERO;
	    result[1] = this;
	} else {
	    byte resultMagnitude[][] =
		plumbDivideAndRemainder(magnitude, val.magnitude);
	    result[0] = new BigInteger(resultMagnitude[0], signum*val.signum);
	    result[1] = new BigInteger(resultMagnitude[1], signum);
	}
	return result;
    }

    /**
     * Returns a BigInteger whose value is (this ** exponent).  Throws
     * an ArithmeticException if exponent < 0 (as the operation would yield
     * a non-integer value). Note that exponent is an integer rather than
     * a BigInteger.
     */
    public BigInteger pow(int exponent) throws ArithmeticException {
	if (exponent < 0)
	    throw new ArithmeticException("Negative exponent");
	if (signum==0)
	    return (exponent==0 ? ONE : this);

	/* Perform exponetiation using repeated squaring trick */
	BigInteger result = valueOf(exponent<0 && (exponent&1)==1 ? -1 : 1);
	BigInteger baseToPow2 = this;
	while (exponent != 0) {
	    if ((exponent & 1)==1)
		result = result.multiply(baseToPow2);
	    if ((exponent >>= 1) != 0)
		baseToPow2 = new BigInteger(
				    plumbSquare(baseToPow2.magnitude), 1);
	}
	return result;
    }

    /**
     * Returns a BigInteger whose value is the greatest common denominator
     * of abs(this) and abs(val).  Returns 0 if this == 0 && val == 0.
     */
    public BigInteger gcd(BigInteger val) {
	if (val.signum == 0)
	    return this.abs();
	else if (this.signum == 0)
	    return val.abs();
	else
	    return new BigInteger(plumbGcd(magnitude, val.magnitude), 1);
    }

   /**
    * Returns a BigInteger whose value is the absolute value of this
    * number.
    */
    public BigInteger abs() {
	return (signum >= 0 ? this : this.negate());
    }

    /**
     * Returns a BigInteger whose value is (-1 * this).
     */
    public BigInteger negate() {
	return new BigInteger(this.magnitude, -this.signum);
    }

    /**
     * Returns the signum function of this number (i.e., -1, 0 or 1 as
     * the value of this number is negative, zero or positive).
     */
    public int signum() {
	return this.signum;
    }

    // Modular Arithmetic Operations

    /**
     * Returns a BigInteger whose value is this mod m. Throws an
     * ArithmeticException if m <= 0.
     */
    public BigInteger mod(BigInteger m) {
	if (m.signum <= 0)
	    throw new ArithmeticException("BigInteger: modulus not positive");

	BigInteger result = this.remainder(m);
	return (result.signum >= 0 ? result : result.add(m));
    }

    /**
     * Returns a BigInteger whose value is (this ** exponent) mod m.  (If
     * exponent == 1, the returned value is (this mod m).  If exponent < 0,
     * the returned value is the modular multiplicative inverse of
     * (this ** -exponent).)  Throws an ArithmeticException if m <= 0.
     */
    public BigInteger modPow(BigInteger exponent, BigInteger m) {
	if (m.signum <= 0)
	    throw new ArithmeticException("BigInteger: modulus not positive");

	/* Workaround for a bug in Plumb: x^0 (y) dumps core for x != 0 */
	if (exponent.signum == 0)
	    return ONE;

	boolean invertResult;
	if ((invertResult = (exponent.signum < 0)))
	    exponent = exponent.negate();

	BigInteger base = (this.signum < 0 || this.compareTo(m) >= 0
			   ? this.mod(m) : this);
	BigInteger result;
	if (m.testBit(0)) { /* Odd modulus: just pass it on to Plumb */
	    result = new BigInteger
	     (plumbModPow(base.magnitude, exponent.magnitude, m.magnitude), 1);
	} else {
	    /*
	     * Even modulus.  Plumb only supports odd, so tear it into
	     * "odd part" (m1) and power of two (m2), use Plumb to exponentiate
	     * mod m1, manually exponentiate mod m2, and use Chinese Remainder
	     * Theorem to combine results.
	     */

	    /* Tear m apart into odd part (m1) and power of 2 (m2) */
	    int p = m.getLowestSetBit();      /* Max pow of 2 that divides m */
	    BigInteger m1 = m.shiftRight(p);  /* m/2**p */
	    BigInteger m2 = ONE.shiftLeft(p); /* 2**p */

	    /* Caculate (base ** exponent) mod m1 */
	    BigInteger a1 = new BigInteger
	     (plumbModPow(base.magnitude, exponent.magnitude, m1.magnitude),1);

	    /* Caculate (this ** exponent) mod m2 */
	    BigInteger a2 = base.modPow2(exponent, p);

	    /* Combine results using Chinese Remainder Theorem */
	    BigInteger y1 = m2.modInverse(m1);
	    BigInteger y2 = m1.modInverse(m2);
	    result = a1.multiply(m2).multiply(y1).add
		    (a2.multiply(m1).multiply(y2)).mod(m);
	}

	return (invertResult ? result.modInverse(m) : result);
    }

    /**
     * Returns (this ** exponent) mod(2**p)
     */
    private BigInteger modPow2(BigInteger exponent, int p) {
	/*
	 * Perform exponetiation using repeated squaring trick, chopping off
	 * high order bits as indicated by modulus.
	 */
	BigInteger result = valueOf(1);
	BigInteger baseToPow2 = this.mod2(p);
	while (exponent.signum != 0) {
	    if (exponent.testBit(0))
		result = result.multiply(baseToPow2).mod2(p);
	    exponent = exponent.shiftRight(1);
	    if (exponent.signum != 0)
		baseToPow2 = new BigInteger(
			       plumbSquare(baseToPow2.magnitude), 1).mod2(p);
	}
	return result;
    }

    /**
     * Returns this mod(2**p).  Assumes that this BigInteger >= 0 and p > 0.
     */
    private BigInteger mod2(int p) {
	if (bitLength() <= p)
	    return this;

	/* Copy remaining bytes of magnitude */
	int numBytes = (p+7)/8;
	byte[] mag = new byte[numBytes];
	for (int i=0; i<numBytes; i++)
	    mag[i] = magnitude[i + (magnitude.length - numBytes)];

	/* Mask out any excess bits */
	int excessBits = 8*numBytes - p;
	mag[0] &= (1 << (8-excessBits)) - 1;

	return (mag[0]==0 ? new BigInteger(1, mag) : new BigInteger(mag, 1));
    }

    /**
     * Returns modular multiplicative inverse of this, mod m.  Throws an
     * ArithmeticException if m <= 0 or this has no multiplicative inverse
     * mod m (i.e., gcd(this, m) != 1).
     */
    public BigInteger modInverse(BigInteger m) throws ArithmeticException {
	if (m.signum != 1)
	    throw new ArithmeticException("BigInteger: modulus not positive");

	/* Calculate (this mod m) */
	BigInteger modVal = this.remainder(m);
	if (modVal.signum < 0)
	    modVal = modVal.add(m);
	if (!modVal.gcd(m).equals(ONE))
	    throw new ArithmeticException("BigInteger not invertible");

	return new BigInteger(plumbModInverse(modVal.magnitude,m.magnitude),1);
    }


    // Shift Operations

    /**
     * Returns a BigInteger whose value is (this << n).  (Computes
     * floor(this * 2**n).)
     */
    public BigInteger shiftLeft(int n) {
	if (n==0)
	    return this;
	if (n<0)
	    return shiftRight(-n);

	int nBytes = n/8;
	int nBits = n%8;

	byte result[] = new byte[(bitLength()+n)/8+1];
	if (nBits == 0) {
	    for (int i=nBytes; i<result.length; i++)
		result[result.length-1-i] = getByte(i-nBytes);
	} else {
	    for (int i=nBytes; i<result.length; i++)
		result[result.length-1-i] = (byte)
		    ((getByte(i-nBytes) << nBits)
			| (i==nBytes ? 0
			   : ((getByte(i-nBytes-1)&0xff) >> (8-nBits))));
	}

	return valueOf(result);
    }

    /**
     * Returns a BigInteger whose value is (this >> n).  Sign extension is
     * performed.  (Computes floor(this / 2**n).)
     */
    public BigInteger shiftRight(int n) {
	if (n==0)
	    return this;
	if (n<0)
	    return shiftLeft(-n);
	if (n >= bitLength())
	    return (signum<0 ? valueOf(-1) : ZERO);

	int nBytes = n/8;
	int nBits = n%8;

	byte result[] = new byte[(bitLength-n)/8+1];
	if (nBits == 0) {
	    for (int i=0; i<result.length; i++)
		result[result.length-1-i] = getByte(nBytes+i);
	} else {
	    for (int i=0; i<result.length; i++)
		result[result.length-1-i] = (byte)
		((getByte(nBytes+i+1)<<8 | (getByte(nBytes+i)&0xff)) >> nBits);
	}

	return valueOf(result);
    }


    // Bitwise Operations

    /**
     * Returns a BigInteger whose value is (this & val).  (This method
     * returns a negative number iff this and val are both negative.)
     */
    public BigInteger and(BigInteger val) {
	byte[] result = new byte[Math.max(byteLength(), val.byteLength())];
	for (int i=0; i<result.length; i++)
	    result[i] = (byte) (getByte(result.length-i-1)
				& val.getByte(result.length-i-1));

	return valueOf(result);
    }

    /**
     * Returns a BigInteger whose value is (this | val).  (This method
     * returns a negative number iff either this or val is negative.)
     */
    public BigInteger or(BigInteger val) {
	byte[] result = new byte[Math.max(byteLength(), val.byteLength())];
	for (int i=0; i<result.length; i++)
	    result[i] = (byte) (getByte(result.length-i-1)
				| val.getByte(result.length-i-1));

	return valueOf(result);
    }

    /**
     * Returns a BigInteger whose value is (this ^ val).  (This method
     * returns a negative number iff exactly one of this and val are
     * negative.)
     */
    public BigInteger xor(BigInteger val) {
	byte[] result = new byte[Math.max(byteLength(), val.byteLength())];
	for (int i=0; i<result.length; i++)
	    result[i] = (byte) (getByte(result.length-i-1)
				^ val.getByte(result.length-i-1));

	return valueOf(result);
    }

    /**
     * Returns a BigInteger whose value is (~this).  (This method returns
     * a negative value iff this number is non-negative.)
     */
    public BigInteger not() {
	byte[] result = new byte[byteLength()];
	for (int i=0; i<result.length; i++)
	    result[i] = (byte) ~getByte(result.length-i-1);

	return valueOf(result);
    }

    /**
     * Returns a BigInteger whose value is (this & ~val).  This method,
     * which is equivalent to and(val.not()), is provided as a convenience
     * for masking operations.  (This method returns a negative number iff
     * this is negative and val is positive.)
     */
    public BigInteger andNot(BigInteger val) {
	byte[] result = new byte[Math.max(byteLength(), val.byteLength())];
	for (int i=0; i<result.length; i++)
	    result[i] = (byte) (getByte(result.length-i-1)
				& ~val.getByte(result.length-i-1));