4641897: Faster string conversion of large integers
Accelerate conversion to string by means of Schoenhage recursive base conversion.
Reviewed-by: bpb, alanb
diff --git a/jdk/src/share/classes/java/math/BigInteger.java b/jdk/src/share/classes/java/math/BigInteger.java
index 8972ac7..48354a9 100644
--- a/jdk/src/share/classes/java/math/BigInteger.java
+++ b/jdk/src/share/classes/java/math/BigInteger.java
@@ -33,6 +33,7 @@
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.ObjectStreamField;
+import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import sun.misc.DoubleConsts;
@@ -213,6 +214,16 @@
*/
private static final int TOOM_COOK_SQUARE_THRESHOLD = 140;
+ /**
+ * The threshold value for using Schoenhage recursive base conversion. If
+ * the number of ints in the number are larger than this value,
+ * the Schoenhage algorithm will be used. In practice, it appears that the
+ * Schoenhage routine is faster for any threshold down to 2, and is
+ * relatively flat for thresholds between 2-25, so this choice may be
+ * varied within this range for very small effect.
+ */
+ private static final int SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 8;
+
//Constructors
/**
@@ -1026,6 +1037,19 @@
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.
+ */
+ private static ArrayList<BigInteger>[] powerCache;
+
+ /** The cache of logarithms of radices for base conversion. */
+ private static final double[] logCache;
+
+ /** The natural log of 2. This is used in computing cache indices. */
+ private static final double LOG_TWO = Math.log(2.0);
+
static {
for (int i = 1; i <= MAX_CONSTANT; i++) {
int[] magnitude = new int[1];
@@ -1033,6 +1057,22 @@
posConst[i] = new BigInteger(magnitude, 1);
negConst[i] = new BigInteger(magnitude, -1);
}
+
+ /*
+ * 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 = (ArrayList<BigInteger>[])
+ new ArrayList[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 ArrayList<BigInteger>(1);
+ powerCache[i].add(BigInteger.valueOf(i));
+ logCache[i] = Math.log(i);
+ }
}
/**
@@ -1357,7 +1397,7 @@
if ((xlen < TOOM_COOK_THRESHOLD) && (ylen < TOOM_COOK_THRESHOLD))
return multiplyKaratsuba(this, val);
else
- return multiplyToomCook3(this, val);
+ return multiplyToomCook3(this, val);
}
private static BigInteger multiplyByInt(int[] x, int y, int sign) {
@@ -3299,6 +3339,28 @@
if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
radix = 10;
+ // If it's small enough, use smallToString.
+ if (mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD)
+ return smallToString(radix);
+
+ // Otherwise use recursive toString, which requires positive arguments.
+ // The results will be concatenated into this StringBuilder
+ StringBuilder sb = new StringBuilder();
+ if (signum < 0) {
+ toString(this.negate(), sb, radix, 0);
+ sb.insert(0, '-');
+ }
+ else
+ toString(this, sb, radix, 0);
+
+ 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];
@@ -3337,6 +3399,78 @@
return buf.toString();
}
+ /**
+ * Converts the specified BigInteger to a string and appends to
+ * <code>sb</code>. This implements the recursive Schoenhage algorithm
+ * for base conversions.
+ * <p/>
+ * See Knuth, Donald, _The Art of Computer Programming_, Vol. 2,
+ * Answers to Exercises (4.4) Question 14.
+ *
+ * @param u The number to convert to a string.
+ * @param sb The StringBuilder that will be appended to in place.
+ * @param radix The base to convert to.
+ * @param digits The minimum number of digits to pad to.
+ */
+ private static void toString(BigInteger u, StringBuilder sb, int radix,
+ int digits) {
+ /* If we're smaller than a certain threshold, use the smallToString
+ method, padding with leading zeroes when necessary. */
+ 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;
+ }
+
+ int b, n;
+ 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);
+ BigInteger v = getRadixConversionCache(radix, n);
+ BigInteger[] results;
+ results = u.divideAndRemainder(v);
+
+ int expectedDigits = 1 << n;
+
+ // Now recursively build the two halves of each number.
+ toString(results[0], sb, radix, digits-expectedDigits);
+ toString(results[1], sb, radix, expectedDigits);
+ }
+
+ /**
+ * Returns the value radix^(2^exponent) from the cache.
+ * If this value doesn't already exist in the cache, it is added.
+ * <p/>
+ * This could be changed to a more complicated caching method using
+ * <code>Future</code>.
+ */
+ private static synchronized BigInteger getRadixConversionCache(int radix,
+ int exponent) {
+ BigInteger retVal = null;
+ ArrayList<BigInteger> cacheLine = powerCache[radix];
+ int oldSize = cacheLine.size();
+ if (exponent >= oldSize) {
+ cacheLine.ensureCapacity(exponent+1);
+ for (int i=oldSize; i<=exponent; i++) {
+ retVal = cacheLine.get(i-1).square();
+ cacheLine.add(i, retVal);
+ }
+ }
+ else
+ retVal = cacheLine.get(exponent);
+
+ return retVal;
+ }
/* zero[i] is a string of i consecutive zeros. */
private static String zeros[] = new String[64];
diff --git a/jdk/test/java/math/BigInteger/BigIntegerTest.java b/jdk/test/java/math/BigInteger/BigIntegerTest.java
index 4522d44..17c58bc 100644
--- a/jdk/test/java/math/BigInteger/BigIntegerTest.java
+++ b/jdk/test/java/math/BigInteger/BigIntegerTest.java
@@ -61,10 +61,13 @@
// KARATSUBA_SQUARE_THRESHOLD = 90 ints = 2880 bits
// TOOM_COOK_SQUARE_THRESHOLD = 140 ints = 4480 bits
//
+ // SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 8 ints = 256 bits
+ //
static final int BITS_KARATSUBA = 1600;
static final int BITS_TOOM_COOK = 2400;
static final int BITS_KARATSUBA_SQUARE = 2880;
static final int BITS_TOOM_COOK_SQUARE = 4480;
+ static final int BITS_SCHOENHAGE_BASE = 256;
static final int ORDER_SMALL = 60;
static final int ORDER_MEDIUM = 100;
@@ -467,12 +470,13 @@
public static void stringConv() {
int failCount = 0;
+ // Generic string conversion.
for (int i=0; i<100; i++) {
byte xBytes[] = new byte[Math.abs(rnd.nextInt())%100+1];
rnd.nextBytes(xBytes);
BigInteger x = new BigInteger(xBytes);
- for (int radix=2; radix < 37; radix++) {
+ for (int radix=Character.MIN_RADIX; radix < Character.MAX_RADIX; radix++) {
String result = x.toString(radix);
BigInteger test = new BigInteger(result, radix);
if (!test.equals(x)) {
@@ -483,6 +487,32 @@
}
}
}
+
+ // String conversion straddling the Schoenhage algorithm crossover
+ // threshold, and at twice and four times the threshold.
+ for (int k = 0; k <= 2; k++) {
+ int factor = 1 << k;
+ int upper = factor * BITS_SCHOENHAGE_BASE + 33;
+ int lower = upper - 35;
+
+ for (int bits = upper; bits >= lower; bits--) {
+ for (int i = 0; i < 50; i++) {
+ BigInteger x = BigInteger.ONE.shiftLeft(bits - 1).or(new BigInteger(bits - 2, rnd));
+
+ for (int radix = Character.MIN_RADIX; radix < Character.MAX_RADIX; radix++) {
+ String result = x.toString(radix);
+ BigInteger test = new BigInteger(result, radix);
+ if (!test.equals(x)) {
+ failCount++;
+ System.err.println("BigInteger toString: " + x);
+ System.err.println("Test: " + test);
+ System.err.println(radix);
+ }
+ }
+ }
+ }
+ }
+
report("String Conversion", failCount);
}
