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 // 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
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
|