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
3949 // The results will be concatenated into this StringBuilder
3950 StringBuilder sb = new StringBuilder(numChars);
3951
3952 // Put sign (if any) into result buffer
3953 if (signum < 0) {
3954 sb.append('-');
3955 }
3956
3957 // Use recursive toString.
3958 toString(abs, sb, radix, 1);
3959 return sb.toString();
3960 }
3961
3962 /**
3963 * If {@code numLeadingZeros > 0}, appends that many zeros to the
3964 * specified StringBuilder.
3965 * Otherwise, does nothing.
3966 *
3967 * @param sb The StringBuilder that will be appended to.
3968 * @param numLeadingZeros The number of zeros to append.
3969 */
3970 private static void padWithZeros(StringBuilder buf, int numLeadingZeros) {
3971 while (numLeadingZeros >= NUM_ZEROS) {
3972 buf.append(ZEROS);
3973 numLeadingZeros -= NUM_ZEROS;
3974 }
3975 if (numLeadingZeros > 0) {
3976 buf.append(ZEROS, 0, numLeadingZeros);
3977 }
3978 }
3979
3980 /**
3981 * This method is used to perform toString when arguments are small.
3982 * A negative sign will be prepended if and only if {@code this < 0}.
3983 * If {@code digits <= 0} no padding (pre-pending with zeros) will be
3984 * effected.
3985 *
3986 * This method can only be called for non-negative numbers.
3987 *
3988 * @param radix The base to convert to.
3989 * @param sb The StringBuilder that will be appended to in place.
3990 * @param digits The minimum number of digits to pad to.
3991 */
3992 private void smallToString(int radix, StringBuilder buf, int digits) {
3993 if (signum == 0) {
3994 padWithZeros(buf, digits);
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() + (numGroups - 1) * digitsPerLong[radix]);
4024
4025 // Put first digit group into result buffer
4026 buf.append(s);
4027
4028 // Append remaining digit groups each padded with leading zeros
4029 for (int i=numGroups-2; i >= 0; i--) {
4030 // Prepend (any) leading zeros for this digit group
4031 s = Long.toString(digitGroups[i], radix);
4032 int numLeadingZeros = digitsPerLong[radix] - s.length();
4033 if (numLeadingZeros != 0) {
4034 buf.append(ZEROS, 0, numLeadingZeros);
4035 }
4036 buf.append(s);
4037 }
4038 }
4039
4040 /**
4041 * Converts the specified BigInteger to a string and appends to
4042 * {@code sb}. This implements the recursive Schoenhage algorithm
4043 * for base conversions.
4044 *
4045 * This method can only be called for non-negative numbers.
4046 *
4047 * <p>
4048 * See Knuth, Donald, _The Art of Computer Programming_, Vol. 2,
4049 * Answers to Exercises (4.4) Question 14.
4050 *
4051 * @param u The number to convert to a string.
4052 * @param sb The StringBuilder that will be appended to in place.
4053 * @param radix The base to convert to.
4054 * @param digits The minimum number of digits to pad to.
4055 */
4056 private static void toString(BigInteger u, StringBuilder sb,
4057 int radix, int digits) {
4058 // If we're smaller than a certain threshold, use the smallToString
4059 // method, padding with leading zeroes when necessary unless we're
4060 // at the beginning of the string or digits <= 0. As u.signum() >= 0,
4061 // smallToString() will not prepend a negative sign.
4062 if (u.mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) {
4063 u.smallToString(radix, sb, digits);
4064 return;
4065 }
4066
4067 // Calculate a value for n in the equation radix^(2^n) = u
4068 // and subtract 1 from that value. This is used to find the
4069 // cache index that contains the best value to divide u.
4070 int b = u.bitLength();
4071 int n = (int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) /
4072 LOG_TWO - 1.0);
4073
4074 BigInteger v = getRadixConversionCache(radix, n);
4075 BigInteger[] results;
4076 results = u.divideAndRemainder(v);
4077
4078 int expectedDigits = 1 << n;
4079
4080 // Now recursively build the two halves of each number.
4081 toString(results[0], sb, radix, digits - expectedDigits);
4082 toString(results[1], sb, radix, expectedDigits);
4083 }
4084
4085 /**
4086 * Returns the value radix^(2^exponent) from the cache.
4087 * If this value doesn't already exist in the cache, it is added.
4088 * <p>
4089 * This could be changed to a more complicated caching method using
4090 * {@code Future}.
4091 */
4092 private static BigInteger getRadixConversionCache(int radix, int exponent) {
4093 BigInteger[] cacheLine = powerCache[radix]; // volatile read
4094 if (exponent < cacheLine.length) {
4095 return cacheLine[exponent];
4096 }
4097
4098 int oldLength = cacheLine.length;
4099 cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
4100 for (int i = oldLength; i <= exponent; i++) {
4101 cacheLine[i] = cacheLine[i - 1].pow(2);
4102 }
4103
4104 BigInteger[][] pc = powerCache; // volatile read again
4105 if (exponent >= pc[radix].length) {
4106 pc = pc.clone();
4107 pc[radix] = cacheLine;
4108 powerCache = pc; // volatile write, publish
4109 }
4110 return cacheLine[exponent];
4111 }
4112
4113 /* Size of ZEROS string. */
4114 private static int NUM_ZEROS = 63;
4115
4116 /* ZEROS is a string of NUM_ZEROS consecutive zeros. */
4117 private static final String ZEROS = "0".repeat(NUM_ZEROS);
4118
4119 /**
4120 * Returns the decimal String representation of this BigInteger.
4121 * The digit-to-character mapping provided by
4122 * {@code Character.forDigit} is used, and a minus sign is
4123 * prepended if appropriate. (This representation is compatible
4124 * with the {@link #BigInteger(String) (String)} constructor, and
4125 * allows for String concatenation with Java's + operator.)
4126 *
4127 * @return decimal String representation of this BigInteger.
4128 * @see Character#forDigit
4129 * @see #BigInteger(java.lang.String)
4130 */
4131 public String toString() {
4132 return toString(10);
4133 }
4134
4135 /**
4136 * Returns a byte array containing the two's-complement
4137 * representation of this BigInteger. The byte array will be in
|