biginteger.java

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

/*
 * @(#)BigInteger.java	1.9 98/10/28
 *
 * Copyright 1996-1998 by Sun Microsystems, Inc.,
 * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
 * All rights reserved.
 *
 * This software is the confidential and proprietary information
 * of Sun Microsystems, Inc. ("Confidential Information").  You
 * shall not disclose such Confidential Information and shall use
 * it only in accordance with the terms of the license agreement
 * you entered into with Sun.
 */

package java.math;

import java.util.Random;

/**
 * Immutable arbitrary-precision integers.  All operations behave as if
 * BigIntegers were represented in two's-complement notation (like Java's
 * primitive integer types).  BigIntegers provide analogues to all of Java's
 * primitive integer operators, and all relevant static methods from
 * java.lang.Math.  Additionally, BigIntegers provide operations for modular
 * arithmetic, GCD calculation, primality testing, prime generation,
 * single-bit manipulation, and a few other odds and ends.
 *
 * <P>Semantics of arithmetic operations exactly mimic those of java's integer
 * arithmetic operators, as defined in The Java Language Specification.  For
 * example, division by zero throws an ArithmeticException, and division of
 * a negative by a positive yields a negative (or zero) remainder.  All of
 * the details in the Spec concerning overflow are ignored, as BigIntegers
 * are made as large as necessary to accommodate the results of an operation.
 *
 * <P>Semantics of shift operations extend those of Java's shift operators
 * to allow for negative shift distances.  A right-shift with a negative
 * shift distance results in a left shift, and vice-versa.  The unsigned
 * right shift operator (>>>) is omitted, as this operation makes little
 * sense in combination with the "infinite word size" abstraction provided
 * by this class.
 *
 * <P>Semantics of bitwise logical operations are are exactly mimic those of
 * Java's bitwise integer operators.  The Binary operators (and, or, xor)
 * implicitly perform sign extension on the shorter of the two operands
 * prior to performing the operation.
 *
 * <P>Comparison operations perform signed integer comparisons, analogous to
 * those performed by java's relational and equality operators.
 *
 * <P>Modular arithmetic operations are provided to compute residues, perform
 * exponentiation, and compute multiplicative inverses.  These methods always
 * return a non-negative result, between 0 and (modulus - 1), inclusive.
 *
 * <P>Single-bit operations operate on a single bit of the two's-complement
 * representation of their operand.  If necessary, the operand is sign
 * extended so that it contains the designated bit.  None of the single-bit
 * operations can produce a number with a different sign from the the
 * BigInteger being operated on, as they affect only a single bit, and the
 * "infinite word size" abstraction provided by this class ensures that there
 * are infinitely many "virtual sign bits" preceding each BigInteger.
 *
 *
 * @see BigDecimal
 * @version 	1.9, 98/10/29
 * @author      Josh Bloch
 */
public class BigInteger extends Number {

    /*
     * The number is internally stored in "minimal" sign-magnitude format
     * (i.e., no BigIntegers have a leading zero byte in their magnitudes).
     * Zero is represented with a signum of 0 (and a zero-length magnitude).
     * Thus, there is exactly one representation for each value.
     */
    private int signum;
    private byte[] magnitude;

    /*
     * These "redundant fields" are initialized with recognizable nonsense
     * values, and cached the first time they are needed (or never, if they
     * aren't needed).
     */
    private int bitCount =  -1;
    private int bitLength = -1;
    private int firstNonzeroByteNum = -2;  /* Only used for negative numbers */
    private int lowestSetBit = -2;

    //Constructors

    /**
     * Translates a byte array containing the two's-complement representation
     * of a (signed) integer into a BigInteger.  The input array is assumed to
     * be big-endian (i.e., the most significant byte is in the [0] position).
     * (The most significant bit of the most significant byte is the sign bit.)
     * The array must contain at least one byte or a NumberFormatException
     * will be thrown.
     */
    public BigInteger(byte[] val) throws NumberFormatException{
	if (val.length == 0)
	    throw new NumberFormatException("Zero length BigInteger");

	if (val[0] < 0) {
	    magnitude = makePositive(val);
	    signum = -1;
	} else {
	    magnitude = stripLeadingZeroBytes(val);
	    signum = (magnitude.length == 0 ? 0 : 1);
	}
    }

