< prev index next >
src/java.base/share/classes/java/math/BigInteger.java
Print this page
rev 55788 : 8228581: Archive BigInteger constants
Reviewed-by: TBD
@@ -39,10 +39,11 @@
import java.util.concurrent.ThreadLocalRandom;
import jdk.internal.math.DoubleConsts;
import jdk.internal.math.FloatConsts;
import jdk.internal.HotSpotIntrinsicCandidate;
+import jdk.internal.misc.VM;
import jdk.internal.vm.annotation.Stable;
/**
* Immutable arbitrary-precision integers. All operations behave as if
* BigIntegers were represented in two's-complement notation (like Java's
@@ -526,23 +527,23 @@
}
int numWords = (int) (numBits + 31) >>> 5;
int[] magnitude = new int[numWords];
// Process first (potentially short) digit group
- int firstGroupLen = numDigits % digitsPerInt[radix];
+ int firstGroupLen = numDigits % DIGITS_PER_INT[radix];
if (firstGroupLen == 0)
- firstGroupLen = digitsPerInt[radix];
+ firstGroupLen = DIGITS_PER_INT[radix];
String group = val.substring(cursor, cursor += firstGroupLen);
magnitude[numWords - 1] = Integer.parseInt(group, radix);
if (magnitude[numWords - 1] < 0)
throw new NumberFormatException("Illegal digit");
// Process remaining digit groups
- int superRadix = intRadix[radix];
+ int superRadix = INT_RADIX[radix];
int groupVal = 0;
while (cursor < len) {
- group = val.substring(cursor, cursor += digitsPerInt[radix]);
+ group = val.substring(cursor, cursor += DIGITS_PER_INT[radix]);
groupVal = Integer.parseInt(group, radix);
if (groupVal < 0)
throw new NumberFormatException("Illegal digit");
destructiveMulAdd(magnitude, superRadix, groupVal);
}
@@ -586,19 +587,19 @@
numWords = (int) (numBits + 31) >>> 5;
}
int[] magnitude = new int[numWords];
// Process first (potentially short) digit group
- int firstGroupLen = numDigits % digitsPerInt[10];
+ int firstGroupLen = numDigits % DIGITS_PER_INT[10];
if (firstGroupLen == 0)
- firstGroupLen = digitsPerInt[10];
+ firstGroupLen = DIGITS_PER_INT[10];
magnitude[numWords - 1] = parseInt(val, cursor, cursor += firstGroupLen);
// Process remaining digit groups
while (cursor < len) {
- int groupVal = parseInt(val, cursor, cursor += digitsPerInt[10]);
- destructiveMulAdd(magnitude, intRadix[10], groupVal);
+ int groupVal = parseInt(val, cursor, cursor += DIGITS_PER_INT[10]);
+ destructiveMulAdd(magnitude, INT_RADIX[10], groupVal);
}
mag = trustedStripLeadingZeroInts(magnitude);
if (mag.length >= MAX_MAG_LENGTH) {
checkRange();
}
@@ -1168,13 +1169,13 @@
public static BigInteger valueOf(long val) {
// If -MAX_CONSTANT < val < MAX_CONSTANT, return stashed constant
if (val == 0)
return ZERO;
if (val > 0 && val <= MAX_CONSTANT)
- return posConst[(int) val];
+ return POS_CONST[(int) val];
else if (val < 0 && val >= -MAX_CONSTANT)
- return negConst[(int) -val];
+ return NEG_CONST[(int) -val];
return new BigInteger(val);
}
/**
@@ -1213,89 +1214,208 @@
/**
* Initialize static constant array when class is loaded.
*/
private static final int MAX_CONSTANT = 16;
@Stable
- private static final BigInteger[] posConst = new BigInteger[MAX_CONSTANT+1];
+ private static final BigInteger[] POS_CONST;
@Stable
- private static final BigInteger[] negConst = new BigInteger[MAX_CONSTANT+1];
+ private static final BigInteger[] NEG_CONST;
/**
* 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.
*/
private static volatile BigInteger[][] powerCache;
/** The cache of logarithms of radices for base conversion. */
- private static final double[] logCache;
+ private static final double[] LOG_CACHE;
/** The natural log of 2. This is used in computing cache indices. */
private static final double LOG_TWO = Math.log(2.0);
+ /** Precalculated strings of consecutive zeros of index length */
+ private static final String[] ZEROS;
+
+ /*
+ * The following two arrays are used for fast String conversions. Both
+ * are indexed by radix. The first is the number of digits of the given
+ * radix that can fit in a Java long without "going negative", i.e., the
+ * highest integer n such that radix**n < 2**63. The second is the
+ * "long radix" that tears each number into "long digits", each of which
+ * consists of the number of digits in the corresponding element in
+ * DIGITS_PER_LONG (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 final int[] DIGITS_PER_LONG;
+
+ // Initialized in static initializer
+ private static final BigInteger[] LONG_RADIX;
+
+ /*
+ * These two arrays are the integer analogue of above.
+ */
+ private static final int[] DIGITS_PER_INT;
+
+ private static final int[] INT_RADIX;
+
+ /** Archiving proxy */
+ private static Object[] archivedCaches;
+
static {
assert 0 < KARATSUBA_THRESHOLD
&& KARATSUBA_THRESHOLD < TOOM_COOK_THRESHOLD
&& TOOM_COOK_THRESHOLD < Integer.MAX_VALUE
&& 0 < KARATSUBA_SQUARE_THRESHOLD
&& KARATSUBA_SQUARE_THRESHOLD < TOOM_COOK_SQUARE_THRESHOLD
&& TOOM_COOK_SQUARE_THRESHOLD < Integer.MAX_VALUE :
"Algorithm thresholds are inconsistent";
+ VM.initializeFromArchive(BigInteger.class);
+ Object[] caches = archivedCaches;
+ if (caches == null) {
+ BigInteger zero = new BigInteger(new int[0], 0);
+ String[] zeros = new String[64];
+ BigInteger[] posConst = new BigInteger[MAX_CONSTANT+1];
+ BigInteger[] negConst = new BigInteger[MAX_CONSTANT+1];
+
for (int i = 1; i <= MAX_CONSTANT; i++) {
int[] magnitude = new int[1];
magnitude[0] = i;
posConst[i] = new BigInteger(magnitude, 1);
negConst[i] = new BigInteger(magnitude, -1);
}
+ // Need to set these early to allow BigInteger.valueOf to work in
+ // subsequent code.
+ POS_CONST = posConst;
+ NEG_CONST = negConst;
/*
* Initialize the cache of radix^(2^x) values used for base conversion
* with just the very first value. Additional values will be created
* on demand.
*/
- powerCache = new BigInteger[Character.MAX_RADIX+1][];
- logCache = new double[Character.MAX_RADIX+1];
+ BigInteger[][] initialPowerCache = new BigInteger[Character.MAX_RADIX + 1][];
+ double[] 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) };
+ for (int i = Character.MIN_RADIX; i <= Character.MAX_RADIX; i++) {
+ initialPowerCache[i] = new BigInteger[]{ BigInteger.valueOf(i) };
logCache[i] = Math.log(i);
}
+
+ // Initialize caches used for fast String conversion
+
+ zeros[63] = "000000000000000000000000000000000000000000000000000000000000000";
+ for (int i = 0; i < 63; i++) {
+ zeros[i] = zeros[63].substring(0, i);
+ }
+
+ BigInteger x1 = valueOf(0x1000000000000000L);
+ BigInteger x4 = valueOf(0x4000000000000000L);
+ BigInteger[] longRadix = {null, null,
+ x4, valueOf(0x383d9170b85ff80bL),
+ x4, valueOf(0x6765c793fa10079dL),
+ valueOf(0x41c21cb8e1000000L), valueOf(0x3642798750226111L),
+ x1, valueOf(0x12bf307ae81ffd59L),
+ valueOf( 0xde0b6b3a7640000L), valueOf(0x4d28cb56c33fa539L),
+ valueOf(0x1eca170c00000000L), valueOf(0x780c7372621bd74dL),
+ valueOf(0x1e39a5057d810000L), valueOf(0x5b27ac993df97701L),
+ x1, valueOf(0x27b95e997e21d9f1L),
+ valueOf(0x5da0e1e53c5c8000L), valueOf( 0xb16a458ef403f19L),
+ valueOf(0x16bcc41e90000000L), valueOf(0x2d04b7fdd9c0ef49L),
+ valueOf(0x5658597bcaa24000L), valueOf( 0x6feb266931a75b7L),
+ valueOf( 0xc29e98000000000L), valueOf(0x14adf4b7320334b9L),
+ valueOf(0x226ed36478bfa000L), valueOf(0x383d9170b85ff80bL),
+ valueOf(0x5a3c23e39c000000L), valueOf( 0x4e900abb53e6b71L),
+ valueOf( 0x7600ec618141000L), valueOf( 0xaee5720ee830681L),
+ x1, valueOf(0x172588ad4f5f0981L),
+ valueOf(0x211e44f7d02c1000L), valueOf(0x2ee56725f06e5c71L),
+ valueOf(0x41c21cb8e1000000L)};
+
+ 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};
+
+ 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};
+
+ 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,
+ 0x17179149, 0x1cb91000, 0x23744899, 0x2b73a840, 0x34e63b41,
+ 0x40000000, 0x4cfa3cc1, 0x5c13d840, 0x6d91b519, 0x39aa400
+ };
+
+ archivedCaches = caches = new Object[] {
+ posConst,
+ negConst,
+ zero,
+ zeros,
+ initialPowerCache,
+ logCache,
+ longRadix,
+ digitsPerLong,
+ digitsPerInt,
+ intRadix
+ };
+
+ } else {
+ POS_CONST = (BigInteger[])caches[0];
+ NEG_CONST = (BigInteger[])caches[1];
+ }
+
+ ZERO = (BigInteger)caches[2];
+ ONE = POS_CONST[1];
+ TWO = POS_CONST[2];
+ TEN = POS_CONST[10];
+ NEGATIVE_ONE = NEG_CONST[1];
+ ZEROS = (String[])caches[3];
+ powerCache = (BigInteger[][])caches[4];
+ LOG_CACHE = (double[])caches[5];
+ LONG_RADIX = (BigInteger[])caches[6];
+ DIGITS_PER_LONG = (int[])caches[7];
+ DIGITS_PER_INT = (int[])caches[8];
+ INT_RADIX = (int[])caches[9];
}
/**
* The BigInteger constant zero.
*
* @since 1.2
*/
- public static final BigInteger ZERO = new BigInteger(new int[0], 0);
+ public static final BigInteger ZERO;
/**
* The BigInteger constant one.
*
* @since 1.2
*/
- public static final BigInteger ONE = valueOf(1);
+ public static final BigInteger ONE;
/**
* The BigInteger constant two.
*
* @since 9
*/
- public static final BigInteger TWO = valueOf(2);
+ public static final BigInteger TWO;
/**
* The BigInteger constant -1. (Not exported.)
*/
- private static final BigInteger NEGATIVE_ONE = valueOf(-1);
+ private static final BigInteger NEGATIVE_ONE;
/**
* The BigInteger constant ten.
*
* @since 1.5
*/
- public static final BigInteger TEN = valueOf(10);
+ public static final BigInteger TEN;
// Arithmetic Operations
/**
* Returns a BigInteger whose value is {@code (this + val)}.
@@ -2728,11 +2848,11 @@
return (m.equals(ONE) ? ZERO : ONE);
if (this.equals(ZERO) && exponent.signum >= 0)
return ZERO;
- if (this.equals(negConst[1]) && (!exponent.testBit(0)))
+ if (this.equals(NEG_CONST[1]) && (!exponent.testBit(0)))
return (m.equals(ONE) ? ZERO : ONE);
boolean invertResult;
if ((invertResult = (exponent.signum < 0)))
exponent = exponent.negate();
@@ -3399,11 +3519,11 @@
int magLen = mag.length;
int newMag[] = null;
// Special case: entire contents shifted off the end
if (nInts >= magLen)
- return (signum >= 0 ? ZERO : negConst[1]);
+ return (signum >= 0 ? ZERO : NEG_CONST[1]);
if (nBits == 0) {
int newMagLen = magLen - nInts;
newMag = Arrays.copyOf(mag, newMagLen);
} else {
@@ -3966,11 +4086,11 @@
// 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];
+ BigInteger d = LONG_RADIX[radix];
MutableBigInteger q = new MutableBigInteger(),
a = new MutableBigInteger(tmp.mag),
b = new MutableBigInteger(d.mag);
MutableBigInteger r = a.divide(b, q);
@@ -3980,22 +4100,22 @@
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);
+ StringBuilder buf = new StringBuilder(numGroups* DIGITS_PER_LONG[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--) {
+ for (int i = numGroups-2; i >= 0; i--) {
// Prepend (any) leading zeros for this digit group
- int numLeadingZeros = digitsPerLong[radix]-digitGroup[i].length();
+ int numLeadingZeros = DIGITS_PER_LONG[radix]-digitGroup[i].length();
if (numLeadingZeros != 0) {
- buf.append(zeros[numLeadingZeros]);
+ buf.append(ZEROS[numLeadingZeros]);
}
buf.append(digitGroup[i]);
}
return buf.toString();
}
@@ -4036,11 +4156,11 @@
b = u.bitLength();
// Calculate a value for n in the equation radix^(2^n) = u
// and subtract 1 from that value. This is used to find the
// cache index that contains the best value to divide u.
- n = (int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) / LOG_TWO - 1.0);
+ n = (int) Math.round(Math.log(b * LOG_TWO / LOG_CACHE[radix]) / LOG_TWO - 1.0);
BigInteger v = getRadixConversionCache(radix, n);
BigInteger[] results;
results = u.divideAndRemainder(v);
int expectedDigits = 1 << n;
@@ -4076,19 +4196,10 @@
powerCache = pc; // volatile write, publish
}
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);
- }
-
/**
* Returns the decimal String representation of this BigInteger.
* The digit-to-character mapping provided by
* {@code Character.forDigit} is used, and a minus sign is
* prepended if appropriate. (This representation is compatible
@@ -4486,62 +4597,10 @@
;
return result;
}
- /*
- * The following two arrays are used for fast String conversions. Both
- * are indexed by radix. The first is the number of digits of the given
- * radix that can fit in a Java long without "going negative", i.e., the
- * highest integer n such that radix**n < 2**63. The second is the
- * "long radix" that tears each number into "long digits", each of which
- * 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),
- valueOf(0x1eca170c00000000L), valueOf(0x780c7372621bd74dL),
- valueOf(0x1e39a5057d810000L), valueOf(0x5b27ac993df97701L),
- valueOf(0x1000000000000000L), valueOf(0x27b95e997e21d9f1L),
- valueOf(0x5da0e1e53c5c8000L), valueOf( 0xb16a458ef403f19L),
- valueOf(0x16bcc41e90000000L), valueOf(0x2d04b7fdd9c0ef49L),
- valueOf(0x5658597bcaa24000L), valueOf( 0x6feb266931a75b7L),
- valueOf( 0xc29e98000000000L), valueOf(0x14adf4b7320334b9L),
- valueOf(0x226ed36478bfa000L), valueOf(0x383d9170b85ff80bL),
- valueOf(0x5a3c23e39c000000L), valueOf( 0x4e900abb53e6b71L),
- valueOf( 0x7600ec618141000L), valueOf( 0xaee5720ee830681L),
- valueOf(0x1000000000000000L), valueOf(0x172588ad4f5f0981L),
- valueOf(0x211e44f7d02c1000L), valueOf(0x2ee56725f06e5c71L),
- 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,
- 0x17179149, 0x1cb91000, 0x23744899, 0x2b73a840, 0x34e63b41,
- 0x40000000, 0x4cfa3cc1, 0x5c13d840, 0x6d91b519, 0x39aa400
- };
-
/**
* These routines provide access to the two's complement representation
* of BigIntegers.
*/
@@ -4551,15 +4610,10 @@
*/
private int intLength() {
return (bitLength() >>> 5) + 1;
}
- /* Returns sign bit */
- private int signBit() {
- return signum < 0 ? 1 : 0;
- }
-
/* Returns an int of sign bits */
private int signInt() {
return signum < 0 ? -1 : 0;
}
< prev index next >