FileDocCategorySizeDatePackage
BigInteger.javaAPI DocJava SE 6 API109806Tue Jun 10 00:25:40 BST 2008java.math

BigInteger

public class BigInteger extends Number implements Comparable
Immutable arbitrary-precision integers. All operations behave as if BigIntegers were represented in two's-complement notation (like Java's primitive integer types). BigInteger provides analogues to all of Java's primitive integer operators, and all relevant methods from java.lang.Math. Additionally, BigInteger provides operations for modular arithmetic, GCD calculation, primality testing, prime generation, bit manipulation, and a few other miscellaneous operations.

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.

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.

Semantics of bitwise logical operations 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.

Comparison operations perform signed integer comparisons, analogous to those performed by Java's relational and equality operators.

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.

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 BigInteger with a different sign from 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.

For the sake of brevity and clarity, pseudo-code is used throughout the descriptions of BigInteger methods. The pseudo-code expression (i + j) is shorthand for "a BigInteger whose value is that of the BigInteger i plus that of the BigInteger j." The pseudo-code expression (i == j) is shorthand for "true if and only if the BigInteger i represents the same value as the BigInteger j." Other pseudo-code expressions are interpreted similarly.

All methods and constructors in this class throw NullPointerException when passed a null object reference for any input parameter.

see
BigDecimal
version
1.75, 06/28/06
author
Josh Bloch
author
Michael McCloskey
since
JDK1.1

Fields Summary
int
signum
The signum of this BigInteger: -1 for negative, 0 for zero, or 1 for positive. Note that the BigInteger zero must have a signum of 0. This is necessary to ensures that there is exactly one representation for each BigInteger value.
int[]
mag
The magnitude of this BigInteger, in big-endian order: the zeroth element of this array is the most-significant int of the magnitude. The magnitude must be "minimal" in that the most-significant int (mag[0]) must be non-zero. This is necessary to ensure that there is exactly one representation for each BigInteger value. Note that this implies that the BigInteger zero has a zero-length mag array.
private int
bitCount
The bitCount of this BigInteger, as returned by bitCount(), or -1 (either value is acceptable).
private int
bitLength
The bitLength of this BigInteger, as returned by bitLength(), or -1 (either value is acceptable).
private int
lowestSetBit
The lowest set bit of this BigInteger, as returned by getLowestSetBit(), or -2 (either value is acceptable).
private int
firstNonzeroByteNum
The index of the lowest-order byte in the magnitude of this BigInteger that contains a nonzero byte, or -2 (either value is acceptable). The least significant byte has int-number 0, the next byte in order of increasing significance has byte-number 1, and so forth.
private int
firstNonzeroIntNum
The index of the lowest-order int in the magnitude of this BigInteger that contains a nonzero int, or -2 (either value is acceptable). The least significant int has int-number 0, the next int in order of increasing significance has int-number 1, and so forth.
private static final long
LONG_MASK
This mask is used to obtain the value of an int as if it were unsigned.
private static long[]
bitsPerDigit
private static final int
SMALL_PRIME_THRESHOLD
private static final int
DEFAULT_PRIME_CERTAINTY
private static final BigInteger
SMALL_PRIME_PRODUCT
private static volatile Random
staticRandom
private static final int
MAX_CONSTANT
Initialize static constant array when class is loaded.
private static BigInteger[]
posConst
private static BigInteger[]
negConst
public static final BigInteger
ZERO
The BigInteger constant zero.
public static final BigInteger
ONE
The BigInteger constant one.
private static final BigInteger
TWO
The BigInteger constant two. (Not exported.)
public static final BigInteger
TEN
The BigInteger constant ten.
static int[]
bnExpModThreshTable
static final byte[]
trailingZeroTable
private static String[]
zeros
private static int[]
digitsPerLong
private static BigInteger[]
longRadix
private static int[]
digitsPerInt
private static int[]
intRadix
private static final long
serialVersionUID
use serialVersionUID from JDK 1.1. for interoperability
private static final ObjectStreamField[]
serialPersistentFields
Serializable fields for BigInteger.
Constructors Summary
public BigInteger(byte[] val)
Translates a byte array containing the two's-complement binary representation of a BigInteger into a BigInteger. The input array is assumed to be in big-endian byte-order: the most significant byte is in the zeroth element.

param
val big-endian two's-complement binary representation of BigInteger.
throws
NumberFormatException val is zero bytes long.


    //Constructors

                                               	                   
       
	if (val.length == 0)
	    throw new NumberFormatException("Zero length BigInteger");

	if (val[0] < 0) {
            mag = makePositive(val);
	    signum = -1;
	} else {
	    mag = stripLeadingZeroBytes(val);
	    signum = (mag.length == 0 ? 0 : 1);
	}
    
public BigInteger(int numBits, Random rnd)
Constructs a randomly generated BigInteger, uniformly distributed over the range 0 to (2numBits - 1), inclusive. The uniformity of the distribution assumes that a fair source of random bits is provided in rnd. Note that this constructor always constructs a non-negative BigInteger.

param
numBits maximum bitLength of the new BigInteger.
param
rnd source of randomness to be used in computing the new BigInteger.
throws
IllegalArgumentException numBits is negative.
see
#bitLength()

	this(1, randomBits(numBits, rnd));
    
public BigInteger(int bitLength, int certainty, Random rnd)
Constructs a randomly generated positive BigInteger that is probably prime, with the specified bitLength.