    /**
     * Translates the sign-magnitude representation of an integer into a
     * BigInteger.  The sign is represented as an integer signum value (-1 for
     * negative, 0 for zero, 1 for positive).  The magnitude is represented
     * as a big-endian byte array (i.e., the most significant byte is in the
     * [0] position).  An invalid signum value or a 0 signum value coupled
     * with a nonzero magnitude will result in a NumberFormatException.
     * A zero length magnitude array is permissible, and will result in
     * in a value of 0 (irrespective of the given signum value).
     */
    public BigInteger(int signum, byte[] magnitude)
    throws NumberFormatException{
	this.magnitude = stripLeadingZeroBytes(magnitude);

	if (signum < -1 || signum > 1)
	    throw(new NumberFormatException("Invalid signum value"));

	if (this.magnitude.length==0) {
	    this.signum = 0;
	} else {
	    if (signum == 0)
		throw(new NumberFormatException("signum-magnitude mismatch"));
	    this.signum = signum;
	}
    }

    /**
     * Translates a string containing an optional minus sign followed by a
     * sequence of one or more digits in the specified radix into a BigInteger.
     * The character-to-digit mapping is provided by Character.digit.
     * Any extraneous characters (including whitespace), or a radix outside
     * the range from Character.MIN_RADIX(2) to Character.MAX_RADIX(36),
     * inclusive, will result in a NumberFormatException.
     */
    public BigInteger(String val, int radix) throws NumberFormatException {
	int cursor = 0, numDigits;

	if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
	    throw new NumberFormatException("Radix out of range");
	if (val.length() == 0)
	    throw new NumberFormatException("Zero length BigInteger");

	/* Check for leading minus sign */
	signum = 1;
	if (val.charAt(0) == '-') {
	    if (val.length() == 1)
		throw new NumberFormatException("Zero length BigInteger");
	    signum = -1;
	    cursor = 1;
	}

	/* Skip leading zeros and compute number of digits in magnitude */
	while (cursor<val.length() && val.charAt(cursor)==ZERO_CHAR)
	    cursor++;
	if (cursor==val.length()) {
	    signum = 0;
	    magnitude = new byte[0];
	    return;
	} else {
	    numDigits = val.length() - cursor;
	}

	/* Process first (potentially short) digit group, if necessary */
	int firstGroupLen = numDigits % digitsPerLong[radix];
	if (firstGroupLen == 0)
	    firstGroupLen = digitsPerLong[radix];
	String group = val.substring(cursor, cursor += firstGroupLen);
	BigInteger tmp = valueOf(Long.parseLong(group, radix));

	/* Process remaining digit groups */
	while (cursor < val.length()) {
	    group = val.substring(cursor, cursor += digitsPerLong[radix]);
	    long groupVal = Long.parseLong(group, radix);
	    if (groupVal <0)
		throw new NumberFormatException("Illegal digit");
	    tmp = tmp.multiply(longRadix[radix]).add(valueOf(groupVal));
	}

	magnitude = tmp.magnitude;
    }

    /**
     * Translates a string containing an optional minus sign followed by a
     * sequence of one or more decimal digits into a BigInteger.  The
     * character-to-digit mapping is provided by Character.digit.
     * Any extraneous characters (including whitespace) will result in a
     * NumberFormatException.
     */
    public BigInteger(String val) throws NumberFormatException {
	this(val, 10);
    }

    /**
     * Returns a random number uniformly distributed on [0, 2**numBits - 1]
     * (assuming a fair source of random bits is provided in rndSrc).
     * Note that this constructor always returns a non-negative BigInteger.
     * Throws an IllegalArgumentException if numBits < 0.
     */
    public BigInteger(int numBits, Random rndSrc)
    throws IllegalArgumentException {
	this(1, randomBits(numBits, rndSrc));
    }

    private static byte[] randomBits(int numBits, Random rndSrc)
    throws IllegalArgumentException {
	if (numBits < 0)
	    throw new IllegalArgumentException("numBits must be non-negative");
	int numBytes = (numBits+7)/8;
	byte[] randomBits = new byte[numBytes];

	/* Generate random bytes and mask out any excess bits */
	if (numBytes > 0) {
	    rndSrc.nextBytes(randomBits);
	    int excessBits = 8*numBytes - numBits;
	    randomBits[0] &= (1 << (8-excessBits)) - 1;
	}
	return randomBits;
    }


