3920 * Character#MIN_RADIX} to {@link Character#MAX_RADIX} inclusive,
3921 * it will default to 10 (as is the case for
3922 * {@code Integer.toString}). The digit-to-character mapping
3923 * provided by {@code Character.forDigit} is used, and a minus
3924 * sign is prepended if appropriate. (This representation is
3925 * compatible with the {@link #BigInteger(String, int) (String,
3926 * int)} constructor.)
3927 *
3928 * @param radix radix of the String representation.
3929 * @return String representation of this BigInteger in the given radix.
3930 * @see Integer#toString
3931 * @see Character#forDigit
3932 * @see #BigInteger(java.lang.String, int)
3933 */
3934 public String toString(int radix) {
3935 if (signum == 0)
3936 return "0";
3937 if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
3938 radix = 10;
3939
3940 // Ensure buffer capacity sufficient to contain string representation
3941 // floor(bitLength*log(2)/log(radix)) + 1
3942 // plus an additional character for the sign if negative.
3943 int b = this.abs().bitLength();
3944 int numChars = (int)(Math.floor(b*LOG_TWO/logCache[radix]) + 1) +
3945 (signum < 0 ? 1 : 0);
3946 StringBuilder sb = new StringBuilder(numChars);
3947
3948 // If it's small enough, use smallToString.
3949 if (mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) {
3950 // smallToString() will prepend a negative sign if this < 0,
3951 // but will not pad with any leading zeros.
3952 smallToString(radix, sb, -1);
3953 return sb.toString();
3954 }
3955
3956 // Otherwise use recursive toString.
3957 // The results will be concatenated into this StringBuilder
3958 toString(this, sb, radix, 0);
3959
3960 return sb.toString();
3961 }
3962
3963 private static void padWithZeros(StringBuilder buf, int len, int digits) {
3964 if (digits > 0 && len < digits) {
3965 int m = digits - len;
3966 while (m >= NUM_ZEROS) {
3967 buf.append(ZEROS);
3968 m -= NUM_ZEROS;
3969 }
3970 if (m > 0) {
3971 buf.append(ZEROS, 0, m);
3972 }
3973 }
3974 }
3975
3976 /**
3977 * This method is used to perform toString when arguments are small.
3978 * A negative sign will be prepended if and only if {@code this < 0}.
3979 * If {@code digits <= 0} no padding (pre-pending with zeros) will be
3980 * effected.
3981 *
3982 * @param radix The base to convert to.
3983 * @param sb The StringBuilder that will be appended to in place.
3984 * @param digits The minimum number of digits to pad to.
3985 */
3986 private void smallToString(int radix, StringBuilder buf, int digits) {
3987 if (signum == 0) {
3988 buf.append('0');
3989 padWithZeros(buf, 1, digits);
3990 return;
3991 }
3992
3993 // Put sign (if any) into result buffer
3994 if (signum < 0) {
3995 buf.append('-');
3996 }
3997
3998 // Compute upper bound on number of digit groups and allocate space
3999 int maxNumDigitGroups = (4*mag.length + 6)/7;
4000 long[] digitGroups = new long[maxNumDigitGroups];
4001
4002 // Translate number to string, a digit group at a time
4003 BigInteger tmp = this.abs();
4004 int numGroups = 0;
4005 while (tmp.signum != 0) {
4006 BigInteger d = longRadix[radix];
4007
4008 MutableBigInteger q = new MutableBigInteger(),
4009 a = new MutableBigInteger(tmp.mag),
4010 b = new MutableBigInteger(d.mag);
4011 MutableBigInteger r = a.divide(b, q);
4012 BigInteger q2 = q.toBigInteger(tmp.signum * d.signum);
4013 BigInteger r2 = r.toBigInteger(tmp.signum * d.signum);
4014
4015 digitGroups[numGroups++] = r2.longValue();
4016 tmp = q2;
4017 }
4018
4019 // Get string version of first digit group
4020 String s = Long.toString(digitGroups[numGroups-1], radix);
4021
4022 // Pad with internal zeros if necessary.
4023 padWithZeros(buf, s.length() + (numGroups - 1)*digitsPerLong[radix],
4024 digits);
4025
4026 // Put first digit group into result buffer
4027 buf.append(s);
4028
4029 // Append remaining digit groups each padded with leading zeros
4030 for (int i=numGroups-2; i >= 0; i--) {
4031 // Prepend (any) leading zeros for this digit group
4032 s = Long.toString(digitGroups[i], radix);
4033 int numLeadingZeros = digitsPerLong[radix] - s.length();
4034 if (numLeadingZeros != 0) {
4035 buf.append(ZEROS, 0, numLeadingZeros);
4036 }
4037 buf.append(s);
4038 }
4039 }
4040
4041 /**
4042 * Converts the specified BigInteger to a string and appends to
4043 * {@code sb}. This implements the recursive Schoenhage algorithm
4044 * for base conversions.
4045 * <p>
4046 * See Knuth, Donald, _The Art of Computer Programming_, Vol. 2,
4047 * Answers to Exercises (4.4) Question 14.
4048 *
4049 * @param u The number to convert to a string.
4050 * @param sb The StringBuilder that will be appended to in place.
4051 * @param radix The base to convert to.
4052 * @param digits The minimum number of digits to pad to.
4053 */
4054 private static void toString(BigInteger u, StringBuilder sb,
4055 int radix, int digits) {
4056 // We're at the beginning if nothing is in the StringBuilder.
4057 boolean atBeginning = sb.length() == 0;
4058
4059 // Make negative values positive and prepend a negative sign.
4060 if (u.signum() < 0) {
4061 u = u.negate();
4062 sb.append('-');
4063 }
4064
4065 // If we're smaller than a certain threshold, use the smallToString
4066 // method, padding with leading zeroes when necessary unless we're
4067 // at the beginning of the string or digits <= 0. As u.signum() >= 0,
4068 // smallToString() will not prepend a negative sign.
4069 if (u.mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) {
4070 u.smallToString(radix, sb, atBeginning ? -1 : digits);
4071 return;
4072 }
4073
4074 // Calculate a value for n in the equation radix^(2^n) = u
4075 // and subtract 1 from that value. This is used to find the
4076 // cache index that contains the best value to divide u.
4077 int b = u.bitLength();
4078 int n = (int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) /
4079 LOG_TWO - 1.0);
4080
4081 BigInteger v = getRadixConversionCache(radix, n);
4082 BigInteger[] results;
4083 results = u.divideAndRemainder(v);
4084
4085 int expectedDigits = 1 << n;
4086
4087 // Now recursively build the two halves of each number.
4088 toString(results[0], sb, radix, digits-expectedDigits);
4089 toString(results[1], sb, radix, expectedDigits);
4090 }
4091
4092 /**
4093 * Returns the value radix^(2^exponent) from the cache.
4094 * If this value doesn't already exist in the cache, it is added.
4095 * <p>
4096 * This could be changed to a more complicated caching method using
4097 * {@code Future}.
4098 */
4099 private static BigInteger getRadixConversionCache(int radix, int exponent) {
4100 BigInteger[] cacheLine = powerCache[radix]; // volatile read
4101 if (exponent < cacheLine.length) {
4102 return cacheLine[exponent];
4103 }
4104
4105 int oldLength = cacheLine.length;
4106 cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
4107 for (int i = oldLength; i <= exponent; i++) {
4108 cacheLine[i] = cacheLine[i - 1].pow(2);
|
3920 * Character#MIN_RADIX} to {@link Character#MAX_RADIX} inclusive,
3921 * it will default to 10 (as is the case for
3922 * {@code Integer.toString}). The digit-to-character mapping
3923 * provided by {@code Character.forDigit} is used, and a minus
3924 * sign is prepended if appropriate. (This representation is
3925 * compatible with the {@link #BigInteger(String, int) (String,
3926 * int)} constructor.)
3927 *
3928 * @param radix radix of the String representation.
3929 * @return String representation of this BigInteger in the given radix.
3930 * @see Integer#toString
3931 * @see Character#forDigit
3932 * @see #BigInteger(java.lang.String, int)
3933 */
3934 public String toString(int radix) {
3935 if (signum == 0)
3936 return "0";
3937 if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
3938 radix = 10;
3939
3940 BigInteger abs = this.abs();
3941
3942 // Ensure buffer capacity sufficient to contain string representation
3943 // floor(bitLength*log(2)/log(radix)) + 1
3944 // plus an additional character for the sign if negative.
3945 int b = abs.bitLength();
3946 int numChars = (int)(Math.floor(b*LOG_TWO/logCache[radix]) + 1) +
3947 (signum < 0 ? 1 : 0);
3948 StringBuilder sb = new StringBuilder(numChars);
3949
3950 if (signum < 0) {
3951 sb.append('-');
3952 }
3953
3954 // Use recursive toString.
3955 toString(abs, sb, radix, 0);
3956
3957 return sb.toString();
3958 }
3959
3960 /**
3961 * If {@code numZeros > 0}, appends that many zeros to the
3962 * specified StringBuilder; otherwise, does nothing.
3963 *
3964 * @param sb The StringBuilder that will be appended to.
3965 * @param numZeros The number of zeros to append.
3966 */
3967 private static void padWithZeros(StringBuilder buf, int numZeros) {
3968 while (numZeros >= NUM_ZEROS) {
3969 buf.append(ZEROS);
3970 numZeros -= NUM_ZEROS;
3971 }
3972 if (numZeros > 0) {
3973 buf.append(ZEROS, 0, numZeros);
3974 }
3975 }
3976
3977 /**
3978 * This method is used to perform toString when arguments are small.
3979 * The value must be non-negative. If {@code digits <= 0} no padding
3980 * (pre-pending with zeros) will be effected.
3981 *
3982 * @param radix The base to convert to.
3983 * @param sb The StringBuilder that will be appended to in place.
3984 * @param digits The minimum number of digits to pad to.
3985 */
3986 private void smallToString(int radix, StringBuilder buf, int digits) {
3987 assert signum >= 0;
3988
3989 if (signum == 0) {
3990 if (digits > 0) {
3991 padWithZeros(buf, digits);
3992 } else {
3993 buf.append('0');
3994 }
3995 return;
3996 }
3997
3998 // Compute upper bound on number of digit groups and allocate space
3999 int maxNumDigitGroups = (4*mag.length + 6)/7;
4000 long[] digitGroups = new long[maxNumDigitGroups];
4001
4002 // Translate number to string, a digit group at a time
4003 BigInteger tmp = this;
4004 int numGroups = 0;
4005 while (tmp.signum != 0) {
4006 BigInteger d = longRadix[radix];
4007
4008 MutableBigInteger q = new MutableBigInteger(),
4009 a = new MutableBigInteger(tmp.mag),
4010 b = new MutableBigInteger(d.mag);
4011 MutableBigInteger r = a.divide(b, q);
4012 BigInteger q2 = q.toBigInteger(tmp.signum * d.signum);
4013 BigInteger r2 = r.toBigInteger(tmp.signum * d.signum);
4014
4015 digitGroups[numGroups++] = r2.longValue();
4016 tmp = q2;
4017 }
4018
4019 // Get string version of first digit group
4020 String s = Long.toString(digitGroups[numGroups-1], radix);
4021
4022 // Pad with internal zeros if necessary.
4023 padWithZeros(buf, digits - (s.length() +
4024 (numGroups - 1)*digitsPerLong[radix]));
4025
4026 // Put first digit group into result buffer
4027 buf.append(s);
4028
4029 // Append remaining digit groups each padded with leading zeros
4030 for (int i=numGroups-2; i >= 0; i--) {
4031 // Prepend (any) leading zeros for this digit group
4032 s = Long.toString(digitGroups[i], radix);
4033 int numLeadingZeros = digitsPerLong[radix] - s.length();
4034 if (numLeadingZeros != 0) {
4035 buf.append(ZEROS, 0, numLeadingZeros);
4036 }
4037 buf.append(s);
4038 }
4039 }
4040
4041 /**
4042 * Converts the specified BigInteger to a string and appends to
4043 * {@code sb}. This implements the recursive Schoenhage algorithm
4044 * for base conversions. This method can only be called for non-negative
4045 * numbers.
4046 * <p>
4047 * See Knuth, Donald, _The Art of Computer Programming_, Vol. 2,
4048 * Answers to Exercises (4.4) Question 14.
4049 *
4050 * @param u The number to convert to a string.
4051 * @param sb The StringBuilder that will be appended to in place.
4052 * @param radix The base to convert to.
4053 * @param digits The minimum number of digits to pad to.
4054 */
4055 private static void toString(BigInteger u, StringBuilder sb,
4056 int radix, int digits) {
4057 assert u.signum() >= 0;
4058
4059 // If we're smaller than a certain threshold, use the smallToString
4060 // method, padding with leading zeroes when necessary unless we're
4061 // at the beginning of the string or digits <= 0. As u.signum() >= 0,
4062 // smallToString() will not prepend a negative sign.
4063 if (u.mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) {
4064 u.smallToString(radix, sb, digits);
4065 return;
4066 }
4067
4068 // Calculate a value for n in the equation radix^(2^n) = u
4069 // and subtract 1 from that value. This is used to find the
4070 // cache index that contains the best value to divide u.
4071 int b = u.bitLength();
4072 int n = (int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) /
4073 LOG_TWO - 1.0);
4074
4075 BigInteger v = getRadixConversionCache(radix, n);
4076 BigInteger[] results;
4077 results = u.divideAndRemainder(v);
4078
4079 int expectedDigits = 1 << n;
4080
4081 // Now recursively build the two halves of each number.
4082 toString(results[0], sb, radix, digits - expectedDigits);
4083 toString(results[1], sb, radix, expectedDigits);
4084 }
4085
4086 /**
4087 * Returns the value radix^(2^exponent) from the cache.
4088 * If this value doesn't already exist in the cache, it is added.
4089 * <p>
4090 * This could be changed to a more complicated caching method using
4091 * {@code Future}.
4092 */
4093 private static BigInteger getRadixConversionCache(int radix, int exponent) {
4094 BigInteger[] cacheLine = powerCache[radix]; // volatile read
4095 if (exponent < cacheLine.length) {
4096 return cacheLine[exponent];
4097 }
4098
4099 int oldLength = cacheLine.length;
4100 cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
4101 for (int i = oldLength; i <= exponent; i++) {
4102 cacheLine[i] = cacheLine[i - 1].pow(2);
|