It is recommended that the {@link #probablePrime probablePrime} method be used in preference to this constructor unless there is a compelling need to specify a certainty.

param
bitLength bitLength of the returned BigInteger.
param
certainty a measure of the uncertainty that the caller is willing to tolerate. The probability that the new BigInteger represents a prime number will exceed (1 - 1/2certainty). The execution time of this constructor is proportional to the value of this parameter.
param
rnd source of random bits used to select candidates to be tested for primality.
throws
ArithmeticException bitLength < 2.
see
#bitLength()

        BigInteger prime;

	if (bitLength < 2)
	    throw new ArithmeticException("bitLength < 2");
        // The cutoff of 95 was chosen empirically for best performance
        prime = (bitLength < 95 ? smallPrime(bitLength, certainty, rnd)
                                : largePrime(bitLength, certainty, rnd));
	signum = 1;
	mag = prime.mag;
    
private BigInteger(int[] val)
This private constructor translates an int array containing the two's-complement binary representation of a BigInteger into a BigInteger. The input array is assumed to be in big-endian int-order: the most significant int is in the zeroth element.

	if (val.length == 0)
	    throw new NumberFormatException("Zero length BigInteger");

	if (val[0] < 0) {
            mag = makePositive(val);
	    signum = -1;
	} else {
	    mag = trustedStripLeadingZeroInts(val);
	    signum = (mag.length == 0 ? 0 : 1);
	}
    
private BigInteger(int[] magnitude, int signum)
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.

	this.signum = (magnitude.length==0 ? 0 : signum);
	this.mag = magnitude;
    
private BigInteger(byte[] magnitude, int signum)
This private constructor is for internal use and assumes that its arguments are correct.

	this.signum = (magnitude.length==0 ? 0 : signum);
        this.mag = stripLeadingZeroBytes(magnitude);
    
BigInteger(MutableBigInteger val, int sign)
This private constructor is for internal use in converting from a MutableBigInteger object into a BigInteger.

        if (val.offset > 0 || val.value.length != val.intLen) {
            mag = new int[val.intLen];
            for(int i=0; i<val.intLen; i++)
                mag[i] = val.value[val.offset+i];
        } else {
            mag = val.value;
        }

	this.signum = (val.intLen == 0) ? 0 : sign;
    
private BigInteger(long val)
Constructs a BigInteger with the specified value, which may not be zero.

        if (val < 0) {
            signum = -1;
            val = -val;
        } else {
            signum = 1;
        }

        int highWord = (int)(val >>> 32);
        if (highWord==0) {
            mag = new int[1];
            mag[0] = (int)val;
        } else {
            mag = new int[2];
            mag[0] = highWord;
            mag[1] = (int)val;
        }
    
public BigInteger(int signum, byte[] magnitude)
Translates the sign-magnitude representation of a BigInteger into a BigInteger. The sign is represented as an integer signum value: -1 for negative, 0 for zero, or 1 for positive. The magnitude is a byte array in big-endian byte-order: the most significant byte is in the zeroth element. A zero-length magnitude array is permissible, and will result inin a BigInteger value of 0, whether signum is -1, 0 or 1.

param
signum signum of the number (-1 for negative, 0 for zero, 1 for positive).
param
magnitude big-endian binary representation of the magnitude of the number.
throws
NumberFormatException signum is not one of the three legal values (-1, 0, and 1), or signum is 0 and magnitude contains one or more non-zero bytes.

	this.mag = stripLeadingZeroBytes(magnitude);

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

	if (this.mag.length==0) {
	    this.signum = 0;
	} else {
	    if (signum == 0)
		throw(new NumberFormatException("signum-magnitude mismatch"));
	    this.signum = signum;
	}
    
private BigInteger(int signum, int[] magnitude)
A constructor for internal use that translates the sign-magnitude representation of a BigInteger into a BigInteger. It checks the arguments and copies the magnitude so this constructor would be safe for external use.

	this.mag = stripLeadingZeroInts(magnitude);

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

	if (this.mag.length==0) {
	    this.signum = 0;
	} else {
	    if (signum == 0)
		throw(new NumberFormatException("signum-magnitude mismatch"));
	    this.signum = signum;
	}
    
public BigInteger(String val, int radix)
Translates the String representation of a BigInteger in the specified radix into a BigInteger. The String representation consists of an optional minus sign followed by a sequence of one or more digits in the specified radix. The character-to-digit mapping is provided by Character.digit. The String may not contain any extraneous characters (whitespace, for example).

param
val String representation of BigInteger.
param
radix radix to be used in interpreting val.
throws
NumberFormatException val is not a valid representation of a BigInteger in the specified radix, or radix is outside the range from {@link Character#MIN_RADIX} to {@link Character#MAX_RADIX}, inclusive.
see
Character#digit

	int cursor = 0, numDigits;
        int len = val.length();

	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 minus sign
	signum = 1;
        int index = val.lastIndexOf("-");
        if (index != -1) {
            if (index == 0) {
                if (val.length() == 1)
                    throw new NumberFormatException("Zero length BigInteger");
                signum = -1;
                cursor = 1;
            } else {
                throw new NumberFormatException("Illegal embedded minus sign");
            }
        }

        // Skip leading zeros and compute number of digits in magnitude
	while (cursor < len &&
               Character.digit(val.charAt(cursor),radix) == 0)
	    cursor++;
	if (cursor == len) {
	    signum = 0;
	    mag = ZERO.mag;
	    return;
	} else {
	    numDigits = len - cursor;
	}

        // Pre-allocate array of expected size. May be too large but can
        // never be too small. Typically exact.
        int numBits = (int)(((numDigits * bitsPerDigit[radix]) >>> 10) + 1);
        int numWords = (numBits + 31) /32;
        mag = new int[numWords];

	// Process first (potentially short) digit group
	int firstGroupLen = numDigits % digitsPerInt[radix];
	if (firstGroupLen == 0)
	    firstGroupLen = digitsPerInt[radix];
	String group = val.substring(cursor, cursor += firstGroupLen);
        mag[mag.length - 1] = Integer.parseInt(group, radix);
	if (mag[mag.length - 1] < 0)
	    throw new NumberFormatException("Illegal digit");
        
	// Process remaining digit groups
        int superRadix = intRadix[radix];
        int groupVal = 0;
	while (cursor < val.length()) {
	    group = val.substring(cursor, cursor += digitsPerInt[radix]);
	    groupVal = Integer.parseInt(group, radix);
	    if (groupVal < 0)
		throw new NumberFormatException("Illegal digit");
            destructiveMulAdd(mag, superRadix, groupVal);
	}
        // Required for cases where the array was overallocated.
        mag = trustedStripLeadingZeroInts(mag);
    
BigInteger(char[] val)

        int cursor = 0, numDigits;
        int len = val.length;

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

        // Skip leading zeros and compute number of digits in magnitude
	while (cursor < len && Character.digit(val[cursor], 10) == 0)
	    cursor++;
	if (cursor == len) {
	    signum = 0;
	    mag = ZERO.mag;
	    return;
	} else {
	    numDigits = len - cursor;
	}

        // Pre-allocate array of expected size
        int numWords;
        if (len < 10) {
            numWords = 1;
        } else {    
            int numBits = (int)(((numDigits * bitsPerDigit[10]) >>> 10) + 1);
            numWords = (numBits + 31) /32;
        }
        mag = new int[numWords];
 
	// Process first (potentially short) digit group
	int firstGroupLen = numDigits % digitsPerInt[10];
	if (firstGroupLen == 0)
	    firstGroupLen = digitsPerInt[10];
        mag[mag.length-1] = parseInt(val, cursor,  cursor += firstGroupLen);
        
	// Process remaining digit groups
	while (cursor < len) {
	    int groupVal = parseInt(val, cursor, cursor += digitsPerInt[10]);
            destructiveMulAdd(mag, intRadix[10], groupVal);
	}
        mag = trustedStripLeadingZeroInts(mag);
    
public BigInteger(String val)
Translates the decimal String representation of a BigInteger into a BigInteger. The String representation consists of an optional minus sign followed by a sequence of one or more decimal digits. The character-to-digit mapping is provided by Character.digit. The String may not contain any extraneous characters (whitespace, for example).

param
val decimal String representation of BigInteger.
throws
NumberFormatException val is not a valid representation of a BigInteger.
see
Character#digit

	this(val, 10);
    
Methods Summary
public java.math.BigIntegerabs()
Returns a BigInteger whose value is the absolute value of this BigInteger.

return
abs(this)

	return (signum >= 0 ? this : this.negate());
    
public java.math.BigIntegeradd(java.math.BigInteger val)
Returns a BigInteger whose value is (this + val).

param
val value to be added to this BigInteger.
return
this + val


    // Arithmetic Operations

                                
        
        int[] resultMag;
	if (val.signum == 0)
            return this;
	if (signum == 0)
	    return val;
	if (val.signum == signum)
            return new BigInteger(add(mag, val.mag), signum);

        int cmp = intArrayCmp(mag, val.mag);
        if (cmp==0)
            return ZERO;
        resultMag = (cmp>0 ? subtract(mag, val.mag)
                           : subtract(val.mag, mag));
        resultMag = trustedStripLeadingZeroInts(resultMag);

        return new BigInteger(resultMag, cmp*signum);
    
private static int[]add(int[] x, int[] y)
Adds the contents of the int arrays x and y. This method allocates a new int array to hold the answer and returns a reference to that array.

        // If x is shorter, swap the two arrays
        if (x.length < y.length) {
            int[] tmp = x;
            x = y;
            y = tmp;
        }

        int xIndex = x.length;
        int yIndex = y.length;
        int result[] = new int[xIndex];
        long sum = 0;

        // Add common parts of both numbers
        while(yIndex > 0) {
            sum = (x[--xIndex] & LONG_MASK) + 
                  (y[--yIndex] & LONG_MASK) + (sum >>> 32);
            result[xIndex] = (int)sum;
        }

        // Copy remainder of longer number while carry propagation is required
        boolean carry = (sum >>> 32 != 0);
        while (xIndex > 0 && carry)
            carry = ((result[--xIndex] = x[xIndex] + 1) == 0);

        // Copy remainder of longer number
        while (xIndex > 0)
            result[--xIndex] = x[xIndex];

        // Grow result if necessary
        if (carry) {
            int newLen = result.length + 1;
            int temp[] = new int[newLen];
            for (int i = 1; i<newLen; i++)
                temp[i] = result[i-1];
            temp[0] = 0x01;
            result = temp;
        }
        return result;
    
static intaddOne(int[] a, int offset, int mlen, int carry)
Add one word to the number a mlen words into a. Return the resulting carry.

        offset = a.length-1-mlen-offset;
        long t = (a[offset] & LONG_MASK) + (carry & LONG_MASK);
        
        a[offset] = (int)t;
        if ((t >>> 32) == 0)
            return 0;
        while (--mlen >= 0) {
            if (--offset < 0) { // Carry out of number
                return 1;
            } else {
                a[offset]++;
                if (a[offset] != 0)
                    return 0;
            }
        }
        return 1;
    
public java.math.BigIntegerand(java.math.BigInteger val)
Returns a BigInteger whose value is (this & val). (This method returns a negative BigInteger if and only if this and val are both negative.)

param
val value to be AND'ed with this BigInteger.
return
this & val

	int[] result = new int[Math.max(intLength(), val.intLength())];
	for (int i=0; i<result.length; i++)
	    result[i] = (int) (getInt(result.length-i-1)
				& val.getInt(result.length-i-1));

	return valueOf(result);
    
public java.math.BigIntegerandNot(java.math.BigInteger val)
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 BigInteger if and only if this is negative and val is positive.)

param
val value to be complemented and AND'ed with this BigInteger.
return
this & ~val

	int[] result = new int[Math.max(intLength(), val.intLength())];
	for (int i=0; i<result.length; i++)
	    result[i] = (int) (getInt(result.length-i-1)
				& ~val.getInt(result.length-i-1));

	return valueOf(result);
    
static intbitCnt(int val)

        val -= (0xaaaaaaaa & val) >>> 1;
        val = (val & 0x33333333) + ((val >>> 2) & 0x33333333);
        val = val + (val >>> 4) & 0x0f0f0f0f;
        val += val >>> 8;
        val += val >>> 16;
        return val & 0xff;
    
public intbitCount()
Returns the number of bits in the two's complement representation of this BigInteger that differ from its sign bit. This method is useful when implementing bit-vector style sets atop BigIntegers.

return
number of bits in the two's complement representation of this BigInteger that differ from its sign bit.


                                                                  
       
	/*
	 * Initialize bitCount field the first time this method is executed.
	 * This method depends on the atomicity of int modifies; without
	 * this guarantee, it would have to be synchronized.
	 */
	if (bitCount == -1) {
	    // Count the bits in the magnitude
	    int magBitCount = 0;
	    for (int i=0; i<mag.length; i++)
		magBitCount += bitCnt(mag[i]);

	    if (signum < 0) {
		// Count the trailing zeros in the magnitude
		int magTrailingZeroCount = 0, j;
		for (j=mag.length-1; mag[j]==0; j--)
		    magTrailingZeroCount += 32;
		magTrailingZeroCount +=
                            trailingZeroCnt(mag[j]);

		bitCount = magBitCount + magTrailingZeroCount - 1;
	    } else {
		bitCount = magBitCount;
	    }
	}
	return bitCount;
    
static intbitLen(int w)
bitLen(val) is the number of bits in val.

        // Binary search - decision tree (5 tests, rarely 6)
        return
         (w < 1<<15 ?
          (w < 1<<7 ?
           (w < 1<<3 ?
            (w < 1<<1 ? (w < 1<<0 ? (w<0 ? 32 : 0) : 1) : (w < 1<<2 ? 2 : 3)) :
            (w < 1<<5 ? (w < 1<<4 ? 4 : 5) : (w < 1<<6 ? 6 : 7))) :
           (w < 1<<11 ?
            (w < 1<<9 ? (w < 1<<8 ? 8 : 9) : (w < 1<<10 ? 10 : 11)) :
            (w < 1<<13 ? (w < 1<<12 ? 12 : 13) : (w < 1<<14 ? 14 : 15)))) :
          (w < 1<<23 ?
           (w < 1<<19 ?
            (w < 1<<17 ? (w < 1<<16 ? 16 : 17) : (w < 1<<18 ? 18 : 19)) :
            (w < 1<<21 ? (w < 1<<20 ? 20 : 21) : (w < 1<<22 ? 22 : 23))) :
           (w < 1<<27 ?
            (w < 1<<25 ? (w < 1<<24 ? 24 : 25) : (w < 1<<26 ? 26 : 27)) :
            (w < 1<<29 ? (w < 1<<28 ? 28 : 29) : (w < 1<<30 ? 30 : 31)))));
    
private static intbitLength(int[] val, int len)
Calculate bitlength of contents of the first len elements an int array, assuming there are no leading zero ints.

        if (len==0)
            return 0;
        return ((len-1)<<5) + bitLen(val[0]);
    
public intbitLength()
Returns the number of bits in the minimal two's-complement representation of this BigInteger, excluding a sign bit. For positive BigIntegers, this is equivalent to the number of bits in the ordinary binary representation. (Computes (ceil(log2(this < 0 ? -this : this+1))).)

return
number of bits in the minimal two's-complement representation of this BigInteger, excluding a sign bit.

	/*
	 * Initialize bitLength field the first time this method is executed.
	 * This method depends on the atomicity of int modifies; without
	 * this guarantee, it would have to be synchronized.
	 */
	if (bitLength == -1) {
	    if (signum == 0) {
		bitLength = 0;
	    } else {
		// Calculate the bit length of the magnitude
		int magBitLength = ((mag.length-1) << 5) + bitLen(mag[0]);

		if (signum < 0) {
		    // Check if magnitude is a power of two
		    boolean pow2 = (bitCnt(mag[0]) == 1);
		    for(int i=1; i<mag.length && pow2; i++)
			pow2 = (mag[i]==0);

		    bitLength = (pow2 ? magBitLength-1 : magBitLength);
		} else {
		    bitLength = magBitLength;
		}
	    }
	}
	return bitLength;
    
public java.math.BigIntegerclearBit(int n)
Returns a BigInteger whose value is equivalent to this BigInteger with the designated bit cleared. (Computes (this & ~(1<<n)).)

param
n index of bit to clear.
return
this & ~(1<<n)
throws
ArithmeticException n is negative.

	if (n<0)
	    throw new ArithmeticException("Negative bit address");

	int intNum = n/32;
	int[] result = new int[Math.max(intLength(), (n+1)/32+1)];

	for (int i=0; i<result.length; i++)
	    result[result.length-i-1] = getInt(i);

	result[result.length-intNum-1] &= ~(1 << (n%32));

	return valueOf(result);
    
public intcompareTo(java.math.BigInteger val)
Compares this BigInteger with the specified BigInteger. This method is provided in preference to individual methods for each of the six boolean comparison operators (<, ==, >, >=, !=, <=). The suggested idiom for performing these comparisons is: (x.compareTo(y) <op> 0), where <op> is one of the six comparison operators.

param
val BigInteger to which this BigInteger is to be compared.
return
-1, 0 or 1 as this BigInteger is numerically less than, equal to, or greater than val.

	return (signum==val.signum
		? signum*intArrayCmp(mag, val.mag)
		: (signum>val.signum ? 1 : -1));
    
private static voiddestructiveMulAdd(int[] x, int y, int z)


    // Multiply x array times word y in place, and add word z
             
        // Perform the multiplication word by word
        long ylong = y & LONG_MASK;
        long zlong = z & LONG_MASK;
        int len = x.length;

        long product = 0;
        long carry = 0;
        for (int i = len-1; i >= 0; i--) {
            product = ylong * (x[i] & LONG_MASK) + carry;
            x[i] = (int)product;
            carry = product >>> 32;
        }

        // Perform the addition
        long sum = (x[len-1] & LONG_MASK) + zlong;
        x[len-1] = (int)sum;
        carry = sum >>> 32;
        for (int i = len-2; i >= 0; i--) {
            sum = (x[i] & LONG_MASK) + carry;
            x[i] = (int)sum;
            carry = sum >>> 32;
        }
    
public java.math.BigIntegerdivide(java.math.BigInteger val)
Returns a BigInteger whose value is (this / val).

param
val value by which this BigInteger is to be divided.
return
this / val
throws
ArithmeticException val==0

        MutableBigInteger q = new MutableBigInteger(),
                          r = new MutableBigInteger(),
                          a = new MutableBigInteger(this.mag),
                          b = new MutableBigInteger(val.mag);

        a.divide(b, q, r);
        return new BigInteger(q, this.signum * val.signum);
    
public java.math.BigInteger[]divideAndRemainder(java.math.BigInteger val)
Returns an array of two BigIntegers containing (this / val) followed by (this % val).

param
val value by which this BigInteger is to be divided, and the remainder computed.
return
an array of two BigIntegers: the quotient (this / val) is the initial element, and the remainder (this % val) is the final element.
throws
ArithmeticException val==0

        BigInteger[] result = new BigInteger[2];
        MutableBigInteger q = new MutableBigInteger(),
                          r = new MutableBigInteger(),
                          a = new MutableBigInteger(this.mag),
                          b = new MutableBigInteger(val.mag);
        a.divide(b, q, r);
        result[0] = new BigInteger(q, this.signum * val.signum);
        result[1] = new BigInteger(r, this.signum);
        return result;
    
public doubledoubleValue()
Converts this BigInteger to a double. This conversion is similar to the narrowing primitive conversion from double to float defined in the Java Language Specification: if this BigInteger has too great a magnitude to represent as a double, it will be converted to {@link Double#NEGATIVE_INFINITY} or {@link Double#POSITIVE_INFINITY} as appropriate. Note that even when the return value is finite, this conversion can lose information about the precision of the BigInteger value.

return
this BigInteger converted to a double.

	// Somewhat inefficient, but guaranteed to work.
	return Double.parseDouble(this.toString());
    
public booleanequals(java.lang.Object x)
Compares this BigInteger with the specified Object for equality.

param
x Object to which this BigInteger is to be compared.
return
true if and only if the specified Object is a BigInteger whose value is numerically equal to this BigInteger.

	// This test is just an optimization, which may or may not help
	if (x == this)
	    return true;

	if (!(x instanceof BigInteger))
	    return false;
	BigInteger xInt = (BigInteger) x;

	if (xInt.signum != signum || xInt.mag.length != mag.length)
	    return false;

	for (int i=0; i<mag.length; i++)
	    if (xInt.mag[i] != mag[i])
		return false;

	return true;
    
private intfirstNonzeroIntNum()
Returns the index of the int that contains the first nonzero int in the little-endian binary representation of the magnitude (int 0 is the least significant). If the magnitude is zero, return value is undefined.

	/*
	 * Initialize firstNonzeroIntNum field the first time this method is
	 * executed. This method depends on the atomicity of int modifies;
	 * without this guarantee, it would have to be synchronized.
	 */
	if (firstNonzeroIntNum == -2) {
	    // Search for the first nonzero int
	    int i;
	    for (i=mag.length-1; i>=0 && mag[i]==0; i--)
		;
	    firstNonzeroIntNum = mag.length-i-1;
	}
	return firstNonzeroIntNum;
    
public java.math.BigIntegerflipBit(int n)
Returns a BigInteger whose value is equivalent to this BigInteger with the designated bit flipped. (Computes (this ^ (1<<n)).)

param
n index of bit to flip.
return
this ^ (1<<n)
throws
ArithmeticException n is negative.

	if (n<0)
	    throw new ArithmeticException("Negative bit address");

	int intNum = n/32;
	int[] result = new int[Math.max(intLength(), intNum+2)];

	for (int i=0; i<result.length; i++)
	    result[result.length-i-1] = getInt(i);

	result[result.length-intNum-1] ^= (1 << (n%32));

	return valueOf(result);
    
public floatfloatValue()
Converts this BigInteger to a float. This conversion is similar to the narrowing primitive conversion from double to float defined in the Java Language Specification: if this BigInteger has too great a magnitude to represent as a float, it will be converted to {@link Float#NEGATIVE_INFINITY} or {@link Float#POSITIVE_INFINITY} as appropriate. Note that even when the return value is finite, this conversion can lose information about the precision of the BigInteger value.

return
this BigInteger converted to a float.

	// Somewhat inefficient, but guaranteed to work.
	return Float.parseFloat(this.toString());
    
public java.math.BigIntegergcd(java.math.BigInteger val)
Returns a BigInteger whose value is the greatest common divisor of abs(this) and abs(val). Returns 0 if this==0 && val==0.

param
val value with which the GCD is to be computed.
return
GCD(abs(this), abs(val))

        if (val.signum == 0)
	    return this.abs();
	else if (this.signum == 0)
	    return val.abs();

        MutableBigInteger a = new MutableBigInteger(this);
        MutableBigInteger b = new MutableBigInteger(val);

        MutableBigInteger result = a.hybridGCD(b);

        return new BigInteger(result, 1);
    
private intgetInt(int n)
Returns the specified int of the little-endian two's complement representation (int 0 is the least significant). The int number can be arbitrarily high (values are logically preceded by infinitely many sign ints).

        if (n < 0)
            return 0;
	if (n >= mag.length)
	    return signInt();

	int magInt = mag[mag.length-n-1];

	return (int) (signum >= 0 ? magInt :
		       (n <= firstNonzeroIntNum() ? -magInt : ~magInt));
    
public intgetLowestSetBit()
Returns the index of the rightmost (lowest-order) one bit in this BigInteger (the number of zero bits to the right of the rightmost one bit). Returns -1 if this BigInteger contains no one bits. (Computes (this==0? -1 : log2(this & -this)).)

return
index of the rightmost one bit in this BigInteger.

	/*
	 * Initialize lowestSetBit field the first time this method is
	 * executed. This method depends on the atomicity of int modifies;
	 * without this guarantee, it would have to be synchronized.
	 */
	if (lowestSetBit == -2) {
	    if (signum == 0) {
		lowestSetBit = -1;
	    } else {
		// Search for lowest order nonzero int
		int i,b;
		for (i=0; (b = getInt(i))==0; i++)
		    ;
		lowestSetBit = (i << 5) + trailingZeroCnt(b);
	    }
	}
	return lowestSetBit;
    
private static java.util.RandomgetSecureRandom()

	if (staticRandom == null) {
	    staticRandom = new java.security.SecureRandom();
	}
	return staticRandom;
    
public inthashCode()
Returns the hash code for this BigInteger.

return
hash code for this BigInteger.

	int hashCode = 0;

	for (int i=0; i<mag.length; i++)
	    hashCode = (int)(31*hashCode + (mag[i] & LONG_MASK));

	return hashCode * signum;
    
private static intintArrayCmp(int[] arg1, int[] arg2)

	if (arg1.length < arg2.length)
	    return -1;
	if (arg1.length > arg2.length)
	    return 1;

	// Argument lengths are equal; compare the values
	for (int i=0; i<arg1.length; i++) {
	    long b1 = arg1[i] & LONG_MASK;
	    long b2 = arg2[i] & LONG_MASK;
	    if (b1 < b2)
		return -1;
	    if (b1 > b2)
		return 1;
	}
	return 0;
    
private static intintArrayCmpToLen(int[] arg1, int[] arg2, int len)

	for (int i=0; i<len; i++) {
	    long b1 = arg1[i] & LONG_MASK;
	    long b2 = arg2[i] & LONG_MASK;
	    if (b1 < b2)
		return -1;
	    if (b1 > b2)
		return 1;
	}
	return 0;
    
private intintLength()
Returns the length of the two's complement representation in ints, including space for at least one sign bit.


                    

                           
       
	return bitLength()/32 + 1;
    
public intintValue()
Converts this BigInteger to an int. This conversion is analogous to a narrowing primitive conversion from long to int as defined in the Java Language Specification: if this BigInteger is too big to fit in an int, only the low-order 32 bits are returned. Note that this conversion can lose information about the overall magnitude of the BigInteger value as well as return a result with the opposite sign.

return
this BigInteger converted to an int.

	int result = 0;
	result = getInt(0);
	return result;
    
public booleanisProbablePrime(int certainty)
Returns true if this BigInteger is probably prime, false if it's definitely composite. If certainty is <= 0, true is returned.

param
certainty a measure of the uncertainty that the caller is willing to tolerate: if the call returns true the probability that this BigInteger is prime exceeds (1 - 1/2certainty). The execution time of this method is proportional to the value of this parameter.
return
true if this BigInteger is probably prime, false if it's definitely composite.

	if (certainty <= 0)
	    return true;
	BigInteger w = this.abs();
	if (w.equals(TWO))
	    return true;
	if (!w.testBit(0) || w.equals(ONE))
	    return false;

        return w.primeToCertainty(certainty, null);
    
private static intjacobiSymbol(int p, java.math.BigInteger n)
Computes Jacobi(p,n). Assumes n positive, odd, n>=3.

        if (p == 0)
            return 0;

        // Algorithm and comments adapted from Colin Plumb's C library.
	int j = 1;
	int u = n.mag[n.mag.length-1];

        // Make p positive
        if (p < 0) {
            p = -p;
            int n8 = u & 7;
            if ((n8 == 3) || (n8 == 7))
                j = -j; // 3 (011) or 7 (111) mod 8
        }

	// Get rid of factors of 2 in p
	while ((p & 3) == 0)
            p >>= 2;
	if ((p & 1) == 0) {
            p >>= 1;
            if (((u ^ (u>>1)) & 2) != 0)
                j = -j;	// 3 (011) or 5 (101) mod 8
	}
	if (p == 1)
	    return j;
	// Then, apply quadratic reciprocity
	if ((p & u & 2) != 0)	// p = u = 3 (mod 4)?
	    j = -j;
	// And reduce u mod p
	u = n.mod(BigInteger.valueOf(p)).intValue();

	// Now compute Jacobi(u,p), u < p
	while (u != 0) {
            while ((u & 3) == 0)
                u >>= 2;
            if ((u & 1) == 0) {
                u >>= 1;
                if (((p ^ (p>>1)) & 2) != 0)
                    j = -j;	// 3 (011) or 5 (101) mod 8
            }
            if (u == 1)
                return j;
            // Now both u and p are odd, so use quadratic reciprocity
            assert (u < p);
            int t = u; u = p; p = t;
            if ((u & p & 2) != 0) // u = p = 3 (mod 4)?
                j = -j;
            // Now u >= p, so it can be reduced
            u %= p;
	}
	return 0;
    
int[]javaIncrement(int[] val)

        int lastSum = 0;
        for (int i=val.length-1;  i >= 0 && lastSum == 0; i--)
            lastSum = (val[i] += 1);
        if (lastSum == 0) {
            val = new int[val.length+1];
            val[0] = 1;
        }
        return val;
    
private static java.math.BigIntegerlargePrime(int bitLength, int certainty, java.util.Random rnd)
Find a random number of the specified bitLength that is probably prime. This method is more appropriate for larger bitlengths since it uses a sieve to eliminate most composites before using a more expensive test.


                                            
             
        BigInteger p;
        p = new BigInteger(bitLength, rnd).setBit(bitLength-1);
        p.mag[p.mag.length-1] &= 0xfffffffe;

        // Use a sieve length likely to contain the next prime number
        int searchLen = (bitLength / 20) * 64;
        BitSieve searchSieve = new BitSieve(p, searchLen);
        BigInteger candidate = searchSieve.retrieve(p, certainty, rnd);

        while ((candidate == null) || (candidate.bitLength() != bitLength)) {
            p = p.add(BigInteger.valueOf(2*searchLen));
            if (p.bitLength() != bitLength)
                p = new BigInteger(bitLength, rnd).setBit(bitLength-1);
            p.mag[p.mag.length-1] &= 0xfffffffe;
            searchSieve = new BitSieve(p, searchLen);
            candidate = searchSieve.retrieve(p, certainty, rnd);
        }
        return candidate;
    
private static int[]leftShift(int[] a, int len, int n)
Left shift int array a up to len by n bits. Returns the array that results from the shift since space may have to be reallocated.

        int nInts = n >>> 5;
        int nBits = n&0x1F;
        int bitsInHighWord = bitLen(a[0]);
        
        // If shift can be done without recopy, do so
        if (n <= (32-bitsInHighWord)) {
            primitiveLeftShift(a, len, nBits);
            return a;
        } else { // Array must be resized
            if (nBits <= (32-bitsInHighWord)) {
                int result[] = new int[nInts+len];
                for (int i=0; i<len; i++)
                    result[i] = a[i];
                primitiveLeftShift(result, result.length, nBits);
                return result;
            } else {
                int result[] = new int[nInts+len+1];
                for (int i=0; i<len; i++)
                    result[i] = a[i];
                primitiveRightShift(result, result.length, 32 - nBits);
                return result;
            }
        }
    
public longlongValue()
Converts this BigInteger to a long. This conversion is analogous to a narrowing primitive conversion from long to int as defined in the Java Language Specification: if this BigInteger is too big to fit in a long, only the low-order 64 bits are returned. Note that this conversion can lose information about the overall magnitude of the BigInteger value as well as return a result with the opposite sign.

return
this BigInteger converted to a long.

	long result = 0;

	for (int i=1; i>=0; i--)
	    result = (result << 32) + (getInt(i) & LONG_MASK);
	return result;
    
private static java.math.BigIntegerlucasLehmerSequence(int z, java.math.BigInteger k, java.math.BigInteger n)

        BigInteger d = BigInteger.valueOf(z);
        BigInteger u = ONE; BigInteger u2;
        BigInteger v = ONE; BigInteger v2;

        for (int i=k.bitLength()-2; i>=0; i--) {
            u2 = u.multiply(v).mod(n);

            v2 = v.square().add(d.multiply(u.square())).mod(n);
            if (v2.testBit(0)) {
                v2 = n.subtract(v2);
                v2.signum = - v2.signum;
            }
            v2 = v2.shiftRight(1);

            u = u2; v = v2;
            if (k.testBit(i)) {
                u2 = u.add(v).mod(n);
                if (u2.testBit(0)) {
                    u2 = n.subtract(u2);
                    u2.signum = - u2.signum;
                }
                u2 = u2.shiftRight(1);
                
                v2 = v.add(d.multiply(u)).mod(n);
                if (v2.testBit(0)) {
                    v2 = n.subtract(v2);
                    v2.signum = - v2.signum;
                }
                v2 = v2.shiftRight(1);

                u = u2; v = v2;
            }
        }
        return u;
    
private byte[]magSerializedForm()
Returns the mag array as an array of bytes.

        int bitLen = (mag.length == 0 ? 0 :
                      ((mag.length - 1) << 5) + bitLen(mag[0]));
        int byteLen = (bitLen + 7)/8;
        byte[] result = new byte[byteLen];

        for (int i=byteLen-1, bytesCopied=4, intIndex=mag.length-1, nextInt=0;
             i>=0; i--) {
            if (bytesCopied == 4) {
                nextInt = mag[intIndex--];
                bytesCopied = 1;
            } else {
                nextInt >>>= 8;
                bytesCopied++;
            }
            result[i] = (byte)nextInt;
        }
        return result;
    
private static int[]makePositive(byte[] a)
Takes an array a representing a negative 2's-complement number and returns the minimal (no leading zero bytes) unsigned whose value is -a.

	int keep, k;
        int byteLength = a.length;

	// Find first non-sign (0xff) byte of input
	for (keep=0; keep<byteLength && a[keep]==-1; keep++)
	    ;

        
	/* Allocate output array.  If all non-sign bytes are 0x00, we must
	 * allocate space for one extra output byte. */
	for (k=keep; k<byteLength && a[k]==0; k++)
	    ;

	int extraByte = (k==byteLength) ? 1 : 0;
        int intLength = ((byteLength - keep + extraByte) + 3)/4;
	int result[] = new int[intLength];

	/* Copy one's complement of input into output, leaving extra
	 * byte (if it exists) == 0x00 */
        int b = byteLength - 1;
        for (int i = intLength-1; i >= 0; i--) {
            result[i] = a[b--] & 0xff;
            int numBytesToTransfer = Math.min(3, b-keep+1);
            if (numBytesToTransfer < 0)
                numBytesToTransfer = 0;
            for (int j=8; j <= 8*numBytesToTransfer; j += 8)
                result[i] |= ((a[b--] & 0xff) << j);

            // Mask indicates which bits must be complemented
            int mask = -1 >>> (8*(3-numBytesToTransfer));
            result[i] = ~result[i] & mask;
        }

	// Add one to one's complement to generate two's complement
	for (int i=result.length-1; i>=0; i--) {
            result[i] = (int)((result[i] & LONG_MASK) + 1);
	    if (result[i] != 0)
                break;
        }

	return result;
    
private static int[]makePositive(int[] a)
Takes an array a representing a negative 2's-complement number and returns the minimal (no leading zero ints) unsigned whose value is -a.

	int keep, j;

	// Find first non-sign (0xffffffff) int of input
	for (keep=0; keep<a.length && a[keep]==-1; keep++)
	    ;

	/* Allocate output array.  If all non-sign ints are 0x00, we must
	 * allocate space for one extra output int. */
	for (j=keep; j<a.length && a[j]==0; j++)
	    ;
	int extraInt = (j==a.length ? 1 : 0);
	int result[] = new int[a.length - keep + extraInt];

	/* Copy one's complement of input into output, leaving extra
	 * int (if it exists) == 0x00 */
	for (int i = keep; i<a.length; i++)
	    result[i - keep + extraInt] = ~a[i];

	// Add one to one's complement to generate two's complement
	for (int i=result.length-1; ++result[i]==0; i--)
	    ;

	return result;
    
public java.math.BigIntegermax(java.math.BigInteger val)
Returns the maximum of this BigInteger and val.

param
val value with which the maximum is to be computed.
return
the BigInteger whose value is the greater of this and val. If they are equal, either may be returned.

	return (compareTo(val)>0 ? this : val);
    
public java.math.BigIntegermin(java.math.BigInteger val)
Returns the minimum of this BigInteger and val.

param
val value with which the minimum is to be computed.
return
the BigInteger whose value is the lesser of this BigInteger and val. If they are equal, either may be returned.

	return (compareTo(val)<0 ? this : val);
    
public java.math.BigIntegermod(java.math.BigInteger m)
Returns a BigInteger whose value is (this mod m). This method differs from remainder in that it always returns a non-negative BigInteger.

param
m the modulus.
return
this mod m
throws
ArithmeticException m <= 0
see
#remainder

	if (m.signum <= 0)
	    throw new ArithmeticException("BigInteger: modulus not positive");

	BigInteger result = this.remainder(m);
	return (result.signum >= 0 ? result : result.add(m));
    
private java.math.BigIntegermod2(int p)
Returns a BigInteger whose value is this mod(2**p). Assumes that this BigInteger >= 0 and p > 0.

	if (bitLength() <= p)
	    return this;

	// Copy remaining ints of mag
	int numInts = (p+31)/32;
	int[] mag = new int[numInts];
	for (int i=0; i<numInts; i++)
	    mag[i] = this.mag[i + (this.mag.length - numInts)];

	// Mask out any excess bits
	int excessBits = (numInts << 5) - p;
	mag[0] &= (1L << (32-excessBits)) - 1;

	return (mag[0]==0 ? new BigInteger(1, mag) : new BigInteger(mag, 1));
    
public java.math.BigIntegermodInverse(java.math.BigInteger m)
Returns a BigInteger whose value is (this-1 mod m).

param
m the modulus.
return
this-1 mod m.
throws
ArithmeticException m <= 0, or this BigInteger has no multiplicative inverse mod m (that is, this BigInteger is not relatively prime to m).

	if (m.signum != 1)
	    throw new ArithmeticException("BigInteger: modulus not positive");

        if (m.equals(ONE))
            return ZERO;

	// Calculate (this mod m)
        BigInteger modVal = this;
        if (signum < 0 || (intArrayCmp(mag, m.mag) >= 0))
            modVal = this.mod(m);

        if (modVal.equals(ONE))
            return ONE;

        MutableBigInteger a = new MutableBigInteger(modVal);
        MutableBigInteger b = new MutableBigInteger(m);
  
        MutableBigInteger result = a.mutableModInverse(b);  
        return new BigInteger(result, 1);
    
public java.math.BigIntegermodPow(java.math.BigInteger exponent, java.math.BigInteger m)
Returns a BigInteger whose value is (thisexponent mod m). (Unlike pow, this method permits negative exponents.)

param
exponent the exponent.
param
m the modulus.
return
thisexponent mod m
throws
ArithmeticException m <= 0
see
#modInverse

	if (m.signum <= 0)
	    throw new ArithmeticException("BigInteger: modulus not positive");

	// Trivial cases
	if (exponent.signum == 0)
            return (m.equals(ONE) ? ZERO : ONE);

        if (this.equals(ONE))
            return (m.equals(ONE) ? ZERO : ONE);

        if (this.equals(ZERO) && exponent.signum >= 0)
            return ZERO;

        if (this.equals(negConst[1]) && (!exponent.testBit(0)))
            return (m.equals(ONE) ? ZERO : 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
	    result = base.oddModPow(exponent, m);
	} else {
	    /*
	     * Even modulus.  Tear it into an "odd part" (m1) and power of two
             * (m2), 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

            // Calculate new base from m1
            BigInteger base2 = (this.signum < 0 || this.compareTo(m1) >= 0
                                ? this.mod(m1) : this);

            // Caculate (base ** exponent) mod m1.
            BigInteger a1 = (m1.equals(ONE) ? ZERO :
                             base2.oddModPow(exponent, m1));

	    // Calculate (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);
    
private java.math.BigIntegermodPow2(java.math.BigInteger exponent, int p)
Returns a BigInteger whose value is (this ** exponent) mod (2**p)

	/*
	 * Perform exponentiation using repeated squaring trick, chopping off
	 * high order bits as indicated by modulus.
	 */
	BigInteger result = valueOf(1);
	BigInteger baseToPow2 = this.mod2(p);
        int expOffset = 0;

        int limit = exponent.bitLength();

        if (this.testBit(0))
           limit = (p-1) < limit ? (p-1) : limit;

	while (expOffset < limit) {
	    if (exponent.testBit(expOffset))
		result = result.multiply(baseToPow2).mod2(p);
            expOffset++;
	    if (expOffset < limit)
                baseToPow2 = baseToPow2.square().mod2(p);
	}

	return result;
    
private static int[]montReduce(int[] n, int[] mod, int mlen, int inv)
Montgomery reduce n, modulo mod. This reduces modulo mod and divides by 2^(32*mlen). Adapted from Colin Plumb's C library.

        int c=0;
        int len = mlen;
        int offset=0;

        do {
            int nEnd = n[n.length-1-offset];
            int carry = mulAdd(n, mod, offset, mlen, inv * nEnd);
            c += addOne(n, offset, mlen, carry);
            offset++;
        } while(--len > 0);
        
        while(c>0)
            c += subN(n, mod, mlen);

        while (intArrayCmpToLen(n, mod, mlen) >= 0)
            subN(n, mod, mlen);

        return n;
    
static intmulAdd(int[] out, int[] in, int offset, int len, int k)
Multiply an array by one word k and add to result, return the carry

        long kLong = k & LONG_MASK;
        long carry = 0;

        offset = out.length-offset - 1;
        for (int j=len-1; j >= 0; j--) {
            long product = (in[j] & LONG_MASK) * kLong +
                           (out[offset] & LONG_MASK) + carry;
            out[offset--] = (int)product;
            carry = product >>> 32;
        }
        return (int)carry;
    
public java.math.BigIntegermultiply(java.math.BigInteger val)
Returns a BigInteger whose value is (this * val).

param
val value to be multiplied by this BigInteger.
return
this * val

        if (signum == 0 || val.signum==0)
	    return ZERO;
        
        int[] result = multiplyToLen(mag, mag.length, 
                                     val.mag, val.mag.length, null);
        result = trustedStripLeadingZeroInts(result);
        return new BigInteger(result, signum*val.signum);
    
private int[]multiplyToLen(int[] x, int xlen, int[] y, int ylen, int[] z)
Multiplies int arrays x and y to the specified lengths and places the result into z.

        int xstart = xlen - 1;
        int ystart = ylen - 1;

        if (z == null || z.length < (xlen+ ylen))
            z = new int[xlen+ylen];

        long carry = 0;
        for (int j=ystart, k=ystart+1+xstart; j>=0; j--, k--) {
            long product = (y[j] & LONG_MASK) *
                           (x[xstart] & LONG_MASK) + carry;
            z[k] = (int)product;
            carry = product >>> 32;
        }
        z[xstart] = (int)carry;

        for (int i = xstart-1; i >= 0; i--) {
            carry = 0;
            for (int j=ystart, k=ystart+1+i; j>=0; j--, k--) {
                long product = (y[j] & LONG_MASK) * 
                               (x[i] & LONG_MASK) + 
                               (z[k] & LONG_MASK) + carry;
                z[k] = (int)product;
                carry = product >>> 32;
            }
            z[i] = (int)carry;
        }
        return z;
    
public java.math.BigIntegernegate()
Returns a BigInteger whose value is (-this).

return
-this

	return new BigInteger(this.mag, -this.signum);
    
public java.math.BigIntegernextProbablePrime()
Returns the first integer greater than this BigInteger that is probably prime. The probability that the number returned by this method is composite does not exceed 2-100. This method will never skip over a prime when searching: if it returns p, there is no prime q such that this < q < p.

return
the first integer greater than this BigInteger that is probably prime.
throws
ArithmeticException this < 0.
since
1.5

        if (this.signum < 0)
            throw new ArithmeticException("start < 0: " + this);
        
        // Handle trivial cases
        if ((this.signum == 0) || this.equals(ONE))
            return TWO;

        BigInteger result = this.add(ONE);

        // Fastpath for small numbers
        if (result.bitLength() < SMALL_PRIME_THRESHOLD) {
 
            // Ensure an odd number
            if (!result.testBit(0))
                result = result.add(ONE);

            while(true) {
                // Do cheap "pre-test" if applicable
                if (result.bitLength() > 6) {
                    long r = result.remainder(SMALL_PRIME_PRODUCT).longValue();
                    if ((r%3==0)  || (r%5==0)  || (r%7==0)  || (r%11==0) || 
                        (r%13==0) || (r%17==0) || (r%19==0) || (r%23==0) || 
                        (r%29==0) || (r%31==0) || (r%37==0) || (r%41==0)) {
                        result = result.add(TWO);
                        continue; // Candidate is composite; try another
                    }
                }
            
                // All candidates of bitLength 2 and 3 are prime by this point
                if (result.bitLength() < 4)
                    return result;

                // The expensive test
                if (result.primeToCertainty(DEFAULT_PRIME_CERTAINTY, null))
                    return result;

                result = result.add(TWO);
            }
        }

        // Start at previous even number
        if (result.testBit(0))
            result = result.subtract(ONE);

        // Looking for the next large prime
        int searchLen = (result.bitLength() / 20) * 64;

        while(true) {
           BitSieve searchSieve = new BitSieve(result, searchLen);
           BigInteger candidate = searchSieve.retrieve(result,
						 DEFAULT_PRIME_CERTAINTY, null);
           if (candidate != null)
               return candidate;
           result = result.add(BigInteger.valueOf(2 * searchLen));
        }
    
public java.math.BigIntegernot()
Returns a BigInteger whose value is (~this). (This method returns a negative value if and only if this BigInteger is non-negative.)

return
~this

	int[] result = new int[intLength()];
	for (int i=0; i<result.length; i++)
	    result[i] = (int) ~getInt(result.length-i-1);

	return valueOf(result);
    
private java.math.BigIntegeroddModPow(java.math.BigInteger y, java.math.BigInteger z)
Returns a BigInteger whose value is x to the power of y mod z. Assumes: z is odd && x < z.

 // Sentinel

                               
          
    /*
     * The algorithm is adapted from Colin Plumb's C library.
     *
     * The window algorithm:
     * The idea is to keep a running product of b1 = n^(high-order bits of exp)
     * and then keep appending exponent bits to it.  The following patterns
     * apply to a 3-bit window (k = 3):
     * To append   0: square
     * To append   1: square, multiply by n^1
     * To append  10: square, multiply by n^1, square
     * To append  11: square, square, multiply by n^3
     * To append 100: square, multiply by n^1, square, square
     * To append 101: square, square, square, multiply by n^5
     * To append 110: square, square, multiply by n^3, square
     * To append 111: square, square, square, multiply by n^7
     *
     * Since each pattern involves only one multiply, the longer the pattern
     * the better, except that a 0 (no multiplies) can be appended directly.
     * We precompute a table of odd powers of n, up to 2^k, and can then
     * multiply k bits of exponent at a time.  Actually, assuming random
     * exponents, there is on average one zero bit between needs to
     * multiply (1/2 of the time there's none, 1/4 of the time there's 1,
     * 1/8 of the time, there's 2, 1/32 of the time, there's 3, etc.), so
     * you have to do one multiply per k+1 bits of exponent.
     *
     * The loop walks down the exponent, squaring the result buffer as
     * it goes.  There is a wbits+1 bit lookahead buffer, buf, that is
     * filled with the upcoming exponent bits.  (What is read after the
     * end of the exponent is unimportant, but it is filled with zero here.)
     * When the most-significant bit of this buffer becomes set, i.e.
     * (buf & tblmask) != 0, we have to decide what pattern to multiply
     * by, and when to do it.  We decide, remember to do it in future
     * after a suitable number of squarings have passed (e.g. a pattern
     * of "100" in the buffer requires that we multiply by n^1 immediately;
     * a pattern of "110" calls for multiplying by n^3 after one more
     * squaring), clear the buffer, and continue.
     *
     * When we start, there is one more optimization: the result buffer
     * is implcitly one, so squaring it or multiplying by it can be
     * optimized away.  Further, if we start with a pattern like "100"
     * in the lookahead window, rather than placing n into the buffer
     * and then starting to square it, we have already computed n^2
     * to compute the odd-powers table, so we can place that into
     * the buffer and save a squaring.
     *
     * This means that if you have a k-bit window, to compute n^z,
     * where z is the high k bits of the exponent, 1/2 of the time
     * it requires no squarings.  1/4 of the time, it requires 1
     * squaring, ... 1/2^(k-1) of the time, it reqires k-2 squarings.
     * And the remaining 1/2^(k-1) of the time, the top k bits are a
     * 1 followed by k-1 0 bits, so it again only requires k-2
     * squarings, not k-1.  The average of these is 1.  Add that
     * to the one squaring we have to do to compute the table,
     * and you'll see that a k-bit window saves k-2 squarings
     * as well as reducing the multiplies.  (It actually doesn't
     * hurt in the case k = 1, either.)
     */
        // Special case for exponent of one
        if (y.equals(ONE))
            return this;

        // Special case for base of zero
        if (signum==0)
            return ZERO;

        int[] base = (int[])mag.clone();
        int[] exp = y.mag;
        int[] mod = z.mag;
        int modLen = mod.length;

        // Select an appropriate window size
        int wbits = 0;
        int ebits = bitLength(exp, exp.length);
	// if exponent is 65537 (0x10001), use minimum window size
	if ((ebits != 17) || (exp[0] != 65537)) {
	    while (ebits > bnExpModThreshTable[wbits]) {
		wbits++;
	    }
	}

        // Calculate appropriate table size
        int tblmask = 1 << wbits;
        
        // Allocate table for precomputed odd powers of base in Montgomery form
        int[][] table = new int[tblmask][];
        for (int i=0; i<tblmask; i++)
            table[i] = new int[modLen];

        // Compute the modular inverse
        int inv = -MutableBigInteger.inverseMod32(mod[modLen-1]);

        // Convert base to Montgomery form
        int[] a = leftShift(base, base.length, modLen << 5);

        MutableBigInteger q = new MutableBigInteger(),
                          r = new MutableBigInteger(),
                          a2 = new MutableBigInteger(a),
                          b2 = new MutableBigInteger(mod);

        a2.divide(b2, q, r);
        table[0] = r.toIntArray();

        // Pad table[0] with leading zeros so its length is at least modLen
        if (table[0].length < modLen) {
           int offset = modLen - table[0].length;
           int[] t2 = new int[modLen];
           for (int i=0; i<table[0].length; i++)
               t2[i+offset] = table[0][i];
           table[0] = t2;
        }

        // Set b to the square of the base
        int[] b = squareToLen(table[0], modLen, null);
        b = montReduce(b, mod, modLen, inv);

        // Set t to high half of b
        int[] t = new int[modLen];
        for(int i=0; i<modLen; i++)
            t[i] = b[i];

        // Fill in the table with odd powers of the base        
        for (int i=1; i<tblmask; i++) {
            int[] prod = multiplyToLen(t, modLen, table[i-1], modLen, null);
            table[i] = montReduce(prod, mod, modLen, inv);
        }

        // Pre load the window that slides over the exponent
        int bitpos = 1 << ((ebits-1) & (32-1));
        
        int buf = 0;
        int elen = exp.length;
        int eIndex = 0;
	for (int i = 0; i <= wbits; i++) {
            buf = (buf << 1) | (((exp[eIndex] & bitpos) != 0)?1:0);
            bitpos >>>= 1;
            if (bitpos == 0) {
                eIndex++;
                bitpos = 1 << (32-1);
                elen--;
            }
	}

        int multpos = ebits;

        // The first iteration, which is hoisted out of the main loop
        ebits--;
        boolean isone = true;

	multpos = ebits - wbits;
	while ((buf & 1) == 0) {
            buf >>>= 1;
            multpos++;
	}

	int[] mult = table[buf >>> 1];

	buf = 0;
        if (multpos == ebits)
	    isone = false;

        // The main loop
        while(true) {
            ebits--;
            // Advance the window
            buf <<= 1;

            if (elen != 0) {
                buf |= ((exp[eIndex] & bitpos) != 0) ? 1 : 0;
                bitpos >>>= 1;
                if (bitpos == 0) {
                    eIndex++;
                    bitpos = 1 << (32-1);
                    elen--;
                }
            }

            // Examine the window for pending multiplies
            if ((buf & tblmask) != 0) {
                multpos = ebits - wbits;
                while ((buf & 1) == 0) {
                    buf >>>= 1;
                    multpos++;
                }
                mult = table[buf >>> 1];
                buf = 0;
            }

            // Perform multiply
            if (ebits == multpos) {
                if (isone) {
                    b = (int[])mult.clone();
                    isone = false;
                } else {
                    t = b;
                    a = multiplyToLen(t, modLen, mult, modLen, a);
                    a = montReduce(a, mod, modLen, inv);
                    t = a; a = b; b = t;
                }
            }

            // Check if done
            if (ebits == 0)
                break;

            // Square the input
            if (!isone) {
                t = b;
                a = squareToLen(t, modLen, a);
                a = montReduce(a, mod, modLen, inv);
                t = a; a = b; b = t;
            }
	}

        // Convert result out of Montgomery form and return
        int[] t2 = new int[2*modLen];
        for(int i=0; i<modLen; i++)
            t2[i+modLen] = b[i];

        b = montReduce(t2, mod, modLen, inv);

        t2 = new int[modLen];
        for(int i=0; i<modLen; i++)
            t2[i] = b[i];
           
        return new BigInteger(1, t2);
    
public java.math.BigIntegeror(java.math.BigInteger val)
Returns a BigInteger whose value is (this | val). (This method returns a negative BigInteger if and only if either this or val is negative.)

param
val value to be OR'ed with this BigInteger.
return
this | val

	int[] result = new int[Math.max(intLength(), val.intLength())];
	for (int i=0; i<result.length; i++)
	    result[i] = (int) (getInt(result.length-i-1)
				| val.getInt(result.length-i-1));

	return valueOf(result);
    
private intparseInt(char[] source, int start, int end)

        int result = Character.digit(source[start++], 10);
        if (result == -1)
            throw new NumberFormatException(new String(source));

        for (int index = start; index<end; index++) {
            int nextVal = Character.digit(source[index], 10);
            if (nextVal == -1)
                throw new NumberFormatException(new String(source));
            result = 10*result + nextVal;
        }

        return result;
    
private booleanpassesLucasLehmer()
Returns true iff this BigInteger is a Lucas-Lehmer probable prime. The following assumptions are made: This BigInteger is a positive, odd number.

        BigInteger thisPlusOne = this.add(ONE);

        // Step 1
        int d = 5;
        while (jacobiSymbol(d, this) != -1) {
            // 5, -7, 9, -11, ...
            d = (d<0) ? Math.abs(d)+2 : -(d+2);
        }
        
        // Step 2
        BigInteger u = lucasLehmerSequence(d, thisPlusOne, this);

        // Step 3
        return u.mod(this).equals(ZERO);
    
private booleanpassesMillerRabin(int iterations, java.util.Random rnd)
Returns true iff this BigInteger passes the specified number of Miller-Rabin tests. This test is taken from the DSA spec (NIST FIPS 186-2). The following assumptions are made: This BigInteger is a positive, odd number greater than 2. iterations<=50.

	// Find a and m such that m is odd and this == 1 + 2**a * m
        BigInteger thisMinusOne = this.subtract(ONE);
	BigInteger m = thisMinusOne;
	int a = m.getLowestSetBit();
	m = m.shiftRight(a);

	// Do the tests
	if (rnd == null) {
	    rnd = getSecureRandom();
	}
	for (int i=0; i<iterations; i++) {
	    // Generate a uniform random on (1, this)
	    BigInteger b;
	    do {
		b = new BigInteger(this.bitLength(), rnd);
	    } while (b.compareTo(ONE) <= 0 || b.compareTo(this) >= 0);

	    int j = 0;
	    BigInteger z = b.modPow(m, this);
	    while(!((j==0 && z.equals(ONE)) || z.equals(thisMinusOne))) {
		if (j>0 && z.equals(ONE) || ++j==a)
		    return false;
		z = z.modPow(TWO, this);
	    }
	}
	return true;
    
public java.math.BigIntegerpow(int exponent)
Returns a BigInteger whose value is (thisexponent). Note that exponent is an integer rather than a BigInteger.

param
exponent exponent to which this BigInteger is to be raised.
return
thisexponent
throws
ArithmeticException exponent is negative. (This would cause the operation to yield a non-integer value.)

	if (exponent < 0)
	    throw new ArithmeticException("Negative exponent");
	if (signum==0)
	    return (exponent==0 ? ONE : this);

	// Perform exponentiation using repeated squaring trick
        int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1);
	int[] baseToPow2 = this.mag;
        int[] result = {1};

	while (exponent != 0) {
	    if ((exponent & 1)==1) {
		result = multiplyToLen(result, result.length, 
                                       baseToPow2, baseToPow2.length, null);
		result = trustedStripLeadingZeroInts(result);
	    }
	    if ((exponent >>>= 1) != 0) {
                baseToPow2 = squareToLen(baseToPow2, baseToPow2.length, null);
		baseToPow2 = trustedStripLeadingZeroInts(baseToPow2);
	    }
	}
	return new BigInteger(result, newSign);
    
booleanprimeToCertainty(int certainty, java.util.Random random)
Returns true if this BigInteger is probably prime, false if it's definitely composite. This method assumes bitLength > 2.

param
certainty a measure of the uncertainty that the caller is willing to tolerate: if the call returns true the probability that this BigInteger is prime exceeds (1 - 1/2certainty). The execution time of this method is proportional to the value of this parameter.
return
true if this BigInteger is probably prime, false if it's definitely composite.

        int rounds = 0;
        int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2;

        // The relationship between the certainty and the number of rounds
        // we perform is given in the draft standard ANSI X9.80, "PRIME
        // NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES".
        int sizeInBits = this.bitLength();
        if (sizeInBits < 100) {
            rounds = 50;
            rounds = n < rounds ? n : rounds;
            return passesMillerRabin(rounds, random);
        }

        if (sizeInBits < 256) {
            rounds = 27;
        } else if (sizeInBits < 512) {
            rounds = 15;
        } else if (sizeInBits < 768) {
            rounds = 8;
        } else if (sizeInBits < 1024) {
            rounds = 4;
        } else {
            rounds = 2;
        }
        rounds = n < rounds ? n : rounds;

        return passesMillerRabin(rounds, random) && passesLucasLehmer();
    
static voidprimitiveLeftShift(int[] a, int len, int n)

        if (len == 0 || n == 0)
            return;

        int n2 = 32 - n;
        for (int i=0, c=a[i], m=i+len-1; i<m; i++) {
            int b = c;
            c = a[i+1];
            a[i] = (b << n) | (c >>> n2);
        }
        a[len-1] <<= n;
    
static voidprimitiveRightShift(int[] a, int len, int n)

        int n2 = 32 - n;
        for (int i=len-1, c=a[i]; i>0; i--) {
            int b = c;
            c = a[i-1];
            a[i] = (c << n2) | (b >>> n);
        }
        a[0] >>>= n;
    
public static java.math.BigIntegerprobablePrime(int bitLength, java.util.Random rnd)
Returns a positive BigInteger that is probably prime, with the specified bitLength. The probability that a BigInteger returned by this method is composite does not exceed 2-100.

param
bitLength bitLength of the returned BigInteger.
param
rnd source of random bits used to select candidates to be tested for primality.
return
a BigInteger of bitLength bits that is probably prime
throws
ArithmeticException bitLength < 2.
see
#bitLength()
since
1.4


                                                    	                                    
           
	if (bitLength < 2)
	    throw new ArithmeticException("bitLength < 2");

        // The cutoff of 95 was chosen empirically for best performance
        return (bitLength < SMALL_PRIME_THRESHOLD ?
                smallPrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd) :
                largePrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd));
    
private static byte[]randomBits(int numBits, java.util.Random rnd)

	if (numBits < 0)
	    throw new IllegalArgumentException("numBits must be non-negative");
	int numBytes = (int)(((long)numBits+7)/8); // avoid overflow
	byte[] randomBits = new byte[numBytes];

	// Generate random bytes and mask out any excess bits
	if (numBytes > 0) {
	    rnd.nextBytes(randomBits);
	    int excessBits = 8*numBytes - numBits;
	    randomBits[0] &= (1 << (8-excessBits)) - 1;
	}
	return randomBits;
    
private voidreadObject(java.io.ObjectInputStream s)
Reconstitute the BigInteger instance from a stream (that is, deserialize it). The magnitude is read in as an array of bytes for historical reasons, but it is converted to an array of ints and the byte array is discarded.


                                                
       
           
        /*
         * In order to maintain compatibility with previous serialized forms,
         * the magnitude of a BigInteger is serialized as an array of bytes.
         * The magnitude field is used as a temporary store for the byte array
         * that is deserialized. The cached computation fields should be
         * transient but are serialized for compatibility reasons.
         */

        // prepare to read the alternate persistent fields
        ObjectInputStream.GetField fields = s.readFields();
            
        // Read the alternate persistent fields that we care about
        signum = (int)fields.get("signum", -2);
        byte[] magnitude = (byte[])fields.get("magnitude", null);

        // Validate signum
	if (signum < -1 || signum > 1) {
            String message = "BigInteger: Invalid signum value";
            if (fields.defaulted("signum"))
                message = "BigInteger: Signum not present in stream";
	    throw new java.io.StreamCorruptedException(message);
        }
	if ((magnitude.length==0) != (signum==0)) {
            String message = "BigInteger: signum-magnitude mismatch";
            if (fields.defaulted("magnitude"))
                message = "BigInteger: Magnitude not present in stream";
	    throw new java.io.StreamCorruptedException(message);
        }

        // Set "cached computation" fields to their initial values
        bitCount = bitLength = -1;
        lowestSetBit = firstNonzeroByteNum = firstNonzeroIntNum = -2;

        // Calculate mag field from magnitude and discard magnitude
	mag = stripLeadingZeroBytes(magnitude);
    
public java.math.BigIntegerremainder(java.math.BigInteger val)
Returns a BigInteger whose value is (this % val).

param
val value by which this BigInteger is to be divided, and the remainder computed.
return
this % val
throws
ArithmeticException val==0

        MutableBigInteger q = new MutableBigInteger(),
                          r = new MutableBigInteger(),
                          a = new MutableBigInteger(this.mag),
                          b = new MutableBigInteger(val.mag);

        a.divide(b, q, r);
        return new BigInteger(r, this.signum);
    
public java.math.BigIntegersetBit(int n)
Returns a BigInteger whose value is equivalent to this BigInteger with the designated bit set. (Computes (this | (1<<n)).)

param
n index of bit to set.
return
this | (1<<n)
throws
ArithmeticException n is negative.

	if (n<0)
	    throw new ArithmeticException("Negative bit address");

	int intNum = n/32;
	int[] result = new int[Math.max(intLength(), intNum+2)];

	for (int i=0; i<result.length; i++)
	    result[result.length-i-1] = getInt(i);

	result[result.length-intNum-1] |= (1 << (n%32));

	return valueOf(result);
    
public java.math.BigIntegershiftLeft(int n)
Returns a BigInteger whose value is (this << n). The shift distance, n, may be negative, in which case this method performs a right shift. (Computes floor(this * 2n).)

param
n shift distance, in bits.
return
this << n
see
#shiftRight

        if (signum == 0)
            return ZERO;
        if (n==0)
            return this;
        if (n<0)
            return shiftRight(-n);

        int nInts = n >>> 5;
        int nBits = n & 0x1f;
        int magLen = mag.length;
        int newMag[] = null;

        if (nBits == 0) {
            newMag = new int[magLen + nInts];
            for (int i=0; i<magLen; i++)
                newMag[i] = mag[i];
        } else {
            int i = 0;
            int nBits2 = 32 - nBits;
            int highBits = mag[0] >>> nBits2;
            if (highBits != 0) {
                newMag = new int[magLen + nInts + 1];
                newMag[i++] = highBits;
            } else {
                newMag = new int[magLen + nInts];
            }
            int j=0;
            while (j < magLen-1)
                newMag[i++] = mag[j++] << nBits | mag[j] >>> nBits2;
            newMag[i] = mag[j] << nBits;
        }

        return new BigInteger(newMag, signum);
    
public java.math.BigIntegershiftRight(int n)
Returns a BigInteger whose value is (this >> n). Sign extension is performed. The shift distance, n, may be negative, in which case this method performs a left shift. (Computes floor(this / 2n).)

param
n shift distance, in bits.
return
this >> n
see
#shiftLeft

        if (n==0)
            return this;
        if (n<0)
            return shiftLeft(-n);

        int nInts = n >>> 5;
        int nBits = n & 0x1f;
        int magLen = mag.length;
        int newMag[] = null;

        // Special case: entire contents shifted off the end
        if (nInts >= magLen)
            return (signum >= 0 ? ZERO : negConst[1]);

        if (nBits == 0) {
            int newMagLen = magLen - nInts;
            newMag = new int[newMagLen];
            for (int i=0; i<newMagLen; i++)
                newMag[i] = mag[i];
        } else {
            int i = 0;
            int highBits = mag[0] >>> nBits;
            if (highBits != 0) {
                newMag = new int[magLen - nInts];
                newMag[i++] = highBits;
            } else {
                newMag = new int[magLen - nInts -1];
            }

            int nBits2 = 32 - nBits;
            int j=0;
            while (j < magLen - nInts - 1)
                newMag[i++] = (mag[j++] << nBits2) | (mag[j] >>> nBits);
        }

        if (signum < 0) {
            // Find out whether any one-bits were shifted off the end.
            boolean onesLost = false;
            for (int i=magLen-1, j=magLen-nInts; i>=j && !onesLost; i--)
                onesLost = (mag[i] != 0);
            if (!onesLost && nBits != 0)
                onesLost = (mag[magLen - nInts - 1] << (32 - nBits) != 0);

            if (onesLost)
                newMag = javaIncrement(newMag);
        }

        return new BigInteger(newMag, signum);
    
private intsignBit()

	return (signum < 0 ? 1 : 0);
    
private intsignInt()

	return (int) (signum < 0 ? -1 : 0);
    
public intsignum()
Returns the signum function of this BigInteger.

return
-1, 0 or 1 as the value of this BigInteger is negative, zero or positive.

	return this.signum;
    
private static java.math.BigIntegersmallPrime(int bitLength, int certainty, java.util.Random rnd)
Find a random number of the specified bitLength that is probably prime. This method is used for smaller primes, its performance degrades on larger bitlengths. This method assumes bitLength > 1.

        int magLen = (bitLength + 31) >>> 5;
        int temp[] = new int[magLen];
        int highBit = 1 << ((bitLength+31) & 0x1f);  // High bit of high int
        int highMask = (highBit << 1) - 1;  // Bits to keep in high int

        while(true) {
            // Construct a candidate
            for (int i=0; i<magLen; i++)
                temp[i] = rnd.nextInt();
            temp[0] = (temp[0] & highMask) | highBit;  // Ensure exact length
            if (bitLength > 2)
                temp[magLen-1] |= 1;  // Make odd if bitlen > 2

            BigInteger p = new BigInteger(temp, 1);

            // Do cheap "pre-test" if applicable
            if (bitLength > 6) {
                long r = p.remainder(SMALL_PRIME_PRODUCT).longValue();
                if ((r%3==0)  || (r%5==0)  || (r%7==0)  || (r%11==0) || 
                    (r%13==0) || (r%17==0) || (r%19==0) || (r%23==0) || 
                    (r%29==0) || (r%31==0) || (r%37==0) || (r%41==0))
                    continue; // Candidate is composite; try another
            }
            
            // All candidates of bitLength 2 and 3 are prime by this point
            if (bitLength < 4)
                return p;

            // Do expensive test if we survive pre-test (or it's inapplicable)
            if (p.primeToCertainty(certainty, rnd))
                return p;
        }
    
private java.math.BigIntegersquare()
Returns a BigInteger whose value is (this2).

return
this2

        if (signum == 0)
	    return ZERO;
        int[] z = squareToLen(mag, mag.length, null);
        return new BigInteger(trustedStripLeadingZeroInts(z), 1);
    
private static final int[]squareToLen(int[] x, int len, int[] z)
Squares the contents of the int array x. The result is placed into the int array z. The contents of x are not changed.

        /*
         * The algorithm used here is adapted from Colin Plumb's C library.
         * Technique: Consider the partial products in the multiplication
         * of "abcde" by itself:
         *
         *               a  b  c  d  e
         *            *  a  b  c  d  e
         *          ==================
         *              ae be ce de ee
         *           ad bd cd dd de
         *        ac bc cc cd ce
         *     ab bb bc bd be
         *  aa ab ac ad ae
         *
         * Note that everything above the main diagonal:
         *              ae be ce de = (abcd) * e
         *           ad bd cd       = (abc) * d
         *        ac bc             = (ab) * c
         *     ab                   = (a) * b
         *
         * is a copy of everything below the main diagonal:
         *                       de
         *                 cd ce
         *           bc bd be
         *     ab ac ad ae
         *
         * Thus, the sum is 2 * (off the diagonal) + diagonal.
         *
         * This is accumulated beginning with the diagonal (which
         * consist of the squares of the digits of the input), which is then
         * divided by two, the off-diagonal added, and multiplied by two
         * again.  The low bit is simply a copy of the low bit of the
         * input, so it doesn't need special care.
         */
        int zlen = len << 1;
        if (z == null || z.length < zlen)
            z = new int[zlen];
        
        // Store the squares, right shifted one bit (i.e., divided by 2)
        int lastProductLowWord = 0;
        for (int j=0, i=0; j<len; j++) {
            long piece = (x[j] & LONG_MASK);
            long product = piece * piece;
            z[i++] = (lastProductLowWord << 31) | (int)(product >>> 33);
            z[i++] = (int)(product >>> 1);
            lastProductLowWord = (int)product;
        }

        // Add in off-diagonal sums
        for (int i=len, offset=1; i>0; i--, offset+=2) {
            int t = x[i-1];
            t = mulAdd(z, x, offset, i-1, t);
            addOne(z, offset-1, i, t);
        }

        // Shift back up and set low bit
        primitiveLeftShift(z, zlen, 1);
        z[zlen-1] |= x[len-1] & 1;

        return z;
    
private static int[]stripLeadingZeroBytes(byte[] a)
Returns a copy of the input array stripped of any leading zero bytes.

        int byteLength = a.length;
	int keep;

	// Find first nonzero byte
	for (keep=0; keep<a.length && a[keep]==0; keep++)
	    ;

	// Allocate new array and copy relevant part of input array
        int intLength = ((byteLength - keep) + 3)/4;
	int[] result = new int[intLength];
        int b = byteLength - 1;
        for (int i = intLength-1; i >= 0; i--) {
            result[i] = a[b--] & 0xff;
            int bytesRemaining = b - keep + 1;
            int bytesToTransfer = Math.min(3, bytesRemaining);
            for (int j=8; j <= 8*bytesToTransfer; j += 8)
                result[i] |= ((a[b--] & 0xff) << j);
        }
        return result;
    
private static int[]stripLeadingZeroInts(int[] val)
Returns a copy of the input array stripped of any leading zero bytes.

        int byteLength = val.length;
	int keep;

	// Find first nonzero byte
        for (keep=0; keep<val.length && val[keep]==0; keep++)
            ;

        int result[] = new int[val.length - keep];
        for(int i=0; i<val.length - keep; i++)
            result[i] = val[keep+i];

        return result;
    
private static intsubN(int[] a, int[] b, int len)
Subtracts two numbers of same length, returning borrow.

        long sum = 0;

        while(--len >= 0) {
            sum = (a[len] & LONG_MASK) - 
                 (b[len] & LONG_MASK) + (sum >> 32);
            a[len] = (int)sum;
        }

        return (int)(sum >> 32);
    
public java.math.BigIntegersubtract(java.math.BigInteger val)
Returns a BigInteger whose value is (this - val).

param
val value to be subtracted from this BigInteger.
return
this - val

        int[] resultMag;
	if (val.signum == 0)
            return this;
	if (signum == 0)
	    return val.negate();
	if (val.signum != signum)
            return new BigInteger(add(mag, val.mag), signum);

        int cmp = intArrayCmp(mag, val.mag);
        if (cmp==0)
            return ZERO;
        resultMag = (cmp>0 ? subtract(mag, val.mag)
                           : subtract(val.mag, mag));
        resultMag = trustedStripLeadingZeroInts(resultMag);
        return new BigInteger(resultMag, cmp*signum);
    
private static int[]subtract(int[] big, int[] little)
Subtracts the contents of the second int arrays (little) from the first (big). The first int array (big) must represent a larger number than the second. This method allocates the space necessary to hold the answer.

        int bigIndex = big.length;
        int result[] = new int[bigIndex];
        int littleIndex = little.length;
        long difference = 0;

        // Subtract common parts of both numbers
        while(littleIndex > 0) {
            difference = (big[--bigIndex] & LONG_MASK) - 
                         (little[--littleIndex] & LONG_MASK) +
                         (difference >> 32);
            result[bigIndex] = (int)difference;
        }

        // Subtract remainder of longer number while borrow propagates
        boolean borrow = (difference >> 32 != 0);
        while (bigIndex > 0 && borrow)
            borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);

        // Copy remainder of longer number
        while (bigIndex > 0)
            result[--bigIndex] = big[bigIndex];

        return result;
    
