< prev index next >
src/java.base/share/classes/java/math/BigInteger.java
Print this page
*** 627,637 ****
return result;
}
// bitsPerDigit in the given radix times 1024
// Rounded up to avoid underallocation.
! private static long bitsPerDigit[] = { 0, 0,
1024, 1624, 2048, 2378, 2648, 2875, 3072, 3247, 3402, 3543, 3672,
3790, 3899, 4001, 4096, 4186, 4271, 4350, 4426, 4498, 4567, 4633,
4696, 4756, 4814, 4870, 4923, 4975, 5025, 5074, 5120, 5166, 5210,
5253, 5295};
--- 627,637 ----
return result;
}
// bitsPerDigit in the given radix times 1024
// Rounded up to avoid underallocation.
! private static long[] bitsPerDigit = { 0, 0,
1024, 1624, 2048, 2378, 2648, 2875, 3072, 3247, 3402, 3543, 3672,
3790, 3899, 4001, 4096, 4186, 4271, 4350, 4426, 4498, 4567, 4633,
4696, 4756, 4814, 4870, 4923, 4975, 5025, 5074, 5120, 5166, 5210,
5253, 5295};
*** 778,788 ****
*
* This method assumes bitLength > 1.
*/
private static BigInteger smallPrime(int bitLength, int certainty, Random rnd) {
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
--- 778,788 ----
*
* This method assumes bitLength > 1.
*/
private static BigInteger smallPrime(int bitLength, int certainty, Random rnd) {
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
*** 1207,1228 ****
/**
* 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
/**
* Initialize static constant array when class is loaded.
*/
private static final int MAX_CONSTANT = 16;
! private static BigInteger posConst[] = new BigInteger[MAX_CONSTANT+1];
! private static BigInteger negConst[] = new BigInteger[MAX_CONSTANT+1];
/**
* The cache of powers of each radix. This allows us to not have to
* recalculate powers of radix^(2^n) more than once. This speeds
* Schoenhage recursive base conversion significantly.
--- 1207,1228 ----
/**
* 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
/**
* Initialize static constant array when class is loaded.
*/
private static final int MAX_CONSTANT = 16;
! private static BigInteger[] posConst = new BigInteger[MAX_CONSTANT+1];
! private static BigInteger[] negConst = new BigInteger[MAX_CONSTANT+1];
/**
* The cache of powers of each radix. This allows us to not have to
* recalculate powers of radix^(2^n) more than once. This speeds
* Schoenhage recursive base conversion significantly.
*** 1373,1383 ****
// Copy remainder of longer number
while (xIndex > 0)
result[--xIndex] = x[xIndex];
// Grow result if necessary
if (carry) {
! int bigger[] = new int[result.length + 1];
System.arraycopy(result, 0, bigger, 1, result.length);
bigger[0] = 0x01;
return bigger;
}
return result;
--- 1373,1383 ----
// Copy remainder of longer number
while (xIndex > 0)
result[--xIndex] = x[xIndex];
// Grow result if necessary
if (carry) {
! int[] bigger = new int[result.length + 1];
System.arraycopy(result, 0, bigger, 1, result.length);
bigger[0] = 0x01;
return bigger;
}
return result;
*** 1396,1406 ****
y = tmp;
}
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 {
--- 1396,1406 ----
y = tmp;
}
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 {
*** 1420,1445 ****
while (xIndex > 0)
result[--xIndex] = x[xIndex];
// Grow result if necessary
if (carry) {
! int bigger[] = new int[result.length + 1];
System.arraycopy(result, 0, bigger, 1, result.length);
bigger[0] = 0x01;
return bigger;
}
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);
--- 1420,1445 ----
while (xIndex > 0)
result[--xIndex] = x[xIndex];
// Grow result if necessary
if (carry) {
! int[] bigger = new int[result.length + 1];
System.arraycopy(result, 0, bigger, 1, result.length);
bigger[0] = 0x01;
return bigger;
}
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);
*** 1467,1477 ****
* assumes val >= 0
*/
private static int[] subtract(int[] big, long val) {
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;
--- 1467,1477 ----
* assumes val >= 0
*/
private static int[] subtract(int[] big, long val) {
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;
*** 1523,1533 ****
* than the second. This method allocates the space necessary to hold the
* answer.
*/
private static int[] subtract(int[] big, int[] little) {
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) {
--- 1523,1533 ----
* than the second. This method allocates the space necessary to hold the
* answer.
*/
private static int[] subtract(int[] big, int[] little) {
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) {
*** 1888,1898 ****
// 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);
}
--- 1888,1898 ----
// 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);
}
*** 1945,1955 ****
if (len <= n) {
return abs();
}
! int lowerInts[] = new int[n];
System.arraycopy(mag, len-n, lowerInts, 0, n);
return new BigInteger(trustedStripLeadingZeroInts(lowerInts), 1);
}
--- 1945,1955 ----
if (len <= n) {
return abs();
}
! int[] lowerInts = new int[n];
System.arraycopy(mag, len-n, lowerInts, 0, n);
return new BigInteger(trustedStripLeadingZeroInts(lowerInts), 1);
}
*** 1964,1974 ****
if (len <= n) {
return ZERO;
}
int upperLen = len - n;
! int upperInts[] = new int[upperLen];
System.arraycopy(mag, 0, upperInts, 0, upperLen);
return new BigInteger(trustedStripLeadingZeroInts(upperInts), 1);
}
--- 1964,1974 ----
if (len <= n) {
return ZERO;
}
int upperLen = len - n;
! int[] upperInts = new int[upperLen];
System.arraycopy(mag, 0, upperInts, 0, upperLen);
return new BigInteger(trustedStripLeadingZeroInts(upperInts), 1);
}
*** 2506,2521 ****
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];
System.arraycopy(a, 0, result, 0, len);
primitiveLeftShift(result, result.length, nBits);
return result;
} else {
! int result[] = new int[nInts+len+1];
System.arraycopy(a, 0, result, 0, len);
primitiveRightShift(result, result.length, 32 - nBits);
return result;
}
}
--- 2506,2521 ----
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];
System.arraycopy(a, 0, result, 0, len);
primitiveLeftShift(result, result.length, nBits);
return result;
} else {
! int[] result = new int[nInts+len+1];
System.arraycopy(a, 0, result, 0, len);
primitiveRightShift(result, result.length, 32 - nBits);
return result;
}
}
*** 3238,3248 ****
*/
private static int[] shiftLeft(int[] mag, int n) {
int nInts = n >>> 5;
int nBits = n & 0x1f;
int magLen = mag.length;
! int newMag[] = null;
if (nBits == 0) {
newMag = new int[magLen + nInts];
System.arraycopy(mag, 0, newMag, 0, magLen);
} else {
--- 3238,3248 ----
*/
private static int[] shiftLeft(int[] mag, int n) {
int nInts = n >>> 5;
int nBits = n & 0x1f;
int magLen = mag.length;
! int[] newMag = null;
if (nBits == 0) {
newMag = new int[magLen + nInts];
System.arraycopy(mag, 0, newMag, 0, magLen);
} else {
*** 3297,3307 ****
*/
private BigInteger shiftRightImpl(int 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]);
--- 3297,3307 ----
*/
private BigInteger shiftRightImpl(int 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]);
*** 3862,3872 ****
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];
// Translate number to string, a digit group at a time
BigInteger tmp = this.abs();
int numGroups = 0;
while (tmp.signum != 0) {
--- 3862,3872 ----
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];
// Translate number to string, a digit group at a time
BigInteger tmp = this.abs();
int numGroups = 0;
while (tmp.signum != 0) {
*** 3979,3989 ****
}
return cacheLine[exponent];
}
/* 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);
--- 3979,3989 ----
}
return cacheLine[exponent];
}
/* 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);
*** 4261,4271 ****
}
/**
* Returns a copy of the input array stripped of any leading zero bytes.
*/
! private static int[] stripLeadingZeroInts(int val[]) {
int vlen = val.length;
int keep;
// Find first nonzero byte
for (keep = 0; keep < vlen && val[keep] == 0; keep++)
--- 4261,4271 ----
}
/**
* Returns a copy of the input array stripped of any leading zero bytes.
*/
! private static int[] stripLeadingZeroInts(int[] val) {
int vlen = val.length;
int keep;
// Find first nonzero byte
for (keep = 0; keep < vlen && val[keep] == 0; keep++)
*** 4275,4285 ****
/**
* Returns the input array stripped of any leading zero bytes.
* Since the source is trusted the copying may be skipped.
*/
! private static int[] trustedStripLeadingZeroInts(int val[]) {
int vlen = val.length;
int keep;
// Find first nonzero byte
for (keep = 0; keep < vlen && val[keep] == 0; keep++)
--- 4275,4285 ----
/**
* Returns the input array stripped of any leading zero bytes.
* Since the source is trusted the copying may be skipped.
*/
! private static int[] trustedStripLeadingZeroInts(int[] val) {
int vlen = val.length;
int keep;
// Find first nonzero byte
for (keep = 0; keep < vlen && val[keep] == 0; keep++)
*** 4288,4298 ****
}
/**
* Returns a copy of the input array stripped of any leading zero bytes.
*/
! private static int[] stripLeadingZeroBytes(byte a[], int off, int len) {
int indexBound = off + len;
int keep;
// Find first nonzero byte
for (keep = off; keep < indexBound && a[keep] == 0; keep++)
--- 4288,4298 ----
}
/**
* Returns a copy of the input array stripped of any leading zero bytes.
*/
! private static int[] stripLeadingZeroBytes(byte[] a, int off, int len) {
int indexBound = off + len;
int keep;
// Find first nonzero byte
for (keep = off; keep < indexBound && a[keep] == 0; keep++)
*** 4314,4324 ****
/**
* Takes an array a representing a negative 2's-complement number and
* returns the minimal (no leading zero bytes) unsigned whose value is -a.
*/
! private static int[] makePositive(byte a[], int off, int len) {
int keep, k;
int indexBound = off + len;
// Find first non-sign (0xff) byte of input
for (keep=off; keep < indexBound && a[keep] == -1; keep++)
--- 4314,4324 ----
/**
* Takes an array a representing a negative 2's-complement number and
* returns the minimal (no leading zero bytes) unsigned whose value is -a.
*/
! private static int[] makePositive(byte[] a, int off, int len) {
int keep, k;
int indexBound = off + len;
// Find first non-sign (0xff) byte of input
for (keep=off; keep < indexBound && a[keep] == -1; keep++)
*** 4330,4340 ****
for (k=keep; k < indexBound && a[k] == 0; k++)
;
int extraByte = (k == indexBound) ? 1 : 0;
int intLength = ((indexBound - keep + extraByte) + 3) >>> 2;
! int result[] = new int[intLength];
/* Copy one's complement of input into output, leaving extra
* byte (if it exists) == 0x00 */
int b = indexBound - 1;
for (int i = intLength-1; i >= 0; i--) {
--- 4330,4340 ----
for (k=keep; k < indexBound && a[k] == 0; k++)
;
int extraByte = (k == indexBound) ? 1 : 0;
int intLength = ((indexBound - keep + extraByte) + 3) >>> 2;
! int[] result = new int[intLength];
/* Copy one's complement of input into output, leaving extra
* byte (if it exists) == 0x00 */
int b = indexBound - 1;
for (int i = intLength-1; i >= 0; i--) {
*** 4362,4372 ****
/**
* Takes an array a representing a negative 2's-complement number and
* returns the minimal (no leading zero ints) unsigned whose value is -a.
*/
! 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++)
;
--- 4362,4372 ----
/**
* Takes an array a representing a negative 2's-complement number and
* returns the minimal (no leading zero ints) unsigned whose value is -a.
*/
! 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++)
;
*** 4374,4384 ****
/* 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];
--- 4374,4384 ----
/* 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];
*** 4399,4413 ****
* consists of the number of digits in the corresponding element in
* digitsPerLong (longRadix[i] = i**digitPerLong[i]). Both arrays have
* nonsense values in their 0 and 1 elements, as radixes 0 and 1 are not
* used.
*/
! private static int digitsPerLong[] = {0, 0,
62, 39, 31, 27, 24, 22, 20, 19, 18, 18, 17, 17, 16, 16, 15, 15, 15, 14,
14, 14, 14, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12};
! private static BigInteger longRadix[] = {null, null,
valueOf(0x4000000000000000L), valueOf(0x383d9170b85ff80bL),
valueOf(0x4000000000000000L), valueOf(0x6765c793fa10079dL),
valueOf(0x41c21cb8e1000000L), valueOf(0x3642798750226111L),
valueOf(0x1000000000000000L), valueOf(0x12bf307ae81ffd59L),
valueOf( 0xde0b6b3a7640000L), valueOf(0x4d28cb56c33fa539L),
--- 4399,4413 ----
* consists of the number of digits in the corresponding element in
* digitsPerLong (longRadix[i] = i**digitPerLong[i]). Both arrays have
* nonsense values in their 0 and 1 elements, as radixes 0 and 1 are not
* used.
*/
! private static int[] digitsPerLong = {0, 0,
62, 39, 31, 27, 24, 22, 20, 19, 18, 18, 17, 17, 16, 16, 15, 15, 15, 14,
14, 14, 14, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12};
! private static BigInteger[] longRadix = {null, null,
valueOf(0x4000000000000000L), valueOf(0x383d9170b85ff80bL),
valueOf(0x4000000000000000L), valueOf(0x6765c793fa10079dL),
valueOf(0x41c21cb8e1000000L), valueOf(0x3642798750226111L),
valueOf(0x1000000000000000L), valueOf(0x12bf307ae81ffd59L),
valueOf( 0xde0b6b3a7640000L), valueOf(0x4d28cb56c33fa539L),
*** 4426,4440 ****
valueOf(0x41c21cb8e1000000L)};
/*
* These two arrays are the integer analogue of above.
*/
! private static int digitsPerInt[] = {0, 0, 30, 19, 15, 13, 11,
11, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5};
! private static int intRadix[] = {0, 0,
0x40000000, 0x4546b3db, 0x40000000, 0x48c27395, 0x159fd800,
0x75db9c97, 0x40000000, 0x17179149, 0x3b9aca00, 0xcc6db61,
0x19a10000, 0x309f1021, 0x57f6c100, 0xa2f1b6f, 0x10000000,
0x18754571, 0x247dbc80, 0x3547667b, 0x4c4b4000, 0x6b5a6e1d,
0x6c20a40, 0x8d2d931, 0xb640000, 0xe8d4a51, 0x1269ae40,
--- 4426,4440 ----
valueOf(0x41c21cb8e1000000L)};
/*
* These two arrays are the integer analogue of above.
*/
! private static int[] digitsPerInt = {0, 0, 30, 19, 15, 13, 11,
11, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5};
! private static int[] intRadix = {0, 0,
0x40000000, 0x4546b3db, 0x40000000, 0x48c27395, 0x159fd800,
0x75db9c97, 0x40000000, 0x17179149, 0x3b9aca00, 0xcc6db61,
0x19a10000, 0x309f1021, 0x57f6c100, 0xa2f1b6f, 0x10000000,
0x18754571, 0x247dbc80, 0x3547667b, 0x4c4b4000, 0x6b5a6e1d,
0x6c20a40, 0x8d2d931, 0xb640000, 0xe8d4a51, 0x1269ae40,
< prev index next >