1 /*
2 * Copyright (c) 1996, 2018, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
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 // If it's small enough, use smallToString.
3941 if (mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD)
3942 return smallToString(radix);
3943
3944 // Otherwise use recursive toString, which requires positive arguments.
3945 // The results will be concatenated into this StringBuilder
3946 StringBuilder sb = new StringBuilder();
3947 if (signum < 0) {
3948 toString(this.negate(), sb, radix, 0);
3949 sb.insert(0, '-');
3950 }
3951 else
3952 toString(this, sb, radix, 0);
3953
3954 return sb.toString();
3955 }
3956
3957 /** This method is used to perform toString when arguments are small. */
3958 private String smallToString(int radix) {
3959 if (signum == 0) {
3960 return "0";
3961 }
3962
3963 // Compute upper bound on number of digit groups and allocate space
3964 int maxNumDigitGroups = (4*mag.length + 6)/7;
3965 String digitGroup[] = new String[maxNumDigitGroups];
3966
3967 // Translate number to string, a digit group at a time
3968 BigInteger tmp = this.abs();
3969 int numGroups = 0;
3970 while (tmp.signum != 0) {
3971 BigInteger d = longRadix[radix];
3972
3973 MutableBigInteger q = new MutableBigInteger(),
3974 a = new MutableBigInteger(tmp.mag),
3975 b = new MutableBigInteger(d.mag);
3976 MutableBigInteger r = a.divide(b, q);
3977 BigInteger q2 = q.toBigInteger(tmp.signum * d.signum);
3978 BigInteger r2 = r.toBigInteger(tmp.signum * d.signum);
3979
3980 digitGroup[numGroups++] = Long.toString(r2.longValue(), radix);
3981 tmp = q2;
3982 }
3983
3984 // Put sign (if any) and first digit group into result buffer
3985 StringBuilder buf = new StringBuilder(numGroups*digitsPerLong[radix]+1);
3986 if (signum < 0) {
3987 buf.append('-');
3988 }
3989 buf.append(digitGroup[numGroups-1]);
3990
3991 // Append remaining digit groups padded with leading zeros
3992 for (int i=numGroups-2; i >= 0; i--) {
3993 // Prepend (any) leading zeros for this digit group
3994 int numLeadingZeros = digitsPerLong[radix]-digitGroup[i].length();
3995 if (numLeadingZeros != 0) {
3996 buf.append(zeros[numLeadingZeros]);
3997 }
3998 buf.append(digitGroup[i]);
3999 }
4000 return buf.toString();
4001 }
4002
4003 /**
4004 * Converts the specified BigInteger to a string and appends to
4005 * {@code sb}. This implements the recursive Schoenhage algorithm
4006 * for base conversions.
4007 * <p>
4008 * See Knuth, Donald, _The Art of Computer Programming_, Vol. 2,
4009 * Answers to Exercises (4.4) Question 14.
4010 *
4011 * @param u The number to convert to a string.
4012 * @param sb The StringBuilder that will be appended to in place.
4013 * @param radix The base to convert to.
4014 * @param digits The minimum number of digits to pad to.
4015 */
4016 private static void toString(BigInteger u, StringBuilder sb, int radix,
4017 int digits) {
4018 // If we're smaller than a certain threshold, use the smallToString
4019 // method, padding with leading zeroes when necessary.
4020 if (u.mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) {
4021 String s = u.smallToString(radix);
4022
4023 // Pad with internal zeros if necessary.
4024 // Don't pad if we're at the beginning of the string.
4025 if ((s.length() < digits) && (sb.length() > 0)) {
4026 for (int i=s.length(); i < digits; i++) {
4027 sb.append('0');
4028 }
4029 }
4030
4031 sb.append(s);
4032 return;
4033 }
4034
4035 int b, n;
4036 b = u.bitLength();
4037
4038 // Calculate a value for n in the equation radix^(2^n) = u
4039 // and subtract 1 from that value. This is used to find the
4040 // cache index that contains the best value to divide u.
4041 n = (int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) / LOG_TWO - 1.0);
4042 BigInteger v = getRadixConversionCache(radix, n);
4043 BigInteger[] results;
4044 results = u.divideAndRemainder(v);
4045
4046 int expectedDigits = 1 << n;
4047
4048 // Now recursively build the two halves of each number.
4049 toString(results[0], sb, radix, digits-expectedDigits);
4050 toString(results[1], sb, radix, expectedDigits);
4051 }
4052
4053 /**
4054 * Returns the value radix^(2^exponent) from the cache.
4055 * If this value doesn't already exist in the cache, it is added.
4056 * <p>
4057 * This could be changed to a more complicated caching method using
4058 * {@code Future}.
4059 */
4060 private static BigInteger getRadixConversionCache(int radix, int exponent) {
4061 BigInteger[] cacheLine = powerCache[radix]; // volatile read
4062 if (exponent < cacheLine.length) {
4063 return cacheLine[exponent];
4064 }
4065
4066 int oldLength = cacheLine.length;
4067 cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
4068 for (int i = oldLength; i <= exponent; i++) {
4069 cacheLine[i] = cacheLine[i - 1].pow(2);
4070 }
4071
4072 BigInteger[][] pc = powerCache; // volatile read again
4073 if (exponent >= pc[radix].length) {
4074 pc = pc.clone();
4075 pc[radix] = cacheLine;
4076 powerCache = pc; // volatile write, publish
4077 }
4078 return cacheLine[exponent];
4079 }
4080
4081 /* zero[i] is a string of i consecutive zeros. */
4082 private static String zeros[] = new String[64];
4083 static {
4084 zeros[63] =
4085 "000000000000000000000000000000000000000000000000000000000000000";
4086 for (int i=0; i < 63; i++)
4087 zeros[i] = zeros[63].substring(0, i);
4088 }
4089
4090 /**
4091 * Returns the decimal String representation of this BigInteger.
4092 * The digit-to-character mapping provided by
4093 * {@code Character.forDigit} is used, and a minus sign is
4094 * prepended if appropriate. (This representation is compatible
4095 * with the {@link #BigInteger(String) (String)} constructor, and
4096 * allows for String concatenation with Java's + operator.)
4097 *
4098 * @return decimal String representation of this BigInteger.
4099 * @see Character#forDigit
4100 * @see #BigInteger(java.lang.String)
4101 */
4102 public String toString() {
4103 return toString(10);
4104 }
4105
4106 /**
4107 * Returns a byte array containing the two's-complement
4108 * representation of this BigInteger. The byte array will be in
|
1 /*
2 * Copyright (c) 1996, 2019, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
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);
4103 }
4104
4105 BigInteger[][] pc = powerCache; // volatile read again
4106 if (exponent >= pc[radix].length) {
4107 pc = pc.clone();
4108 pc[radix] = cacheLine;
4109 powerCache = pc; // volatile write, publish
4110 }
4111 return cacheLine[exponent];
4112 }
4113
4114 /* Size of ZEROS string. */
4115 private static int NUM_ZEROS = 63;
4116
4117 /* ZEROS is a string of NUM_ZEROS consecutive zeros. */
4118 private static final String ZEROS = "0".repeat(NUM_ZEROS);
4119
4120 /**
4121 * Returns the decimal String representation of this BigInteger.
4122 * The digit-to-character mapping provided by
4123 * {@code Character.forDigit} is used, and a minus sign is
4124 * prepended if appropriate. (This representation is compatible
4125 * with the {@link #BigInteger(String) (String)} constructor, and
4126 * allows for String concatenation with Java's + operator.)
4127 *
4128 * @return decimal String representation of this BigInteger.
4129 * @see Character#forDigit
4130 * @see #BigInteger(java.lang.String)
4131 */
4132 public String toString() {
4133 return toString(10);
4134 }
4135
4136 /**
4137 * Returns a byte array containing the two's-complement
4138 * representation of this BigInteger. The byte array will be in
|