public booleantestBit(int n)
Returns true if and only if the designated bit is set. (Computes ((this & (1<<n)) != 0).)

param
n index of bit to test.
return
true if and only if the designated bit is set.
throws
ArithmeticException n is negative.

	if (n<0)
	    throw new ArithmeticException("Negative bit address");

	return (getInt(n/32) & (1 << (n%32))) != 0;
    
public byte[]toByteArray()
Returns a byte array containing the two's-complement representation of this BigInteger. The byte array will be in big-endian byte-order: the most significant byte is in the zeroth element. The array will contain the minimum number of bytes required to represent this BigInteger, including at least one sign bit, which is (ceil((this.bitLength() + 1)/8)). (This representation is compatible with the {@link #BigInteger(byte[]) (byte[])} constructor.)

return
a byte array containing the two's-complement representation of this BigInteger.
see
#BigInteger(byte[])

        int byteLen = bitLength()/8 + 1;
        byte[] byteArray = new byte[byteLen];

        for (int i=byteLen-1, bytesCopied=4, nextInt=0, intIndex=0; i>=0; i--) {
            if (bytesCopied == 4) {
                nextInt = getInt(intIndex++);
                bytesCopied = 1;
            } else {
                nextInt >>>= 8;
                bytesCopied++;
            }
            byteArray[i] = (byte)nextInt;
        }
        return byteArray;
    
