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(radix, sb);
3951 return sb.toString();
3952 }
3953
3954 // Otherwise use recursive toString.
3955 // The results will be concatenated into this StringBuilder
3956 toString(this, sb, radix, 0);
3957
3958 return sb.toString();
3959 }
3960
3961 /** This method is used to perform toString when arguments are small. */
3962 private int smallToString(int radix, StringBuilder buf) {
3963 if (signum == 0) {
3964 buf.append('0');
3965 return 1;
3966 }
3967
3968 // Compute upper bound on number of digit groups and allocate space
3969 int maxNumDigitGroups = (4*mag.length + 6)/7;
3970 long[] digitGroups = new long[maxNumDigitGroups];
3971
3972 // Translate number to string, a digit group at a time
3973 BigInteger tmp = this.abs();
3974 int numGroups = 0;
3975 while (tmp.signum != 0) {
3976 BigInteger d = longRadix[radix];
3977
3978 MutableBigInteger q = new MutableBigInteger(),
3979 a = new MutableBigInteger(tmp.mag),
3980 b = new MutableBigInteger(d.mag);
3981 MutableBigInteger r = a.divide(b, q);
3982 BigInteger q2 = q.toBigInteger(tmp.signum * d.signum);
3983 BigInteger r2 = r.toBigInteger(tmp.signum * d.signum);
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.
4027 * @param digits The minimum number of digits to pad 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.
4075 toString(results[0], sb, radix, digits-expectedDigits);
4076 toString(results[1], sb, radix, expectedDigits);
4077 }
4078
4079 /**
4080 * Returns the value radix^(2^exponent) from the cache.
4081 * If this value doesn't already exist in the cache, it is added.
4082 * <p>
4083 * This could be changed to a more complicated caching method using
4084 * {@code Future}.
4085 */
4086 private static BigInteger getRadixConversionCache(int radix, int exponent) {
4087 BigInteger[] cacheLine = powerCache[radix]; // volatile read
|
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 /**
3964 * This method is used to perform toString when arguments are small.
3965 * A negative sign will be prepended if and only if {@code this < 0}.
3966 * If {@code digits <= 0} no padding (pre-pending with zeros) will be
3967 * effected.
3968 *
3969 * @param radix The base to convert to.
3970 * @param sb The StringBuilder that will be appended to in place.
3971 * @param digits The minimum number of digits to pad to.
3972 */
3973 private void smallToString(int radix, StringBuilder buf, int digits) {
3974 if (signum == 0) {
3975 buf.append('0');
3976 return;
3977 }
3978
3979 // Put sign (if any) into result buffer
3980 if (signum < 0) {
3981 buf.append('-');
3982 }
3983
3984 // Compute upper bound on number of digit groups and allocate space
3985 int maxNumDigitGroups = (4*mag.length + 6)/7;
3986 long[] digitGroups = new long[maxNumDigitGroups];
3987
3988 // Translate number to string, a digit group at a time
3989 BigInteger tmp = this.abs();
3990 int numGroups = 0;
3991 while (tmp.signum != 0) {
3992 BigInteger d = longRadix[radix];
3993
3994 MutableBigInteger q = new MutableBigInteger(),
3995 a = new MutableBigInteger(tmp.mag),
3996 b = new MutableBigInteger(d.mag);
3997 MutableBigInteger r = a.divide(b, q);
3998 BigInteger q2 = q.toBigInteger(tmp.signum * d.signum);
3999 BigInteger r2 = r.toBigInteger(tmp.signum * d.signum);
4000
4001 digitGroups[numGroups++] = r2.longValue();
4002 tmp = q2;
4003 }
4004
4005 // Get string version of first digit group
4006 String s = Long.toString(digitGroups[numGroups-1], radix);
4007
4008 // Pad with internal zeros if necessary.
4009 if (digits > 0) {
4010 int len = s.length() + (numGroups - 1)*digitsPerLong[radix];
4011 if (len < digits) {
4012 int m = digits - len;
4013 while (m >= NUM_ZEROS) {
4014 buf.append(zeros);
4015 m -= NUM_ZEROS;
4016 }
4017 if (m > 0) {
4018 buf.append(zeros, 0, m);
4019 }
4020 }
4021 }
4022
4023 // Put first digit group into result buffer
4024 buf.append(s);
4025
4026 // Append remaining digit groups each padded with leading zeros
4027 for (int i=numGroups-2; i >= 0; i--) {
4028 // Prepend (any) leading zeros for this digit group
4029 s = Long.toString(digitGroups[i], radix);
4030 int numLeadingZeros = digitsPerLong[radix] - s.length();
4031 if (numLeadingZeros != 0) {
4032 buf.append(zeros, 0, numLeadingZeros);
4033 }
4034 buf.append(s);
4035 }
4036 }
4037
4038 /**
4039 * Converts the specified BigInteger to a string and appends to
4040 * {@code sb}. This implements the recursive Schoenhage algorithm
4041 * for base conversions.
4042 * <p>
4043 * See Knuth, Donald, _The Art of Computer Programming_, Vol. 2,
4044 * Answers to Exercises (4.4) Question 14.
4045 *
4046 * @param u The number to convert to a string.
4047 * @param sb The StringBuilder that will be appended to in place.
4048 * @param radix The base to convert to.
4049 * @param digits The minimum number of digits to pad to.
4050 */
4051 private static void toString(BigInteger u, StringBuilder sb,
4052 int radix, int digits) {
4053 // We're at the beginning if nothing is in the StringBuilder.
4054 boolean atBeginning = sb.length() == 0;
4055
4056 // Make negative values positive and prepend a negative sign.
4057 if (u.signum() < 0) {
4058 u = u.negate();
4059 sb.append('-');
4060 }
4061
4062 // If we're smaller than a certain threshold, use the smallToString
4063 // method, padding with leading zeroes when necessary unless we're
4064 // at the beginning of the string or digits <= 0. As u.signum() >= 0,
4065 // smallToString() will not prepend a negative sign.
4066 if (u.mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) {
4067 u.smallToString(radix, sb, atBeginning ? -1 : digits);
4068 return;
4069 }
4070
4071 // Calculate a value for n in the equation radix^(2^n) = u
4072 // and subtract 1 from that value. This is used to find the
4073 // cache index that contains the best value to divide u.
4074 int b = u.bitLength();
4075 int n = (int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) /
4076 LOG_TWO - 1.0);
4077
4078 BigInteger v = getRadixConversionCache(radix, n);
4079 BigInteger[] results;
4080 results = u.divideAndRemainder(v);
4081
4082 int expectedDigits = 1 << n;
4083
4084 // Now recursively build the two halves of each number.
4085 toString(results[0], sb, radix, digits-expectedDigits);
4086 toString(results[1], sb, radix, expectedDigits);
4087 }
4088
4089 /**
4090 * Returns the value radix^(2^exponent) from the cache.
4091 * If this value doesn't already exist in the cache, it is added.
4092 * <p>
4093 * This could be changed to a more complicated caching method using
4094 * {@code Future}.
4095 */
4096 private static BigInteger getRadixConversionCache(int radix, int exponent) {
4097 BigInteger[] cacheLine = powerCache[radix]; // volatile read
|