< prev index next >
src/java.base/share/classes/java/math/BigInteger.java
Print this page
@@ -1,7 +1,7 @@
/*
- * Copyright (c) 1996, 2018, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1996, 2019, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
@@ -3935,36 +3935,57 @@
if (signum == 0)
return "0";
if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
radix = 10;
+ // Ensure buffer capacity sufficient to contain string representation
+ // floor(bitLength*log(2)/log(radix)) + 1
+ // plus an additional character for the sign if negative.
+ int b = this.abs().bitLength();
+ int numChars = (int)(Math.floor(b*LOG_TWO/logCache[radix]) + 1) +
+ (signum < 0 ? 1 : 0);
+ StringBuilder sb = new StringBuilder(numChars);
+
// If it's small enough, use smallToString.
- if (mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD)
- return smallToString(radix);
+ if (mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) {
+ // smallToString() will prepend a negative sign if this < 0,
+ // but will not pad with any leading zeros.
+ smallToString(radix, sb, -1);
+ return sb.toString();
+ }
- // Otherwise use recursive toString, which requires positive arguments.
+ // Otherwise use recursive toString.
// 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) {
+ /**
+ * This method is used to perform toString when arguments are small.
+ * A negative sign will be prepended if and only if {@code this < 0}.
+ * If {@code digits <= 0} no padding (pre-pending with zeros) will be
+ * effected.
+ *
+ * @param radix The base to convert to.
+ * @param sb The StringBuilder that will be appended to in place.
+ * @param digits The minimum number of digits to pad to.
+ */
+ private void smallToString(int radix, StringBuilder buf, int digits) {
if (signum == 0) {
- return "0";
+ buf.append('0');
+ return;
+ }
+
+ // Put sign (if any) into result buffer
+ if (signum < 0) {
+ buf.append('-');
}
// Compute upper bound on number of digit groups and allocate space
int maxNumDigitGroups = (4*mag.length + 6)/7;
- String digitGroup[] = new String[maxNumDigitGroups];
+ long[] digitGroups = new long[maxNumDigitGroups];
// Translate number to string, a digit group at a time
BigInteger tmp = this.abs();
int numGroups = 0;
while (tmp.signum != 0) {
@@ -3975,31 +3996,45 @@
b = new MutableBigInteger(d.mag);
MutableBigInteger r = a.divide(b, q);
BigInteger q2 = q.toBigInteger(tmp.signum * d.signum);
BigInteger r2 = r.toBigInteger(tmp.signum * d.signum);
- digitGroup[numGroups++] = Long.toString(r2.longValue(), radix);
+ digitGroups[numGroups++] = r2.longValue();
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('-');
+ // Get string version of first digit group
+ String s = Long.toString(digitGroups[numGroups-1], radix);
+
+ // Pad with internal zeros if necessary.
+ if (digits > 0) {
+ int len = s.length() + (numGroups - 1)*digitsPerLong[radix];
+ if (len < digits) {
+ int m = digits - len;
+ while (m >= NUM_ZEROS) {
+ buf.append(zeros);
+ m -= NUM_ZEROS;
+ }
+ if (m > 0) {
+ buf.append(zeros, 0, m);
+ }
}
- buf.append(digitGroup[numGroups-1]);
+ }
+
+ // Put first digit group into result buffer
+ buf.append(s);
- // Append remaining digit groups padded with leading zeros
+ // Append remaining digit groups each 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();
+ s = Long.toString(digitGroups[i], radix);
+ int numLeadingZeros = digitsPerLong[radix] - s.length();
if (numLeadingZeros != 0) {
- buf.append(zeros[numLeadingZeros]);
+ buf.append(zeros, 0, numLeadingZeros);
}
- buf.append(digitGroup[i]);
+ buf.append(s);
}
- return buf.toString();
}
/**
* Converts the specified BigInteger to a string and appends to
* {@code sb}. This implements the recursive Schoenhage algorithm
@@ -4011,36 +4046,37 @@
* @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++) {
- sb.append('0');
- }
+ private static void toString(BigInteger u, StringBuilder sb,
+ int radix, int digits) {
+ // We're at the beginning if nothing is in the StringBuilder.
+ boolean atBeginning = sb.length() == 0;
+
+ // Make negative values positive and prepend a negative sign.
+ if (u.signum() < 0) {
+ u = u.negate();
+ sb.append('-');
}
- sb.append(s);
+ // If we're smaller than a certain threshold, use the smallToString
+ // method, padding with leading zeroes when necessary unless we're
+ // at the beginning of the string or digits <= 0. As u.signum() >= 0,
+ // smallToString() will not prepend a negative sign.
+ if (u.mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) {
+ u.smallToString(radix, sb, atBeginning ? -1 : digits);
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);
+ int b = u.bitLength();
+ int 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;
@@ -4076,18 +4112,15 @@
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);
- }
+ /* Size of zeros string. */
+ private static int NUM_ZEROS = 63;
+
+ /* zero is a string of NUM_ZEROS consecutive zeros. */
+ private static final String zeros = "0".repeat(NUM_ZEROS);
/**
* 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
< prev index next >