public java.lang.StringtoString(int radix)
Returns the String representation of this BigInteger in the given radix. If the radix is outside the range from {@link Character#MIN_RADIX} to {@link Character#MAX_RADIX} inclusive, it will default to 10 (as is the case for Integer.toString). The digit-to-character mapping provided by Character.forDigit is used, and a minus sign is prepended if appropriate. (This representation is compatible with the {@link #BigInteger(String, int) (String, int)} constructor.)

param
radix radix of the String representation.
return
String representation of this BigInteger in the given radix.
see
Integer#toString
see
Character#forDigit
see
#BigInteger(java.lang.String, int)

	if (signum == 0)
	    return "0";
	if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
	    radix = 10;

	// Compute upper bound on number of digit groups and allocate space
	int maxNumDigitGroups = (4*mag.length + 6)/7;
	String digitGroup[] = new String[maxNumDigitGroups];
        
	// Translate number to string, a digit group at a time
	BigInteger tmp = this.abs();
	int numGroups = 0;
	while (tmp.signum != 0) {
            BigInteger d = longRadix[radix];

            MutableBigInteger q = new MutableBigInteger(),
                              r = new MutableBigInteger(),
                              a = new MutableBigInteger(tmp.mag),
                              b = new MutableBigInteger(d.mag);
            a.divide(b, q, r);
            BigInteger q2 = new BigInteger(q, tmp.signum * d.signum);
            BigInteger r2 = new BigInteger(r, tmp.signum * d.signum);

            digitGroup[numGroups++] = Long.toString(r2.longValue(), radix);
            tmp = q2;
	}

	// Put sign (if any) and first digit group into result buffer
	StringBuilder buf = new StringBuilder(numGroups*digitsPerLong[radix]+1);
	if (signum<0)
	    buf.append('-");
	buf.append(digitGroup[numGroups-1]);

	// Append remaining digit groups padded with leading zeros
	for (int i=numGroups-2; i>=0; i--) {
	    // Prepend (any) leading zeros for this digit group
	    int numLeadingZeros = digitsPerLong[radix]-digitGroup[i].length();
	    if (numLeadingZeros != 0)
		buf.append(zeros[numLeadingZeros]);
	    buf.append(digitGroup[i]);
	}
	return buf.toString();
    
public java.lang.StringtoString()
Returns the decimal String representation of this BigInteger. The digit-to-character mapping provided by Character.forDigit is used, and a minus sign is prepended if appropriate. (This representation is compatible with the {@link #BigInteger(String) (String)} constructor, and allows for String concatenation with Java's + operator.)

return
decimal String representation of this BigInteger.
see
Character#forDigit
see
#BigInteger(java.lang.String)

     
	zeros[63] =
	    "000000000000000000000000000000000000000000000000000000000000000";
	for (int i=0; i<63; i++)
	    zeros[i] = zeros[63].substring(0, i);
    
	return toString(10);
    
static inttrailingZeroCnt(int val)

        // Loop unrolled for performance
        int byteVal = val & 0xff;
        if (byteVal != 0)
            return trailingZeroTable[byteVal];

        byteVal = (val >>> 8) & 0xff;
        if (byteVal != 0)
            return trailingZeroTable[byteVal] + 8;

        byteVal = (val >>> 16) & 0xff;
        if (byteVal != 0)
            return trailingZeroTable[byteVal] + 16;

        byteVal = (val >>> 24) & 0xff;
        return trailingZeroTable[byteVal] + 24;
    
private static int[]trustedStripLeadingZeroInts(int[] val)
Returns the input array stripped of any leading zero bytes. Since the source is trusted the copying may be skipped.

        int byteLength = val.length;
	int keep;

	// Find first nonzero byte
        for (keep=0; keep<val.length && val[keep]==0; keep++)
            ;

        // Only perform copy if necessary
        if (keep > 0) {
            int result[] = new int[val.length - keep];
            for(int i=0; i<val.length - keep; i++)
               result[i] = val[keep+i];
            return result; 
        }
        return val;
    
public static java.math.BigIntegervalueOf(long val)
Returns a BigInteger whose value is equal to that of the specified long. This "static factory method" is provided in preference to a (long) constructor because it allows for reuse of frequently used BigIntegers.

param
val value of the BigInteger to return.
return
a BigInteger with the specified value.

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

	return new BigInteger(val);
    
private static java.math.BigIntegervalueOf(int[] val)
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).

        return (val[0]>0 ? new BigInteger(val, 1) : new BigInteger(val));
    
private voidwriteObject(java.io.ObjectOutputStream s)
Save the BigInteger instance to a stream. The magnitude of a BigInteger is serialized as a byte array for historical reasons.

serialData
two necessary fields are written as well as obsolete fields for compatibility with older versions.

        // set the values of the Serializable fields
        ObjectOutputStream.PutField fields = s.putFields();
        fields.put("signum", signum);
        fields.put("magnitude", magSerializedForm());
        fields.put("bitCount", -1);
        fields.put("bitLength", -1);
        fields.put("lowestSetBit", -2);
        fields.put("firstNonzeroByteNum", -2);
            
        // save them
        s.writeFields();
public java.math.BigIntegerxor(java.math.BigInteger val)
Returns a BigInteger whose value is (this ^ val). (This method returns a negative BigInteger if and only if exactly one of this and val are negative.)

param
val value to be XOR'ed with this BigInteger.
return
this ^ val

	int[] result = new int[Math.max(intLength(), val.intLength())];
	for (int i=0; i<result.length; i++)
	    result[i] = (int) (getInt(result.length-i-1)
				^ val.getInt(result.length-i-1));

	return valueOf(result);