src/share/classes/java/math/BigInteger.java
Print this page
rev 7663 : 8014319: Faster division of large integers
Summary: Implement Burnickel-Ziegler division algorithm in BigInteger
Reviewed-by: bpb
Contributed-by: Tim Buktu <tbuktu@hotmail.com>
rev 7664 : 8020641: Clean up some code style in recent BigInteger contributions
Summary: Some minor cleanup to adhere better to Java coding conventions.
Reviewed-by: darcy
Contributed-by: Brian Burkhalter <brian.burkhalter@oracle.com>
*** 296,306 ****
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;
--- 296,306 ----
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;
*** 317,327 ****
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;
--- 317,327 ----
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;
*** 370,381 ****
} else
throw new NumberFormatException("Illegal embedded sign character");
// 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;
}
--- 370,383 ----
} else
throw new NumberFormatException("Illegal embedded sign character");
// 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;
}
*** 461,471 ****
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;
}
--- 463,473 ----
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;
}
*** 628,640 ****
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
--- 630,642 ----
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
*** 716,726 ****
// 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) ||
--- 718,728 ----
// 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) ||
*** 747,757 ****
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;
--- 749,759 ----
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;
*** 814,824 ****
// 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);
--- 816,826 ----
// 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);
*** 887,897 ****
private static BigInteger lucasLehmerSequence(int z, BigInteger k, 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 = v2.subtract(n);
--- 889,899 ----
private static BigInteger lucasLehmerSequence(int z, BigInteger k, 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 = v2.subtract(n);
*** 943,963 ****
// 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;
--- 945,965 ----
// 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;
*** 967,986 ****
* This internal 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.
*/
BigInteger(int[] magnitude, int signum) {
! this.signum = (magnitude.length==0 ? 0 : signum);
this.mag = magnitude;
}
/**
* This private constructor is for internal use and assumes that its
* arguments are correct.
*/
private BigInteger(byte[] magnitude, int signum) {
! this.signum = (magnitude.length==0 ? 0 : signum);
this.mag = stripLeadingZeroBytes(magnitude);
}
//Static Factory Methods
--- 969,988 ----
* This internal 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.
*/
BigInteger(int[] magnitude, int signum) {
! this.signum = (magnitude.length == 0 ? 0 : signum);
this.mag = magnitude;
}
/**
* This private constructor is for internal use and assumes that its
* arguments are correct.
*/
private BigInteger(byte[] magnitude, int signum) {
! this.signum = (magnitude.length == 0 ? 0 : signum);
this.mag = stripLeadingZeroBytes(magnitude);
}
//Static Factory Methods
*** 1015,1025 ****
} 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;
--- 1017,1027 ----
} 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;
*** 1031,1041 ****
* Returns a BigInteger with the given two's complement representation.
* Assumes that the input array will not be modified (the returned
* BigInteger will reference the input array if feasible).
*/
private static BigInteger valueOf(int val[]) {
! return (val[0]>0 ? new BigInteger(val, 1) : new BigInteger(val));
}
// Constants
/**
--- 1033,1043 ----
* Returns a BigInteger with the given two's complement representation.
* Assumes that the input array will not be modified (the returned
* BigInteger will reference the input array if feasible).
*/
private static BigInteger valueOf(int val[]) {
! return (val[0] > 0 ? new BigInteger(val, 1) : new BigInteger(val));
}
// Constants
/**
*** 1072,1083 ****
* on demand.
*/
powerCache = new BigInteger[Character.MAX_RADIX+1][];
logCache = new double[Character.MAX_RADIX+1];
! for (int i=Character.MIN_RADIX; i<=Character.MAX_RADIX; i++)
! {
powerCache[i] = new BigInteger[] { BigInteger.valueOf(i) };
logCache[i] = Math.log(i);
}
}
--- 1074,1084 ----
* on demand.
*/
powerCache = new BigInteger[Character.MAX_RADIX+1][];
logCache = new double[Character.MAX_RADIX+1];
! for (int i=Character.MIN_RADIX; i <= Character.MAX_RADIX; i++) {
powerCache[i] = new BigInteger[] { BigInteger.valueOf(i) };
logCache[i] = Math.log(i);
}
}
*** 1167,1177 ****
int[] y;
long sum = 0;
int xIndex = x.length;
int[] result;
int highWord = (int)(val >>> 32);
! if (highWord==0) {
result = new int[xIndex];
sum = (x[--xIndex] & LONG_MASK) + val;
result[xIndex] = (int)sum;
} else {
if (xIndex == 1) {
--- 1168,1178 ----
int[] y;
long sum = 0;
int xIndex = x.length;
int[] result;
int highWord = (int)(val >>> 32);
! if (highWord == 0) {
result = new int[xIndex];
sum = (x[--xIndex] & LONG_MASK) + val;
result[xIndex] = (int)sum;
} else {
if (xIndex == 1) {
*** 1220,1235 ****
int xIndex = x.length;
int yIndex = y.length;
int result[] = new int[xIndex];
long sum = 0;
! if(yIndex==1) {
sum = (x[--xIndex] & LONG_MASK) + (y[0] & LONG_MASK) ;
result[xIndex] = (int)sum;
} else {
// Add common parts of both numbers
! while(yIndex > 0) {
sum = (x[--xIndex] & LONG_MASK) +
(y[--yIndex] & LONG_MASK) + (sum >>> 32);
result[xIndex] = (int)sum;
}
}
--- 1221,1236 ----
int xIndex = x.length;
int yIndex = y.length;
int result[] = new int[xIndex];
long sum = 0;
! if (yIndex == 1) {
sum = (x[--xIndex] & LONG_MASK) + (y[0] & LONG_MASK) ;
result[xIndex] = (int)sum;
} else {
// Add common parts of both numbers
! while (yIndex > 0) {
sum = (x[--xIndex] & LONG_MASK) +
(y[--yIndex] & LONG_MASK) + (sum >>> 32);
result[xIndex] = (int)sum;
}
}
*** 1252,1279 ****
return result;
}
private static int[] subtract(long val, int[] little) {
int highWord = (int)(val >>> 32);
! if (highWord==0) {
int result[] = new int[1];
result[0] = (int)(val - (little[0] & LONG_MASK));
return result;
} else {
int result[] = new int[2];
! if(little.length==1) {
long difference = ((int)val & LONG_MASK) - (little[0] & LONG_MASK);
result[1] = (int)difference;
// Subtract remainder of longer number while borrow propagates
boolean borrow = (difference >> 32 != 0);
! if(borrow) {
result[0] = highWord - 1;
} else { // Copy remainder of longer number
result[0] = highWord;
}
return result;
! } else { // little.length==2
long difference = ((int)val & LONG_MASK) - (little[1] & LONG_MASK);
result[1] = (int)difference;
difference = (highWord & LONG_MASK) - (little[0] & LONG_MASK) + (difference >> 32);
result[0] = (int)difference;
return result;
--- 1253,1280 ----
return result;
}
private static int[] subtract(long val, int[] little) {
int highWord = (int)(val >>> 32);
! if (highWord == 0) {
int result[] = new int[1];
result[0] = (int)(val - (little[0] & LONG_MASK));
return result;
} else {
int result[] = new int[2];
! if (little.length == 1) {
long difference = ((int)val & LONG_MASK) - (little[0] & LONG_MASK);
result[1] = (int)difference;
// Subtract remainder of longer number while borrow propagates
boolean borrow = (difference >> 32 != 0);
! if (borrow) {
result[0] = highWord - 1;
} else { // Copy remainder of longer number
result[0] = highWord;
}
return result;
! } else { // little.length == 2
long difference = ((int)val & LONG_MASK) - (little[1] & LONG_MASK);
result[1] = (int)difference;
difference = (highWord & LONG_MASK) - (little[0] & LONG_MASK) + (difference >> 32);
result[0] = (int)difference;
return result;
*** 1292,1312 ****
int highWord = (int)(val >>> 32);
int bigIndex = big.length;
int result[] = new int[bigIndex];
long difference = 0;
! if (highWord==0) {
difference = (big[--bigIndex] & LONG_MASK) - val;
result[bigIndex] = (int)difference;
} else {
difference = (big[--bigIndex] & LONG_MASK) - (val & LONG_MASK);
result[bigIndex] = (int)difference;
difference = (big[--bigIndex] & LONG_MASK) - (highWord & 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);
--- 1293,1312 ----
int highWord = (int)(val >>> 32);
int bigIndex = big.length;
int result[] = new int[bigIndex];
long difference = 0;
! if (highWord == 0) {
difference = (big[--bigIndex] & LONG_MASK) - val;
result[bigIndex] = (int)difference;
} else {
difference = (big[--bigIndex] & LONG_MASK) - (val & LONG_MASK);
result[bigIndex] = (int)difference;
difference = (big[--bigIndex] & LONG_MASK) - (highWord & 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);
*** 1351,1361 ****
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;
}
--- 1351,1361 ----
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;
}
*** 1383,1415 ****
return ZERO;
int xlen = mag.length;
int ylen = val.mag.length;
! if ((xlen < KARATSUBA_THRESHOLD) || (ylen < KARATSUBA_THRESHOLD))
! {
int resultSign = signum == val.signum ? 1 : -1;
if (val.mag.length == 1) {
return multiplyByInt(mag,val.mag[0], resultSign);
}
! if(mag.length == 1) {
return multiplyByInt(val.mag,mag[0], resultSign);
}
int[] result = multiplyToLen(mag, xlen,
val.mag, ylen, null);
result = trustedStripLeadingZeroInts(result);
return new BigInteger(result, resultSign);
! }
! else
! if ((xlen < TOOM_COOK_THRESHOLD) && (ylen < TOOM_COOK_THRESHOLD))
return multiplyKaratsuba(this, val);
! else
return multiplyToomCook3(this, val);
}
private static BigInteger multiplyByInt(int[] x, int y, int sign) {
! if(Integer.bitCount(y)==1) {
return new BigInteger(shiftLeft(x,Integer.numberOfTrailingZeros(y)), sign);
}
int xlen = x.length;
int[] rmag = new int[xlen + 1];
long carry = 0;
--- 1383,1415 ----
return ZERO;
int xlen = mag.length;
int ylen = val.mag.length;
! if ((xlen < KARATSUBA_THRESHOLD) || (ylen < KARATSUBA_THRESHOLD)) {
int resultSign = signum == val.signum ? 1 : -1;
if (val.mag.length == 1) {
return multiplyByInt(mag,val.mag[0], resultSign);
}
! if (mag.length == 1) {
return multiplyByInt(val.mag,mag[0], resultSign);
}
int[] result = multiplyToLen(mag, xlen,
val.mag, ylen, null);
result = trustedStripLeadingZeroInts(result);
return new BigInteger(result, resultSign);
! } else {
! if ((xlen < TOOM_COOK_THRESHOLD) && (ylen < TOOM_COOK_THRESHOLD)) {
return multiplyKaratsuba(this, val);
! } else {
return multiplyToomCook3(this, val);
}
+ }
+ }
private static BigInteger multiplyByInt(int[] x, int y, int sign) {
! if (Integer.bitCount(y) == 1) {
return new BigInteger(shiftLeft(x,Integer.numberOfTrailingZeros(y)), sign);
}
int xlen = x.length;
int[] rmag = new int[xlen + 1];
long carry = 0;
*** 1480,1500 ****
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;
--- 1480,1500 ----
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;
*** 1517,1528 ****
* both numbers are larger than a certain threshold (found
* experimentally).
*
* See: http://en.wikipedia.org/wiki/Karatsuba_algorithm
*/
! private static BigInteger multiplyKaratsuba(BigInteger x, BigInteger y)
! {
int xlen = x.mag.length;
int ylen = y.mag.length;
// The number of ints in each half of the number.
int half = (Math.max(xlen, ylen)+1) / 2;
--- 1517,1527 ----
* both numbers are larger than a certain threshold (found
* experimentally).
*
* See: http://en.wikipedia.org/wiki/Karatsuba_algorithm
*/
! private static BigInteger multiplyKaratsuba(BigInteger x, BigInteger y) {
int xlen = x.mag.length;
int ylen = y.mag.length;
// The number of ints in each half of the number.
int half = (Math.max(xlen, ylen)+1) / 2;
*** 1541,1555 ****
BigInteger p3 = xh.add(xl).multiply(yh.add(yl));
// result = p1 * 2^(32*2*half) + (p3 - p1 - p2) * 2^(32*half) + p2
BigInteger result = p1.shiftLeft(32*half).add(p3.subtract(p1).subtract(p2)).shiftLeft(32*half).add(p2);
! if (x.signum != y.signum)
return result.negate();
! else
return result;
}
/**
* Multiplies two BigIntegers using a 3-way Toom-Cook multiplication
* algorithm. This is a recursive divide-and-conquer algorithm which is
* more efficient for large numbers than what is commonly called the
--- 1540,1555 ----
BigInteger p3 = xh.add(xl).multiply(yh.add(yl));
// result = p1 * 2^(32*2*half) + (p3 - p1 - p2) * 2^(32*half) + p2
BigInteger result = p1.shiftLeft(32*half).add(p3.subtract(p1).subtract(p2)).shiftLeft(32*half).add(p2);
! if (x.signum != y.signum) {
return result.negate();
! } else {
return result;
}
+ }
/**
* Multiplies two BigIntegers using a 3-way Toom-Cook multiplication
* algorithm. This is a recursive divide-and-conquer algorithm which is
* more efficient for large numbers than what is commonly called the
*** 1575,1586 ****
* Multivariate Polynomials in Characteristic 2 and 0." by Marco BODRATO;
* In C.Carlet and B.Sunar, Eds., "WAIFI'07 proceedings", p. 116-133,
* LNCS #4547. Springer, Madrid, Spain, June 21-22, 2007.
*
*/
! private static BigInteger multiplyToomCook3(BigInteger a, BigInteger b)
! {
int alen = a.mag.length;
int blen = b.mag.length;
int largest = Math.max(alen, blen);
--- 1575,1585 ----
* Multivariate Polynomials in Characteristic 2 and 0." by Marco BODRATO;
* In C.Carlet and B.Sunar, Eds., "WAIFI'07 proceedings", p. 116-133,
* LNCS #4547. Springer, Madrid, Spain, June 21-22, 2007.
*
*/
! private static BigInteger multiplyToomCook3(BigInteger a, BigInteger b) {
int alen = a.mag.length;
int blen = b.mag.length;
int largest = Math.max(alen, blen);
*** 1611,1626 ****
v1 = da1.multiply(db1);
v2 = da1.add(a2).shiftLeft(1).subtract(a0).multiply(
db1.add(b2).shiftLeft(1).subtract(b0));
vinf = a2.multiply(b2);
! /* The algorithm requires two divisions by 2 and one by 3.
! All divisions are known to be exact, that is, they do not produce
! remainders, and all results are positive. The divisions by 2 are
! implemented as right shifts which are relatively efficient, leaving
! only an exact division by 3, which is done by a specialized
! linear-time algorithm. */
t2 = v2.subtract(vm1).exactDivideBy3();
tm1 = v1.subtract(vm1).shiftRight(1);
t1 = v1.subtract(v0);
t2 = t2.subtract(t1).shiftRight(1);
t1 = t1.subtract(tm1).subtract(vinf);
--- 1610,1625 ----
v1 = da1.multiply(db1);
v2 = da1.add(a2).shiftLeft(1).subtract(a0).multiply(
db1.add(b2).shiftLeft(1).subtract(b0));
vinf = a2.multiply(b2);
! // The algorithm requires two divisions by 2 and one by 3.
! // All divisions are known to be exact, that is, they do not produce
! // remainders, and all results are positive. The divisions by 2 are
! // implemented as right shifts which are relatively efficient, leaving
! // only an exact division by 3, which is done by a specialized
! // linear-time algorithm.
t2 = v2.subtract(vm1).exactDivideBy3();
tm1 = v1.subtract(vm1).shiftRight(1);
t1 = v1.subtract(v0);
t2 = t2.subtract(t1).shiftRight(1);
t1 = t1.subtract(tm1).subtract(vinf);
*** 1630,1644 ****
// Number of bits to shift left.
int ss = k*32;
BigInteger result = vinf.shiftLeft(ss).add(t2).shiftLeft(ss).add(t1).shiftLeft(ss).add(tm1).shiftLeft(ss).add(v0);
! if (a.signum != b.signum)
return result.negate();
! else
return result;
}
/**
* Returns a slice of a BigInteger for use in Toom-Cook multiplication.
*
--- 1629,1644 ----
// Number of bits to shift left.
int ss = k*32;
BigInteger result = vinf.shiftLeft(ss).add(t2).shiftLeft(ss).add(t1).shiftLeft(ss).add(tm1).shiftLeft(ss).add(v0);
! if (a.signum != b.signum) {
return result.negate();
! } else {
return result;
}
+ }
/**
* Returns a slice of a BigInteger for use in Toom-Cook multiplication.
*
*** 1651,1692 ****
* @param fullsize The size of the larger integer array, used to align
* slices to the appropriate position when multiplying different-sized
* numbers.
*/
private BigInteger getToomSlice(int lowerSize, int upperSize, int slice,
! int fullsize)
! {
int start, end, sliceSize, len, offset;
len = mag.length;
offset = fullsize - len;
! if (slice == 0)
! {
start = 0 - offset;
end = upperSize - 1 - offset;
! }
! else
! {
start = upperSize + (slice-1)*lowerSize - offset;
end = start + lowerSize - 1;
}
! if (start < 0)
start = 0;
! if (end < 0)
return ZERO;
sliceSize = (end-start) + 1;
! if (sliceSize <= 0)
return ZERO;
// While performing Toom-Cook, all slices are positive and
// the sign is adjusted when the final number is composed.
! if (start==0 && sliceSize >= len)
return this.abs();
int intSlice[] = new int[sliceSize];
System.arraycopy(mag, start, intSlice, 0, sliceSize);
return new BigInteger(trustedStripLeadingZeroInts(intSlice), 1);
--- 1651,1692 ----
* @param fullsize The size of the larger integer array, used to align
* slices to the appropriate position when multiplying different-sized
* numbers.
*/
private BigInteger getToomSlice(int lowerSize, int upperSize, int slice,
! int fullsize) {
int start, end, sliceSize, len, offset;
len = mag.length;
offset = fullsize - len;
! if (slice == 0) {
start = 0 - offset;
end = upperSize - 1 - offset;
! } else {
start = upperSize + (slice-1)*lowerSize - offset;
end = start + lowerSize - 1;
}
! if (start < 0) {
start = 0;
! }
! if (end < 0) {
return ZERO;
+ }
sliceSize = (end-start) + 1;
! if (sliceSize <= 0) {
return ZERO;
+ }
// While performing Toom-Cook, all slices are positive and
// the sign is adjusted when the final number is composed.
! if (start == 0 && sliceSize >= len) {
return this.abs();
+ }
int intSlice[] = new int[sliceSize];
System.arraycopy(mag, start, intSlice, 0, sliceSize);
return new BigInteger(trustedStripLeadingZeroInts(intSlice), 1);
*** 1698,1732 ****
* multiplication. This is an efficient algorithm that runs in linear
* time. If the argument is not exactly divisible by 3, results are
* undefined. Note that this is expected to be called with positive
* arguments only.
*/
! private BigInteger exactDivideBy3()
! {
int len = mag.length;
int[] result = new int[len];
long x, w, q, borrow;
borrow = 0L;
! for (int i=len-1; i>=0; i--)
! {
x = (mag[i] & LONG_MASK);
w = x - borrow;
! if (borrow > x) // Did we make the number go negative?
borrow = 1L;
! else
borrow = 0L;
// 0xAAAAAAAB is the modular inverse of 3 (mod 2^32). Thus,
// the effect of this is to divide by 3 (mod 2^32).
// This is much faster than division on most architectures.
q = (w * 0xAAAAAAABL) & LONG_MASK;
result[i] = (int) q;
// Now check the borrow. The second check can of course be
// eliminated if the first fails.
! if (q >= 0x55555556L)
! {
borrow++;
if (q >= 0xAAAAAAABL)
borrow++;
}
}
--- 1698,1730 ----
* multiplication. This is an efficient algorithm that runs in linear
* time. If the argument is not exactly divisible by 3, results are
* undefined. Note that this is expected to be called with positive
* arguments only.
*/
! private BigInteger exactDivideBy3() {
int len = mag.length;
int[] result = new int[len];
long x, w, q, borrow;
borrow = 0L;
! for (int i=len-1; i >= 0; i--) {
x = (mag[i] & LONG_MASK);
w = x - borrow;
! if (borrow > x) { // Did we make the number go negative?
borrow = 1L;
! } else {
borrow = 0L;
+ }
// 0xAAAAAAAB is the modular inverse of 3 (mod 2^32). Thus,
// the effect of this is to divide by 3 (mod 2^32).
// This is much faster than division on most architectures.
q = (w * 0xAAAAAAABL) & LONG_MASK;
result[i] = (int) q;
// Now check the borrow. The second check can of course be
// eliminated if the first fails.
! if (q >= 0x55555556L) {
borrow++;
if (q >= 0xAAAAAAABL)
borrow++;
}
}
*** 1739,1750 ****
* This is used by Karatsuba multiplication and Karatsuba squaring.
*/
private BigInteger getLower(int n) {
int len = mag.length;
! if (len <= n)
return this;
int lowerInts[] = new int[n];
System.arraycopy(mag, len-n, lowerInts, 0, n);
return new BigInteger(trustedStripLeadingZeroInts(lowerInts), 1);
--- 1737,1749 ----
* This is used by Karatsuba multiplication and Karatsuba squaring.
*/
private BigInteger getLower(int n) {
int len = mag.length;
! if (len <= n) {
return this;
+ }
int lowerInts[] = new int[n];
System.arraycopy(mag, len-n, lowerInts, 0, n);
return new BigInteger(trustedStripLeadingZeroInts(lowerInts), 1);
*** 1756,1767 ****
* Karatsuba squaring.
*/
private BigInteger getUpper(int n) {
int len = mag.length;
! if (len <= n)
return ZERO;
int upperLen = len - n;
int upperInts[] = new int[upperLen];
System.arraycopy(mag, 0, upperInts, 0, upperLen);
--- 1755,1767 ----
* Karatsuba squaring.
*/
private BigInteger getUpper(int n) {
int len = mag.length;
! if (len <= n) {
return ZERO;
+ }
int upperLen = len - n;
int upperInts[] = new int[upperLen];
System.arraycopy(mag, 0, upperInts, 0, upperLen);
*** 1774,1798 ****
* Returns a BigInteger whose value is {@code (this<sup>2</sup>)}.
*
* @return {@code this<sup>2</sup>}
*/
private BigInteger square() {
! if (signum == 0)
return ZERO;
int len = mag.length;
! if (len < KARATSUBA_SQUARE_THRESHOLD)
! {
int[] z = squareToLen(mag, len, null);
return new BigInteger(trustedStripLeadingZeroInts(z), 1);
! }
! else
! if (len < TOOM_COOK_SQUARE_THRESHOLD)
return squareKaratsuba();
! else
return squareToomCook3();
}
/**
* Squares the contents of the int array x. The result is placed into the
* int array z. The contents of x are not changed.
*/
--- 1774,1799 ----
* Returns a BigInteger whose value is {@code (this<sup>2</sup>)}.
*
* @return {@code this<sup>2</sup>}
*/
private BigInteger square() {
! if (signum == 0) {
return ZERO;
+ }
int len = mag.length;
! if (len < KARATSUBA_SQUARE_THRESHOLD) {
int[] z = squareToLen(mag, len, null);
return new BigInteger(trustedStripLeadingZeroInts(z), 1);
! } else {
! if (len < TOOM_COOK_SQUARE_THRESHOLD) {
return squareKaratsuba();
! } else {
return squareToomCook3();
}
+ }
+ }
/**
* Squares the contents of the int array x. The result is placed into the
* int array z. The contents of x are not changed.
*/
*** 1835,1854 ****
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);
}
--- 1836,1855 ----
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);
}
*** 1864,1875 ****
* be used when both numbers are larger than a certain threshold (found
* experimentally). It is a recursive divide-and-conquer algorithm that
* has better asymptotic performance than the algorithm used in
* squareToLen.
*/
! private BigInteger squareKaratsuba()
! {
int half = (mag.length+1) / 2;
BigInteger xl = getLower(half);
BigInteger xh = getUpper(half);
--- 1865,1875 ----
* be used when both numbers are larger than a certain threshold (found
* experimentally). It is a recursive divide-and-conquer algorithm that
* has better asymptotic performance than the algorithm used in
* squareToLen.
*/
! private BigInteger squareKaratsuba() {
int half = (mag.length+1) / 2;
BigInteger xl = getLower(half);
BigInteger xh = getUpper(half);
*** 1885,1896 ****
* should be used when both numbers are larger than a certain threshold
* (found experimentally). It is a recursive divide-and-conquer algorithm
* that has better asymptotic performance than the algorithm used in
* squareToLen or squareKaratsuba.
*/
! private BigInteger squareToomCook3()
! {
int len = mag.length;
// k is the size (in ints) of the lower-order slices.
int k = (len+2)/3; // Equal to ceil(largest/3)
--- 1885,1895 ----
* should be used when both numbers are larger than a certain threshold
* (found experimentally). It is a recursive divide-and-conquer algorithm
* that has better asymptotic performance than the algorithm used in
* squareToLen or squareKaratsuba.
*/
! private BigInteger squareToomCook3() {
int len = mag.length;
// k is the size (in ints) of the lower-order slices.
int k = (len+2)/3; // Equal to ceil(largest/3)
*** 1911,1927 ****
da1 = da1.add(a1);
v1 = da1.square();
vinf = a2.square();
v2 = da1.add(a2).shiftLeft(1).subtract(a0).square();
! /* The algorithm requires two divisions by 2 and one by 3.
! All divisions are known to be exact, that is, they do not produce
! remainders, and all results are positive. The divisions by 2 are
! implemented as right shifts which are relatively efficient, leaving
! only a division by 3.
! The division by 3 is done by an optimized algorithm for this case.
! */
t2 = v2.subtract(vm1).exactDivideBy3();
tm1 = v1.subtract(vm1).shiftRight(1);
t1 = v1.subtract(v0);
t2 = t2.subtract(t1).shiftRight(1);
t1 = t1.subtract(tm1).subtract(vinf);
--- 1910,1925 ----
da1 = da1.add(a1);
v1 = da1.square();
vinf = a2.square();
v2 = da1.add(a2).shiftLeft(1).subtract(a0).square();
! // The algorithm requires two divisions by 2 and one by 3.
! // All divisions are known to be exact, that is, they do not produce
! // remainders, and all results are positive. The divisions by 2 are
! // implemented as right shifts which are relatively efficient, leaving
! // only a division by 3.
! // The division by 3 is done by an optimized algorithm for this case.
t2 = v2.subtract(vm1).exactDivideBy3();
tm1 = v1.subtract(vm1).shiftRight(1);
t1 = v1.subtract(v0);
t2 = t2.subtract(t1).shiftRight(1);
t1 = t1.subtract(tm1).subtract(vinf);
*** 1942,1956 ****
* @param val value by which this BigInteger is to be divided.
* @return {@code this / val}
* @throws ArithmeticException if {@code val} is zero.
*/
public BigInteger divide(BigInteger val) {
! if (mag.length<BURNIKEL_ZIEGLER_THRESHOLD || val.mag.length<BURNIKEL_ZIEGLER_THRESHOLD)
return divideKnuth(val);
! else
return divideBurnikelZiegler(val);
}
/**
* Returns a BigInteger whose value is {@code (this / val)} using an O(n^2) algorithm from Knuth.
*
* @param val value by which this BigInteger is to be divided.
--- 1940,1956 ----
* @param val value by which this BigInteger is to be divided.
* @return {@code this / val}
* @throws ArithmeticException if {@code val} is zero.
*/
public BigInteger divide(BigInteger val) {
! if (mag.length < BURNIKEL_ZIEGLER_THRESHOLD ||
! val.mag.length < BURNIKEL_ZIEGLER_THRESHOLD) {
return divideKnuth(val);
! } else {
return divideBurnikelZiegler(val);
}
+ }
/**
* Returns a BigInteger whose value is {@code (this / val)} using an O(n^2) algorithm from Knuth.
*
* @param val value by which this BigInteger is to be divided.
*** 1977,1991 ****
* is the initial element, and the remainder {@code (this % val)}
* is the final element.
* @throws ArithmeticException if {@code val} is zero.
*/
public BigInteger[] divideAndRemainder(BigInteger val) {
! if (mag.length<BURNIKEL_ZIEGLER_THRESHOLD || val.mag.length<BURNIKEL_ZIEGLER_THRESHOLD)
return divideAndRemainderKnuth(val);
! else
return divideAndRemainderBurnikelZiegler(val);
}
/** Long division */
private BigInteger[] divideAndRemainderKnuth(BigInteger val) {
BigInteger[] result = new BigInteger[2];
MutableBigInteger q = new MutableBigInteger(),
--- 1977,1993 ----
* is the initial element, and the remainder {@code (this % val)}
* is the final element.
* @throws ArithmeticException if {@code val} is zero.
*/
public BigInteger[] divideAndRemainder(BigInteger val) {
! if (mag.length < BURNIKEL_ZIEGLER_THRESHOLD ||
! val.mag.length < BURNIKEL_ZIEGLER_THRESHOLD) {
return divideAndRemainderKnuth(val);
! } else {
return divideAndRemainderBurnikelZiegler(val);
}
+ }
/** Long division */
private BigInteger[] divideAndRemainderKnuth(BigInteger val) {
BigInteger[] result = new BigInteger[2];
MutableBigInteger q = new MutableBigInteger(),
*** 2004,2018 ****
* remainder computed.
* @return {@code this % val}
* @throws ArithmeticException if {@code val} is zero.
*/
public BigInteger remainder(BigInteger val) {
! if (mag.length<BURNIKEL_ZIEGLER_THRESHOLD || val.mag.length<BURNIKEL_ZIEGLER_THRESHOLD)
return remainderKnuth(val);
! else
return remainderBurnikelZiegler(val);
}
/** Long division */
private BigInteger remainderKnuth(BigInteger val) {
MutableBigInteger q = new MutableBigInteger(),
a = new MutableBigInteger(this.mag),
--- 2006,2022 ----
* remainder computed.
* @return {@code this % val}
* @throws ArithmeticException if {@code val} is zero.
*/
public BigInteger remainder(BigInteger val) {
! if (mag.length < BURNIKEL_ZIEGLER_THRESHOLD ||
! val.mag.length < BURNIKEL_ZIEGLER_THRESHOLD) {
return remainderKnuth(val);
! } else {
return remainderBurnikelZiegler(val);
}
+ }
/** Long division */
private BigInteger remainderKnuth(BigInteger val) {
MutableBigInteger q = new MutableBigInteger(),
a = new MutableBigInteger(this.mag),
*** 2061,2074 ****
* @return <tt>this<sup>exponent</sup></tt>
* @throws ArithmeticException {@code exponent} is negative. (This would
* cause the operation to yield a non-integer value.)
*/
public BigInteger pow(int exponent) {
! if (exponent < 0)
throw new ArithmeticException("Negative exponent");
! if (signum==0)
! return (exponent==0 ? ONE : this);
BigInteger partToSquare = this.abs();
// Factor out powers of two from the base, as the exponentiation of
// these can be done by left shifts only.
--- 2065,2080 ----
* @return <tt>this<sup>exponent</sup></tt>
* @throws ArithmeticException {@code exponent} is negative. (This would
* cause the operation to yield a non-integer value.)
*/
public BigInteger pow(int exponent) {
! if (exponent < 0) {
throw new ArithmeticException("Negative exponent");
! }
! if (signum == 0) {
! return (exponent == 0 ? ONE : this);
! }
BigInteger partToSquare = this.abs();
// Factor out powers of two from the base, as the exponentiation of
// these can be done by left shifts only.
*** 2077,2175 ****
int powersOfTwo = partToSquare.getLowestSetBit();
int remainingBits;
// Factor the powers of two out quickly by shifting right, if needed.
! if (powersOfTwo > 0)
! {
partToSquare = partToSquare.shiftRight(powersOfTwo);
remainingBits = partToSquare.bitLength();
! if (remainingBits == 1) // Nothing left but +/- 1?
! if (signum<0 && (exponent&1)==1)
return NEGATIVE_ONE.shiftLeft(powersOfTwo*exponent);
! else
return ONE.shiftLeft(powersOfTwo*exponent);
}
! else
! {
remainingBits = partToSquare.bitLength();
! if (remainingBits == 1) // Nothing left but +/- 1?
! if (signum<0 && (exponent&1)==1)
return NEGATIVE_ONE;
! else
return ONE;
}
// This is a quick way to approximate the size of the result,
// similar to doing log2[n] * exponent. This will give an upper bound
// of how big the result can be, and which algorithm to use.
int scaleFactor = remainingBits * exponent;
// Use slightly different algorithms for small and large operands.
// See if the result will safely fit into a long. (Largest 2^63-1)
! if (partToSquare.mag.length==1 && scaleFactor <= 62)
! {
// Small number algorithm. Everything fits into a long.
! int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1);
long result = 1;
long baseToPow2 = partToSquare.mag[0] & LONG_MASK;
int workingExponent = exponent;
// Perform exponentiation using repeated squaring trick
while (workingExponent != 0) {
! if ((workingExponent & 1)==1)
result = result * baseToPow2;
! if ((workingExponent >>>= 1) != 0)
baseToPow2 = baseToPow2 * baseToPow2;
}
// Multiply back the powers of two (quickly, by shifting left)
! if (powersOfTwo > 0)
! {
int bitsToShift = powersOfTwo*exponent;
! if (bitsToShift + scaleFactor <= 62) // Fits in long?
return valueOf((result << bitsToShift) * newSign);
! else
return valueOf(result*newSign).shiftLeft(bitsToShift);
}
! else
return valueOf(result*newSign);
}
! else
! {
// Large number algorithm. This is basically identical to
// the algorithm above, but calls multiply() and square()
// which may use more efficient algorithms for large numbers.
BigInteger answer = ONE;
int workingExponent = exponent;
// Perform exponentiation using repeated squaring trick
while (workingExponent != 0) {
! if ((workingExponent & 1)==1)
answer = answer.multiply(partToSquare);
! if ((workingExponent >>>= 1) != 0)
partToSquare = partToSquare.square();
}
// Multiply back the (exponentiated) powers of two (quickly,
// by shifting left)
! if (powersOfTwo > 0)
answer = answer.shiftLeft(powersOfTwo*exponent);
! if (signum<0 && (exponent&1)==1)
return answer.negate();
! else
return answer;
}
}
/**
* Returns a BigInteger whose value is the greatest common divisor of
* {@code abs(this)} and {@code abs(val)}. Returns 0 if
! * {@code this==0 && val==0}.
*
* @param val value with which the GCD is to be computed.
* @return {@code GCD(abs(this), abs(val))}
*/
public BigInteger gcd(BigInteger val) {
--- 2083,2186 ----
int powersOfTwo = partToSquare.getLowestSetBit();
int remainingBits;
// Factor the powers of two out quickly by shifting right, if needed.
! if (powersOfTwo > 0) {
partToSquare = partToSquare.shiftRight(powersOfTwo);
remainingBits = partToSquare.bitLength();
! if (remainingBits == 1) { // Nothing left but +/- 1?
! if (signum < 0 && (exponent&1) == 1) {
return NEGATIVE_ONE.shiftLeft(powersOfTwo*exponent);
! } else {
return ONE.shiftLeft(powersOfTwo*exponent);
}
! }
! } else {
remainingBits = partToSquare.bitLength();
! if (remainingBits == 1) { // Nothing left but +/- 1?
! if (signum < 0 && (exponent&1) == 1) {
return NEGATIVE_ONE;
! } else {
return ONE;
}
+ }
+ }
// This is a quick way to approximate the size of the result,
// similar to doing log2[n] * exponent. This will give an upper bound
// of how big the result can be, and which algorithm to use.
int scaleFactor = remainingBits * exponent;
// Use slightly different algorithms for small and large operands.
// See if the result will safely fit into a long. (Largest 2^63-1)
! if (partToSquare.mag.length == 1 && scaleFactor <= 62) {
// Small number algorithm. Everything fits into a long.
! int newSign = (signum <0 && (exponent&1) == 1 ? -1 : 1);
long result = 1;
long baseToPow2 = partToSquare.mag[0] & LONG_MASK;
int workingExponent = exponent;
// Perform exponentiation using repeated squaring trick
while (workingExponent != 0) {
! if ((workingExponent & 1) == 1) {
result = result * baseToPow2;
+ }
! if ((workingExponent >>>= 1) != 0) {
baseToPow2 = baseToPow2 * baseToPow2;
}
+ }
// Multiply back the powers of two (quickly, by shifting left)
! if (powersOfTwo > 0) {
int bitsToShift = powersOfTwo*exponent;
! if (bitsToShift + scaleFactor <= 62) { // Fits in long?
return valueOf((result << bitsToShift) * newSign);
! } else {
return valueOf(result*newSign).shiftLeft(bitsToShift);
}
! }
! else {
return valueOf(result*newSign);
}
! } else {
// Large number algorithm. This is basically identical to
// the algorithm above, but calls multiply() and square()
// which may use more efficient algorithms for large numbers.
BigInteger answer = ONE;
int workingExponent = exponent;
// Perform exponentiation using repeated squaring trick
while (workingExponent != 0) {
! if ((workingExponent & 1) == 1) {
answer = answer.multiply(partToSquare);
+ }
! if ((workingExponent >>>= 1) != 0) {
partToSquare = partToSquare.square();
}
+ }
// Multiply back the (exponentiated) powers of two (quickly,
// by shifting left)
! if (powersOfTwo > 0) {
answer = answer.shiftLeft(powersOfTwo*exponent);
+ }
! if (signum < 0 && (exponent&1) == 1) {
return answer.negate();
! } else {
return answer;
}
}
+ }
/**
* Returns a BigInteger whose value is the greatest common divisor of
* {@code abs(this)} and {@code abs(val)}. Returns 0 if
! * {@code this == 0 && val == 0}.
*
* @param val value with which the GCD is to be computed.
* @return {@code GCD(abs(this), abs(val))}
*/
public BigInteger gcd(BigInteger val) {
*** 2222,2232 ****
}
// shifts a up to len right n bits assumes no leading zeros, 0<n<32
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;
--- 2233,2243 ----
}
// shifts a up to len right n bits assumes no leading zeros, 0<n<32
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;
*** 2236,2246 ****
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;
--- 2247,2257 ----
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;
*** 2447,2457 ****
// 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 = mag.clone();
int[] exp = y.mag;
int[] mod = z.mag;
--- 2458,2468 ----
// 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 = mag.clone();
int[] exp = y.mag;
int[] mod = z.mag;
*** 2470,2480 ****
// 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]);
--- 2481,2491 ----
// 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]);
*** 2490,2500 ****
// 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
--- 2501,2511 ----
// 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
*** 2503,2513 ****
// Set t to high half of b
int[] t = Arrays.copyOf(b, modLen);
// 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
--- 2514,2524 ----
// Set t to high half of b
int[] t = Arrays.copyOf(b, modLen);
// 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
*** 2543,2553 ****
buf = 0;
if (multpos == ebits)
isone = false;
// The main loop
! while(true) {
ebits--;
// Advance the window
buf <<= 1;
if (elen != 0) {
--- 2554,2564 ----
buf = 0;
if (multpos == ebits)
isone = false;
// The main loop
! while (true) {
ebits--;
// Advance the window
buf <<= 1;
if (elen != 0) {
*** 2620,2632 ****
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);
--- 2631,2643 ----
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);
*** 2637,2647 ****
/*
* Returns -1, 0 or +1 as big-endian unsigned int array arg1 is less than,
* equal to, or greater than arg2 up to length len.
*/
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)
--- 2648,2658 ----
/*
* Returns -1, 0 or +1 as big-endian unsigned int array arg1 is less than,
* equal to, or greater than arg2 up to length len.
*/
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)
*** 2654,2664 ****
* Subtracts two numbers of same length, returning borrow.
*/
private static int subN(int[] a, int[] b, int len) {
long sum = 0;
! while(--len >= 0) {
sum = (a[len] & LONG_MASK) -
(b[len] & LONG_MASK) + (sum >> 32);
a[len] = (int)sum;
}
--- 2665,2675 ----
* Subtracts two numbers of same length, returning borrow.
*/
private static int subN(int[] a, int[] b, int len) {
long sum = 0;
! while (--len >= 0) {
sum = (a[len] & LONG_MASK) -
(b[len] & LONG_MASK) + (sum >> 32);
a[len] = (int)sum;
}
*** 2748,2758 ****
// 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));
}
/**
* Returns a BigInteger whose value is {@code (this}<sup>-1</sup> {@code mod m)}.
*
--- 2759,2769 ----
// 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));
}
/**
* Returns a BigInteger whose value is {@code (this}<sup>-1</sup> {@code mod m)}.
*
*** 2799,2811 ****
* @see #shiftRight
*/
public BigInteger shiftLeft(int n) {
if (signum == 0)
return ZERO;
! if (n==0)
return this;
! if (n<0) {
if (n == Integer.MIN_VALUE) {
throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported.");
} else {
return shiftRight(-n);
}
--- 2810,2822 ----
* @see #shiftRight
*/
public BigInteger shiftLeft(int n) {
if (signum == 0)
return ZERO;
! if (n == 0)
return this;
! if (n < 0) {
if (n == Integer.MIN_VALUE) {
throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported.");
} else {
return shiftRight(-n);
}
*** 2853,2865 ****
* @throws ArithmeticException if the shift distance is {@code
* Integer.MIN_VALUE}.
* @see #shiftLeft
*/
public BigInteger shiftRight(int n) {
! if (n==0)
return this;
! if (n<0) {
if (n == Integer.MIN_VALUE) {
throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported.");
} else {
return shiftLeft(-n);
}
--- 2864,2876 ----
* @throws ArithmeticException if the shift distance is {@code
* Integer.MIN_VALUE}.
* @see #shiftLeft
*/
public BigInteger shiftRight(int n) {
! if (n == 0)
return this;
! if (n < 0) {
if (n == Integer.MIN_VALUE) {
throw new ArithmeticException("Shift distance of Integer.MIN_VALUE not supported.");
} else {
return shiftLeft(-n);
}
*** 2894,2904 ****
}
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)
--- 2905,2915 ----
}
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)
*** 2929,2939 ****
* @param val value to be AND'ed with this BigInteger.
* @return {@code this & val}
*/
public BigInteger and(BigInteger val) {
int[] result = new int[Math.max(intLength(), val.intLength())];
! for (int i=0; i<result.length; i++)
result[i] = (getInt(result.length-i-1)
& val.getInt(result.length-i-1));
return valueOf(result);
}
--- 2940,2950 ----
* @param val value to be AND'ed with this BigInteger.
* @return {@code this & val}
*/
public BigInteger and(BigInteger val) {
int[] result = new int[Math.max(intLength(), val.intLength())];
! for (int i=0; i < result.length; i++)
result[i] = (getInt(result.length-i-1)
& val.getInt(result.length-i-1));
return valueOf(result);
}
*** 2946,2956 ****
* @param val value to be OR'ed with this BigInteger.
* @return {@code this | val}
*/
public BigInteger or(BigInteger val) {
int[] result = new int[Math.max(intLength(), val.intLength())];
! for (int i=0; i<result.length; i++)
result[i] = (getInt(result.length-i-1)
| val.getInt(result.length-i-1));
return valueOf(result);
}
--- 2957,2967 ----
* @param val value to be OR'ed with this BigInteger.
* @return {@code this | val}
*/
public BigInteger or(BigInteger val) {
int[] result = new int[Math.max(intLength(), val.intLength())];
! for (int i=0; i < result.length; i++)
result[i] = (getInt(result.length-i-1)
| val.getInt(result.length-i-1));
return valueOf(result);
}
*** 2963,2973 ****
* @param val value to be XOR'ed with this BigInteger.
* @return {@code this ^ val}
*/
public BigInteger xor(BigInteger val) {
int[] result = new int[Math.max(intLength(), val.intLength())];
! for (int i=0; i<result.length; i++)
result[i] = (getInt(result.length-i-1)
^ val.getInt(result.length-i-1));
return valueOf(result);
}
--- 2974,2984 ----
* @param val value to be XOR'ed with this BigInteger.
* @return {@code this ^ val}
*/
public BigInteger xor(BigInteger val) {
int[] result = new int[Math.max(intLength(), val.intLength())];
! for (int i=0; i < result.length; i++)
result[i] = (getInt(result.length-i-1)
^ val.getInt(result.length-i-1));
return valueOf(result);
}
*** 2979,2989 ****
*
* @return {@code ~this}
*/
public BigInteger not() {
int[] result = new int[intLength()];
! for (int i=0; i<result.length; i++)
result[i] = ~getInt(result.length-i-1);
return valueOf(result);
}
--- 2990,3000 ----
*
* @return {@code ~this}
*/
public BigInteger not() {
int[] result = new int[intLength()];
! for (int i=0; i < result.length; i++)
result[i] = ~getInt(result.length-i-1);
return valueOf(result);
}
*** 2997,3007 ****
* @param val value to be complemented and AND'ed with this BigInteger.
* @return {@code this & ~val}
*/
public BigInteger andNot(BigInteger val) {
int[] result = new int[Math.max(intLength(), val.intLength())];
! for (int i=0; i<result.length; i++)
result[i] = (getInt(result.length-i-1)
& ~val.getInt(result.length-i-1));
return valueOf(result);
}
--- 3008,3018 ----
* @param val value to be complemented and AND'ed with this BigInteger.
* @return {@code this & ~val}
*/
public BigInteger andNot(BigInteger val) {
int[] result = new int[Math.max(intLength(), val.intLength())];
! for (int i=0; i < result.length; i++)
result[i] = (getInt(result.length-i-1)
& ~val.getInt(result.length-i-1));
return valueOf(result);
}
*** 3016,3026 ****
* @param n index of bit to test.
* @return {@code true} if and only if the designated bit is set.
* @throws ArithmeticException {@code n} is negative.
*/
public boolean testBit(int n) {
! if (n<0)
throw new ArithmeticException("Negative bit address");
return (getInt(n >>> 5) & (1 << (n & 31))) != 0;
}
--- 3027,3037 ----
* @param n index of bit to test.
* @return {@code true} if and only if the designated bit is set.
* @throws ArithmeticException {@code n} is negative.
*/
public boolean testBit(int n) {
! if (n < 0)
throw new ArithmeticException("Negative bit address");
return (getInt(n >>> 5) & (1 << (n & 31))) != 0;
}
*** 3031,3047 ****
* @param n index of bit to set.
* @return {@code this | (1<<n)}
* @throws ArithmeticException {@code n} is negative.
*/
public BigInteger setBit(int n) {
! if (n<0)
throw new ArithmeticException("Negative bit address");
int intNum = n >>> 5;
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 & 31));
return valueOf(result);
--- 3042,3058 ----
* @param n index of bit to set.
* @return {@code this | (1<<n)}
* @throws ArithmeticException {@code n} is negative.
*/
public BigInteger setBit(int n) {
! if (n < 0)
throw new ArithmeticException("Negative bit address");
int intNum = n >>> 5;
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 & 31));
return valueOf(result);
*** 3055,3071 ****
* @param n index of bit to clear.
* @return {@code this & ~(1<<n)}
* @throws ArithmeticException {@code n} is negative.
*/
public BigInteger clearBit(int n) {
! if (n<0)
throw new ArithmeticException("Negative bit address");
int intNum = n >>> 5;
int[] result = new int[Math.max(intLength(), ((n + 1) >>> 5) + 1)];
! for (int i=0; i<result.length; i++)
result[result.length-i-1] = getInt(i);
result[result.length-intNum-1] &= ~(1 << (n & 31));
return valueOf(result);
--- 3066,3082 ----
* @param n index of bit to clear.
* @return {@code this & ~(1<<n)}
* @throws ArithmeticException {@code n} is negative.
*/
public BigInteger clearBit(int n) {
! if (n < 0)
throw new ArithmeticException("Negative bit address");
int intNum = n >>> 5;
int[] result = new int[Math.max(intLength(), ((n + 1) >>> 5) + 1)];
! for (int i=0; i < result.length; i++)
result[result.length-i-1] = getInt(i);
result[result.length-intNum-1] &= ~(1 << (n & 31));
return valueOf(result);
*** 3079,3095 ****
* @param n index of bit to flip.
* @return {@code this ^ (1<<n)}
* @throws ArithmeticException {@code n} is negative.
*/
public BigInteger flipBit(int n) {
! if (n<0)
throw new ArithmeticException("Negative bit address");
int intNum = n >>> 5;
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 & 31));
return valueOf(result);
--- 3090,3106 ----
* @param n index of bit to flip.
* @return {@code this ^ (1<<n)}
* @throws ArithmeticException {@code n} is negative.
*/
public BigInteger flipBit(int n) {
! if (n < 0)
throw new ArithmeticException("Negative bit address");
int intNum = n >>> 5;
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 & 31));
return valueOf(result);
*** 3097,3107 ****
/**
* 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 {@code (this==0? -1 : log2(this & -this))}.)
*
* @return index of the rightmost one bit in this BigInteger.
*/
public int getLowestSetBit() {
@SuppressWarnings("deprecation") int lsb = lowestSetBit - 2;
--- 3108,3118 ----
/**
* 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 {@code (this == 0? -1 : log2(this & -this))}.)
*
* @return index of the rightmost one bit in this BigInteger.
*/
public int getLowestSetBit() {
@SuppressWarnings("deprecation") int lsb = lowestSetBit - 2;
*** 3110,3120 ****
if (signum == 0) {
lsb -= 1;
} else {
// Search for lowest order nonzero int
int i,b;
! for (i=0; (b = getInt(i))==0; i++)
;
lsb += (i << 5) + Integer.numberOfTrailingZeros(b);
}
lowestSetBit = lsb + 2;
}
--- 3121,3131 ----
if (signum == 0) {
lsb -= 1;
} else {
// Search for lowest order nonzero int
int i,b;
! for (i=0; (b = getInt(i)) == 0; i++)
;
lsb += (i << 5) + Integer.numberOfTrailingZeros(b);
}
lowestSetBit = lsb + 2;
}
*** 3171,3186 ****
public int bitCount() {
@SuppressWarnings("deprecation") int bc = bitCount - 1;
if (bc == -1) { // bitCount not initialized yet
bc = 0; // offset by one to initialize
// Count the bits in the magnitude
! for (int i=0; i<mag.length; i++)
bc += Integer.bitCount(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 += Integer.numberOfTrailingZeros(mag[j]);
bc += magTrailingZeroCount - 1;
}
bitCount = bc + 1;
--- 3182,3197 ----
public int bitCount() {
@SuppressWarnings("deprecation") int bc = bitCount - 1;
if (bc == -1) { // bitCount not initialized yet
bc = 0; // offset by one to initialize
// Count the bits in the magnitude
! for (int i=0; i < mag.length; i++)
bc += Integer.bitCount(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 += Integer.numberOfTrailingZeros(mag[j]);
bc += magTrailingZeroCount - 1;
}
bitCount = bc + 1;
*** 3277,3294 ****
*/
final int compareMagnitude(long val) {
assert val != Long.MIN_VALUE;
int[] m1 = mag;
int len = m1.length;
! if(len > 2) {
return 1;
}
if (val < 0) {
val = -val;
}
int highWord = (int)(val >>> 32);
! if (highWord==0) {
if (len < 1)
return -1;
if (len > 1)
return 1;
int a = m1[0];
--- 3288,3305 ----
*/
final int compareMagnitude(long val) {
assert val != Long.MIN_VALUE;
int[] m1 = mag;
int len = m1.length;
! if (len > 2) {
return 1;
}
if (val < 0) {
val = -val;
}
int highWord = (int)(val >>> 32);
! if (highWord == 0) {
if (len < 1)
return -1;
if (len > 1)
return 1;
int a = m1[0];
*** 3352,3373 ****
* @param val value with which the minimum is to be computed.
* @return the BigInteger whose value is the lesser of this BigInteger and
* {@code val}. If they are equal, either may be returned.
*/
public BigInteger min(BigInteger val) {
! return (compareTo(val)<0 ? this : val);
}
/**
* Returns the maximum of this BigInteger and {@code val}.
*
* @param val value with which the maximum is to be computed.
* @return the BigInteger whose value is the greater of this and
* {@code val}. If they are equal, either may be returned.
*/
public BigInteger max(BigInteger val) {
! return (compareTo(val)>0 ? this : val);
}
// Hash Function
--- 3363,3384 ----
* @param val value with which the minimum is to be computed.
* @return the BigInteger whose value is the lesser of this BigInteger and
* {@code val}. If they are equal, either may be returned.
*/
public BigInteger min(BigInteger val) {
! return (compareTo(val) < 0 ? this : val);
}
/**
* Returns the maximum of this BigInteger and {@code val}.
*
* @param val value with which the maximum is to be computed.
* @return the BigInteger whose value is the greater of this and
* {@code val}. If they are equal, either may be returned.
*/
public BigInteger max(BigInteger val) {
! return (compareTo(val) > 0 ? this : val);
}
// Hash Function
*** 3377,3387 ****
* @return hash code for this BigInteger.
*/
public int hashCode() {
int hashCode = 0;
! for (int i=0; i<mag.length; i++)
hashCode = (int)(31*hashCode + (mag[i] & LONG_MASK));
return hashCode * signum;
}
--- 3388,3398 ----
* @return hash code for this BigInteger.
*/
public int hashCode() {
int hashCode = 0;
! for (int i=0; i < mag.length; i++)
hashCode = (int)(31*hashCode + (mag[i] & LONG_MASK));
return hashCode * signum;
}
*** 3425,3436 ****
return sb.toString();
}
/** This method is used to perform toString when arguments are small. */
private String smallToString(int radix) {
! if (signum == 0)
return "0";
// Compute upper bound on number of digit groups and allocate space
int maxNumDigitGroups = (4*mag.length + 6)/7;
String digitGroup[] = new String[maxNumDigitGroups];
--- 3436,3448 ----
return sb.toString();
}
/** This method is used to perform toString when arguments are small. */
private String smallToString(int radix) {
! if (signum == 0) {
return "0";
+ }
// Compute upper bound on number of digit groups and allocate space
int maxNumDigitGroups = (4*mag.length + 6)/7;
String digitGroup[] = new String[maxNumDigitGroups];
*** 3451,3470 ****
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();
}
--- 3463,3484 ----
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();
}
*** 3488,3500 ****
if (u.mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) {
String s = u.smallToString(radix);
// Pad with internal zeros if necessary.
// Don't pad if we're at the beginning of the string.
! if ((s.length() < digits) && (sb.length() > 0))
! for (int i=s.length(); i<digits; i++) // May be a faster way to
sb.append('0'); // do this?
sb.append(s);
return;
}
--- 3502,3516 ----
if (u.mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) {
String s = u.smallToString(radix);
// Pad with internal zeros if necessary.
// Don't pad if we're at the beginning of the string.
! if ((s.length() < digits) && (sb.length() > 0)) {
! for (int i=s.length(); i < digits; i++) { // May be a faster way to
sb.append('0'); // do this?
+ }
+ }
sb.append(s);
return;
}
*** 3547,3557 ****
/* zero[i] is a string of i consecutive zeros. */
private static String zeros[] = new String[64];
static {
zeros[63] =
"000000000000000000000000000000000000000000000000000000000000000";
! for (int i=0; i<63; i++)
zeros[i] = zeros[63].substring(0, i);
}
/**
* Returns the decimal String representation of this BigInteger.
--- 3563,3573 ----
/* zero[i] is a string of i consecutive zeros. */
private static String zeros[] = new String[64];
static {
zeros[63] =
"000000000000000000000000000000000000000000000000000000000000000";
! for (int i=0; i < 63; i++)
zeros[i] = zeros[63].substring(0, i);
}
/**
* Returns the decimal String representation of this BigInteger.
*** 3585,3595 ****
*/
public byte[] toByteArray() {
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;
--- 3601,3611 ----
*/
public byte[] toByteArray() {
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;
*** 3637,3647 ****
* @see #longValueExact()
*/
public long longValue() {
long result = 0;
! for (int i=1; i>=0; i--)
result = (result << 32) + (getInt(i) & LONG_MASK);
return result;
}
/**
--- 3653,3663 ----
* @see #longValueExact()
*/
public long longValue() {
long result = 0;
! for (int i=1; i >= 0; i--)
result = (result << 32) + (getInt(i) & LONG_MASK);
return result;
}
/**
*** 3853,3863 ****
private static int[] stripLeadingZeroBytes(byte a[]) {
int byteLength = a.length;
int keep;
// Find first nonzero byte
! for (keep = 0; keep < byteLength && a[keep]==0; keep++)
;
// Allocate new array and copy relevant part of input array
int intLength = ((byteLength - keep) + 3) >>> 2;
int[] result = new int[intLength];
--- 3869,3879 ----
private static int[] stripLeadingZeroBytes(byte a[]) {
int byteLength = a.length;
int keep;
// Find first nonzero byte
! for (keep = 0; keep < byteLength && a[keep] == 0; keep++)
;
// Allocate new array and copy relevant part of input array
int intLength = ((byteLength - keep) + 3) >>> 2;
int[] result = new int[intLength];
*** 3879,3898 ****
private static int[] makePositive(byte 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 */
--- 3895,3914 ----
private static int[] makePositive(byte 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 */
*** 3909,3919 ****
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;
}
--- 3925,3935 ----
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;
}
*** 3926,3952 ****
*/
private static int[] makePositive(int 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;
}
--- 3942,3968 ----
*/
private static int[] makePositive(int 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;
}
*** 4200,4210 ****
int bitLen = (len == 0 ? 0 : ((len - 1) << 5) + bitLengthForInt(mag[0]));
int byteLen = (bitLen + 7) >>> 3;
byte[] result = new byte[byteLen];
for (int i = byteLen - 1, bytesCopied = 4, intIndex = len - 1, nextInt = 0;
! i>=0; i--) {
if (bytesCopied == 4) {
nextInt = mag[intIndex--];
bytesCopied = 1;
} else {
nextInt >>>= 8;
--- 4216,4226 ----
int bitLen = (len == 0 ? 0 : ((len - 1) << 5) + bitLengthForInt(mag[0]));
int byteLen = (bitLen + 7) >>> 3;
byte[] result = new byte[byteLen];
for (int i = byteLen - 1, bytesCopied = 4, intIndex = len - 1, nextInt = 0;
! i >= 0; i--) {
if (bytesCopied == 4) {
nextInt = mag[intIndex--];
bytesCopied = 1;
} else {
nextInt >>>= 8;