< prev index next >
src/java.base/share/classes/java/math/BigInteger.java
Print this page
*** 1,7 ****
/*
! * Copyright (c) 1996, 2018, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
--- 1,7 ----
/*
! * Copyright (c) 1996, 2019, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
*** 3935,3970 ****
if (signum == 0)
return "0";
if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
radix = 10;
// If it's small enough, use smallToString.
! if (mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD)
! return smallToString(radix);
! // Otherwise use recursive toString, which requires positive arguments.
// The results will be concatenated into this StringBuilder
- StringBuilder sb = new StringBuilder();
- if (signum < 0) {
- toString(this.negate(), sb, radix, 0);
- sb.insert(0, '-');
- }
- else
toString(this, sb, radix, 0);
return sb.toString();
}
/** This method is used to perform toString when arguments are small. */
! private String smallToString(int radix) {
if (signum == 0) {
! return "0";
}
// Compute upper bound on number of digit groups and allocate space
int maxNumDigitGroups = (4*mag.length + 6)/7;
! String digitGroup[] = new String[maxNumDigitGroups];
// Translate number to string, a digit group at a time
BigInteger tmp = this.abs();
int numGroups = 0;
while (tmp.signum != 0) {
--- 3935,3975 ----
if (signum == 0)
return "0";
if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX)
radix = 10;
+ // Ensure buffer capacity sufficient to contain string representation
+ // floor(bitLength*log(2)/log(radix)) + 1
+ // plus an additional character for the sign if negative.
+ int b = this.abs().bitLength();
+ int numChars = (int)(Math.floor(b*LOG_TWO/logCache[radix]) + 1) +
+ (signum < 0 ? 1 : 0);
+ StringBuilder sb = new StringBuilder(numChars);
+
// If it's small enough, use smallToString.
! if (mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) {
! smallToString(radix, sb);
! return sb.toString();
! }
! // Otherwise use recursive toString.
// The results will be concatenated into this StringBuilder
toString(this, sb, radix, 0);
return sb.toString();
}
/** This method is used to perform toString when arguments are small. */
! private int smallToString(int radix, StringBuilder buf) {
if (signum == 0) {
! buf.append('0');
! return 1;
}
// Compute upper bound on number of digit groups and allocate space
int maxNumDigitGroups = (4*mag.length + 6)/7;
! long[] digitGroups = new long[maxNumDigitGroups];
// Translate number to string, a digit group at a time
BigInteger tmp = this.abs();
int numGroups = 0;
while (tmp.signum != 0) {
*** 3975,4005 ****
b = new MutableBigInteger(d.mag);
MutableBigInteger r = a.divide(b, q);
BigInteger q2 = q.toBigInteger(tmp.signum * d.signum);
BigInteger r2 = r.toBigInteger(tmp.signum * d.signum);
! digitGroup[numGroups++] = Long.toString(r2.longValue(), radix);
tmp = q2;
}
// Put sign (if any) and first digit group into result buffer
- StringBuilder buf = new StringBuilder(numGroups*digitsPerLong[radix]+1);
if (signum < 0) {
buf.append('-');
}
! buf.append(digitGroup[numGroups-1]);
// Append remaining digit groups padded with leading zeros
for (int i=numGroups-2; i >= 0; i--) {
// Prepend (any) leading zeros for this digit group
! int numLeadingZeros = digitsPerLong[radix]-digitGroup[i].length();
if (numLeadingZeros != 0) {
! buf.append(zeros[numLeadingZeros]);
}
! buf.append(digitGroup[i]);
}
! return buf.toString();
}
/**
* Converts the specified BigInteger to a string and appends to
* {@code sb}. This implements the recursive Schoenhage algorithm
--- 3980,4018 ----
b = new MutableBigInteger(d.mag);
MutableBigInteger r = a.divide(b, q);
BigInteger q2 = q.toBigInteger(tmp.signum * d.signum);
BigInteger r2 = r.toBigInteger(tmp.signum * d.signum);
! digitGroups[numGroups++] = r2.longValue();
tmp = q2;
}
+ int count = 0;
+
// Put sign (if any) and first digit group into result buffer
if (signum < 0) {
buf.append('-');
+ count++;
}
! String s = Long.toString(digitGroups[numGroups-1], radix);
! buf.append(s);
! count += s.length();
// Append remaining digit groups padded with leading zeros
for (int i=numGroups-2; i >= 0; i--) {
// Prepend (any) leading zeros for this digit group
! s = Long.toString(digitGroups[i], radix);
! int numLeadingZeros = digitsPerLong[radix] - s.length();
if (numLeadingZeros != 0) {
! buf.append(zeros, 0, numLeadingZeros);
! count += numLeadingZeros;
}
! buf.append(s);
! count += s.length();
}
!
! return count;
}
/**
* Converts the specified BigInteger to a string and appends to
* {@code sb}. This implements the recursive Schoenhage algorithm
*** 4011,4046 ****
* @param u The number to convert to a string.
* @param sb The StringBuilder that will be appended to in place.
* @param radix The base to convert to.
* @param digits The minimum number of digits to pad to.
*/
! private static void toString(BigInteger u, StringBuilder sb, int radix,
! int digits) {
// If we're smaller than a certain threshold, use the smallToString
// method, padding with leading zeroes when necessary.
if (u.mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) {
! String s = u.smallToString(radix);
// Pad with internal zeros if necessary.
// Don't pad if we're at the beginning of the string.
! if ((s.length() < digits) && (sb.length() > 0)) {
! for (int i=s.length(); i < digits; i++) {
! sb.append('0');
}
}
- sb.append(s);
return;
}
! int b, n;
! b = u.bitLength();
// Calculate a value for n in the equation radix^(2^n) = u
// and subtract 1 from that value. This is used to find the
// cache index that contains the best value to divide u.
! n = (int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) / LOG_TWO - 1.0);
BigInteger v = getRadixConversionCache(radix, n);
BigInteger[] results;
results = u.divideAndRemainder(v);
int expectedDigits = 1 << n;
--- 4024,4072 ----
* @param u The number to convert to a string.
* @param sb The StringBuilder that will be appended to in place.
* @param radix The base to convert to.
* @param digits The minimum number of digits to pad to.
*/
! private static void toString(BigInteger u, StringBuilder sb,
! int radix, int digits) {
! boolean atBeginning = sb.length() == 0;
! if (u.signum() < 0) {
! u = u.negate();
! sb.append('-');
! }
!
// If we're smaller than a certain threshold, use the smallToString
// method, padding with leading zeroes when necessary.
if (u.mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) {
! // Save current position.
! int pos = sb.length();
! int len = u.smallToString(radix, sb);
// Pad with internal zeros if necessary.
// Don't pad if we're at the beginning of the string.
! if (!atBeginning && len < digits) {
! int m = digits - len;
! while (m >= NUM_ZEROS) {
! sb.insert(pos, zeros, 0, NUM_ZEROS);
! pos += NUM_ZEROS;
! m -= NUM_ZEROS;
! }
! if (m > 0) {
! sb.insert(pos, zeros, 0, m);
}
}
return;
}
! int b = u.bitLength();
// Calculate a value for n in the equation radix^(2^n) = u
// and subtract 1 from that value. This is used to find the
// cache index that contains the best value to divide u.
! int n = (int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) /
! LOG_TWO - 1.0);
BigInteger v = getRadixConversionCache(radix, n);
BigInteger[] results;
results = u.divideAndRemainder(v);
int expectedDigits = 1 << n;
*** 4076,4093 ****
powerCache = pc; // volatile write, publish
}
return cacheLine[exponent];
}
! /* zero[i] is a string of i consecutive zeros. */
! private static String zeros[] = new String[64];
! static {
! zeros[63] =
! "000000000000000000000000000000000000000000000000000000000000000";
! for (int i=0; i < 63; i++)
! zeros[i] = zeros[63].substring(0, i);
! }
/**
* Returns the decimal String representation of this BigInteger.
* The digit-to-character mapping provided by
* {@code Character.forDigit} is used, and a minus sign is
--- 4102,4116 ----
powerCache = pc; // volatile write, publish
}
return cacheLine[exponent];
}
! /* Size of zeros string. */
! private static int NUM_ZEROS = 63;
!
! /* zero is a string of NUM_ZEROS consecutive zeros. */
! private static final String zeros = "0".repeat(NUM_ZEROS);
/**
* Returns the decimal String representation of this BigInteger.
* The digit-to-character mapping provided by
* {@code Character.forDigit} is used, and a minus sign is
< prev index next >