3984
3985 digitGroups[numGroups++] = r2.longValue();
3986 tmp = q2;
3987 }
3988
3989 int count = 0;
3990
3991 // Put sign (if any) and first digit group into result buffer
3992 if (signum < 0) {
3993 buf.append('-');
3994 count++;
3995 }
3996 String s = Long.toString(digitGroups[numGroups-1], radix);
3997 buf.append(s);
3998 count += s.length();
3999
4000 // Append remaining digit groups padded with leading zeros
4001 for (int i=numGroups-2; i >= 0; i--) {
4002 // Prepend (any) leading zeros for this digit group
4003 s = Long.toString(digitGroups[i], radix);
4004 int numLeadingZeros = digitsPerLong[radix]-s.length();
4005 if (numLeadingZeros != 0) {
4006 buf.append(zeros[numLeadingZeros]);
4007 count += numLeadingZeros;
4008 }
4009 buf.append(s);
4010 count += s.length();
4011 }
4012
4013 return count;
4014 }
4015
4016 /**
4017 * Converts the specified BigInteger to a string and appends to
4018 * {@code sb}. This implements the recursive Schoenhage algorithm
4019 * for base conversions.
4020 * <p>
4021 * See Knuth, Donald, _The Art of Computer Programming_, Vol. 2,
4022 * Answers to Exercises (4.4) Question 14.
4023 *
4024 * @param u The number to convert to a string.
4025 * @param sb The StringBuilder that will be appended to in place.
4026 * @param radix The base to convert to.
4028 */
4029 private static void toString(BigInteger u, StringBuilder sb,
4030 int radix, int digits) {
4031 boolean atBeginning = sb.length() == 0;
4032 if (u.signum() < 0) {
4033 u = u.negate();
4034 sb.append('-');
4035 }
4036
4037 // If we're smaller than a certain threshold, use the smallToString
4038 // method, padding with leading zeroes when necessary.
4039 if (u.mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) {
4040 // Save current position.
4041 int pos = sb.length();
4042 int len = u.smallToString(radix, sb);
4043
4044 // Pad with internal zeros if necessary.
4045 // Don't pad if we're at the beginning of the string.
4046 if (!atBeginning && len < digits) {
4047 int m = digits - len;
4048 int zl1 = zeros.length - 1;
4049 while (m >= zl1) {
4050 sb.insert(pos, zeros[zl1]);
4051 pos += zl1;
4052 m -= zl1;
4053 }
4054 if (m > 0) {
4055 sb.insert(pos, zeros[m]);
4056 }
4057 }
4058
4059 return;
4060 }
4061
4062 int b = u.bitLength();
4063
4064 // Calculate a value for n in the equation radix^(2^n) = u
4065 // and subtract 1 from that value. This is used to find the
4066 // cache index that contains the best value to divide u.
4067 int n = (int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) /
4068 LOG_TWO - 1.0);
4069 BigInteger v = getRadixConversionCache(radix, n);
4070 BigInteger[] results;
4071 results = u.divideAndRemainder(v);
4072
4073 int expectedDigits = 1 << n;
4074
4075 // Now recursively build the two halves of each number.
4088 BigInteger[] cacheLine = powerCache[radix]; // volatile read
4089 if (exponent < cacheLine.length) {
4090 return cacheLine[exponent];
4091 }
4092
4093 int oldLength = cacheLine.length;
4094 cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
4095 for (int i = oldLength; i <= exponent; i++) {
4096 cacheLine[i] = cacheLine[i - 1].pow(2);
4097 }
4098
4099 BigInteger[][] pc = powerCache; // volatile read again
4100 if (exponent >= pc[radix].length) {
4101 pc = pc.clone();
4102 pc[radix] = cacheLine;
4103 powerCache = pc; // volatile write, publish
4104 }
4105 return cacheLine[exponent];
4106 }
4107
4108 /* zero[i] is a string of i consecutive zeros. */
4109 private static String[] zeros = new String[64];
4110 static {
4111 zeros[63] =
4112 "000000000000000000000000000000000000000000000000000000000000000";
4113 for (int i=0; i < 63; i++)
4114 zeros[i] = zeros[63].substring(0, i);
4115 }
4116
4117 /**
4118 * Returns the decimal String representation of this BigInteger.
4119 * The digit-to-character mapping provided by
4120 * {@code Character.forDigit} is used, and a minus sign is
4121 * prepended if appropriate. (This representation is compatible
4122 * with the {@link #BigInteger(String) (String)} constructor, and
4123 * allows for String concatenation with Java's + operator.)
4124 *
4125 * @return decimal String representation of this BigInteger.
4126 * @see Character#forDigit
4127 * @see #BigInteger(java.lang.String)
4128 */
4129 public String toString() {
4130 return toString(10);
4131 }
4132
4133 /**
4134 * Returns a byte array containing the two's-complement
4135 * representation of this BigInteger. The byte array will be in
|
3984
3985 digitGroups[numGroups++] = r2.longValue();
3986 tmp = q2;
3987 }
3988
3989 int count = 0;
3990
3991 // Put sign (if any) and first digit group into result buffer
3992 if (signum < 0) {
3993 buf.append('-');
3994 count++;
3995 }
3996 String s = Long.toString(digitGroups[numGroups-1], radix);
3997 buf.append(s);
3998 count += s.length();
3999
4000 // Append remaining digit groups padded with leading zeros
4001 for (int i=numGroups-2; i >= 0; i--) {
4002 // Prepend (any) leading zeros for this digit group
4003 s = Long.toString(digitGroups[i], radix);
4004 int numLeadingZeros = digitsPerLong[radix] - s.length();
4005 if (numLeadingZeros != 0) {
4006 buf.append(zeros, 0, numLeadingZeros);
4007 count += numLeadingZeros;
4008 }
4009 buf.append(s);
4010 count += s.length();
4011 }
4012
4013 return count;
4014 }
4015
4016 /**
4017 * Converts the specified BigInteger to a string and appends to
4018 * {@code sb}. This implements the recursive Schoenhage algorithm
4019 * for base conversions.
4020 * <p>
4021 * See Knuth, Donald, _The Art of Computer Programming_, Vol. 2,
4022 * Answers to Exercises (4.4) Question 14.
4023 *
4024 * @param u The number to convert to a string.
4025 * @param sb The StringBuilder that will be appended to in place.
4026 * @param radix The base to convert to.
4028 */
4029 private static void toString(BigInteger u, StringBuilder sb,
4030 int radix, int digits) {
4031 boolean atBeginning = sb.length() == 0;
4032 if (u.signum() < 0) {
4033 u = u.negate();
4034 sb.append('-');
4035 }
4036
4037 // If we're smaller than a certain threshold, use the smallToString
4038 // method, padding with leading zeroes when necessary.
4039 if (u.mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) {
4040 // Save current position.
4041 int pos = sb.length();
4042 int len = u.smallToString(radix, sb);
4043
4044 // Pad with internal zeros if necessary.
4045 // Don't pad if we're at the beginning of the string.
4046 if (!atBeginning && len < digits) {
4047 int m = digits - len;
4048 while (m >= NUM_ZEROS) {
4049 sb.insert(pos, zeros, 0, NUM_ZEROS);
4050 pos += NUM_ZEROS;
4051 m -= NUM_ZEROS;
4052 }
4053 if (m > 0) {
4054 sb.insert(pos, zeros, 0, m);
4055 }
4056 }
4057
4058 return;
4059 }
4060
4061 int b = u.bitLength();
4062
4063 // Calculate a value for n in the equation radix^(2^n) = u
4064 // and subtract 1 from that value. This is used to find the
4065 // cache index that contains the best value to divide u.
4066 int n = (int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) /
4067 LOG_TWO - 1.0);
4068 BigInteger v = getRadixConversionCache(radix, n);
4069 BigInteger[] results;
4070 results = u.divideAndRemainder(v);
4071
4072 int expectedDigits = 1 << n;
4073
4074 // Now recursively build the two halves of each number.
4087 BigInteger[] cacheLine = powerCache[radix]; // volatile read
4088 if (exponent < cacheLine.length) {
4089 return cacheLine[exponent];
4090 }
4091
4092 int oldLength = cacheLine.length;
4093 cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
4094 for (int i = oldLength; i <= exponent; i++) {
4095 cacheLine[i] = cacheLine[i - 1].pow(2);
4096 }
4097
4098 BigInteger[][] pc = powerCache; // volatile read again
4099 if (exponent >= pc[radix].length) {
4100 pc = pc.clone();
4101 pc[radix] = cacheLine;
4102 powerCache = pc; // volatile write, publish
4103 }
4104 return cacheLine[exponent];
4105 }
4106
4107 /* Size of zeros string. */
4108 private static int NUM_ZEROS = 63;
4109
4110 /* zero is a string of NUM_ZEROS consecutive zeros. */
4111 private static final String zeros = "0".repeat(NUM_ZEROS);
4112
4113 /**
4114 * Returns the decimal String representation of this BigInteger.
4115 * The digit-to-character mapping provided by
4116 * {@code Character.forDigit} is used, and a minus sign is
4117 * prepended if appropriate. (This representation is compatible
4118 * with the {@link #BigInteger(String) (String)} constructor, and
4119 * allows for String concatenation with Java's + operator.)
4120 *
4121 * @return decimal String representation of this BigInteger.
4122 * @see Character#forDigit
4123 * @see #BigInteger(java.lang.String)
4124 */
4125 public String toString() {
4126 return toString(10);
4127 }
4128
4129 /**
4130 * Returns a byte array containing the two's-complement
4131 * representation of this BigInteger. The byte array will be in
|