    /**
     * Returns a randomly selected BigInteger with the specified bitLength
     * that is probably prime.  The certainty parameter is a measure of
     * the uncertainty that the caller is willing to tolerate: the probability
     * that the number is prime will exceed 1 - 1/2**certainty.  The execution
     * time is proportional to the value of the certainty parameter.  The
     * given random number generator is used to select candidates to be
     * tested for primality.  Throws an ArithmeticException if bitLength < 2.
     */
    public BigInteger(int bitLength, int certainty, Random rnd) {
	if (bitLength < 2)
	    throw new ArithmeticException("bitLength < 2");

	BigInteger p;
	do {
	    /*
	     * Select a candidate of exactly the right length.  Note that
	     * Plumb's generator doesn't handle bitLength<=16 properly.
	     */
	    do {
		p = new BigInteger(bitLength-1, rnd).setBit(bitLength-1);
		p = (bitLength <= 16
		     ? (bitLength > 2 ? p.setBit(0) : p)
		     : new BigInteger(plumbGeneratePrime(p.magnitude), 1));
	    } while (p.bitLength() != bitLength);
	} while (!p.isProbablePrime(certainty));

	signum = 1;
	magnitude = p.magnitude;
    }


    /**
     * This private constructor differs from its public cousin
     * with the arguments reversed in two ways: it assumes that its
     * arguments are correct, and it doesn't copy the magnitude array.
     */
    private BigInteger(byte[] magnitude, int signum) {
	this.signum = (magnitude.length==0 ? 0 : signum);
	this.magnitude = magnitude;
    }


    //Static Factory Methods

    /**
     * Returns a BigInteger with the specified value.  This factory is provided
     * in preference to a (long) constructor because it allows for reuse
     * of frequently used BigIntegers (like 0 and 1), obviating the need for
     * exported constants.
     */
    public static BigInteger valueOf(long val) {
	/* If -MAX_CONSTANT < val < MAX_CONSTANT, return stashed constant */
	if (val == 0)
	    return ZERO;
	if (val > 0 && val <= MAX_CONSTANT)
	    return posConst[(int) val];
	else if (val < 0 && val >= -MAX_CONSTANT)
	    return negConst[(int) -val];

	/* Dump two's complement binary into valArray */
	byte valArray[] = new byte[8];
	for (int i=0; i<8; i++, val >>= 8)
	    valArray[7-i] = (byte)val;
	return new BigInteger(valArray);
    }

    private final static BigInteger ZERO = new BigInteger(new byte[0], 0);

    /**
     * Initialize static constant array when class is loaded.
     */
    private final static int MAX_CONSTANT = 16;
    private static BigInteger posConst[] = new BigInteger[MAX_CONSTANT+1];
    private static BigInteger negConst[] = new BigInteger[MAX_CONSTANT+1];
    static {
	for (int i = 1; i <= MAX_CONSTANT; i++) {
	    byte[] magnitude = new byte[1];
	    magnitude[0] = (byte) i;
	    posConst[i] = new BigInteger(magnitude,  1);
	    negConst[i] = new BigInteger(magnitude, -1);
	}
    }

    /**
     * Returns a BigInteger with the given two's complement representation.
     * Assumes that the input array will not be modified (the returned
     * BigInteger will reference the input array if feasible).
     */
    private static BigInteger valueOf(byte val[]) {
	return (val[0]>0 ? new BigInteger(val, 1) : new BigInteger(val));
    }


    // Arithmetic Operations

    /**
     * Returns a BigInteger whose value is (this + val).
     */
    public BigInteger add(BigInteger val) throws ArithmeticException {
	if (val.signum == 0)
	    return this;
	else if (this.signum == 0)
	    return val;
	else if (val.signum == signum)
	    return new BigInteger(plumbAdd(magnitude, val.magnitude), signum);
	else if (this.signum < 0)
	    return plumbSubtract(val.magnitude, magnitude);
	else  /* val.signum < 0 */
	    return plumbSubtract(magnitude, val.magnitude);
    }

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

    /**
     * Returns a BigInteger whose value is (this * val).
     */
    public BigInteger multiply(BigInteger val) {

	if (val.signum == 0 || this.signum==0)
	    return ZERO;
	else
	    return new BigInteger(plumbMultiply(magnitude, val.magnitude),
				  signum * val.signum);
    }

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