src/share/classes/java/math/BigInteger.java
Print this page
rev 7474 : 4641897: Faster string conversion of large integers
Summary: Accelerate conversion to string by means of Schoenhage recursive base conversion.
Reviewed-by: bpb
Contributed-by: Alan Eliasen <eliasen@mindspring.com>
*** 31,40 ****
--- 31,41 ----
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.ObjectStreamField;
+ import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
/**
* Immutable arbitrary-precision integers. All operations behave as if
*** 209,218 ****
--- 210,229 ----
* Toom-Cook squaring will be used. This value is found
* experimentally to work well.
*/
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
/**
* Translates a byte array containing the two's-complement binary
* representation of a BigInteger into a BigInteger. The input array is
*** 1022,1038 ****
--- 1033,1078 ----
*/
private final static 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.
+ */
+ 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];
magnitude[0] = i;
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);
+ }
}
/**
* The BigInteger constant zero.
*
*** 3295,3304 ****
--- 3335,3366 ----
if (signum == 0)
return "0";
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];
// Translate number to string, a digit group at a time
*** 3333,3342 ****
--- 3395,3476 ----
buf.append(digitGroup[i]);
}
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];
static {
zeros[63] =