File	Doc	Category	Size	Date	Package
BigInteger.java	API Doc	Java SE 6 API	109806	Tue Jun 10 00:25:40 BST 2008	java.math

BigInteger

• java.lang.Object
  • java.lang.Number

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.BigInteger	abs() Returns a BigInteger whose value is the absolute value of this BigInteger. return abs(this) return (signum >= 0 ? this : this.negate());
public java.math.BigInteger	add(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 int	addOne(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.BigInteger	and(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.BigInteger	andNot(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 int	bitCnt(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 int	bitCount() 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 int	bitLen(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 int	bitLength(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 int	bitLength() 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.BigInteger	clearBit(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 int	compareTo(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 void	destructiveMulAdd(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.BigInteger	divide(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 double	doubleValue() 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 boolean	equals(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 int	firstNonzeroIntNum() 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.BigInteger	flipBit(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 float	floatValue() 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.BigInteger	gcd(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 int	getInt(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 int	getLowestSetBit() 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.Random	getSecureRandom() if (staticRandom == null) { staticRandom = new java.security.SecureRandom(); } return staticRandom;
public int	hashCode() 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 int	intArrayCmp(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 int	intArrayCmpToLen(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 int	intLength() Returns the length of the two's complement representation in ints, including space for at least one sign bit. return bitLength()/32 + 1;
public int	intValue() 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 boolean	isProbablePrime(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 int	jacobiSymbol(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.BigInteger	largePrime(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 long	longValue() 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.BigInteger	lucasLehmerSequence(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.BigInteger	max(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.BigInteger	min(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.BigInteger	mod(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.BigInteger	mod2(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.BigInteger	modInverse(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.BigInteger	modPow(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.BigInteger	modPow2(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 int	mulAdd(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.BigInteger	multiply(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.BigInteger	negate() Returns a BigInteger whose value is (-this). return -this return new BigInteger(this.mag, -this.signum);
public java.math.BigInteger	nextProbablePrime() 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.BigInteger	not() 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.BigInteger	oddModPow(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.BigInteger	or(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 int	parseInt(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 boolean	passesLucasLehmer() 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 boolean	passesMillerRabin(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.BigInteger	pow(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);
boolean	primeToCertainty(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 void	primitiveLeftShift(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 void	primitiveRightShift(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.BigInteger	probablePrime(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 void	readObject(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.BigInteger	remainder(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.BigInteger	setBit(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.BigInteger	shiftLeft(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.BigInteger	shiftRight(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 int	signBit() return (signum < 0 ? 1 : 0);
private int	signInt() return (int) (signum < 0 ? -1 : 0);
public int	signum() 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.BigInteger	smallPrime(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.BigInteger	square() 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 int	subN(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.BigInteger	subtract(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 boolean	testBit(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.String	toString(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.String	toString() 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 int	trailingZeroCnt(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.BigInteger	valueOf(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.BigInteger	valueOf(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 void	writeObject(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.BigInteger	xor(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);