3580 buf.append('-');
3581 }
3582 buf.append(digitGroup[numGroups-1]);
3583
3584 // Append remaining digit groups padded with leading zeros
3585 for (int i=numGroups-2; i >= 0; i--) {
3586 // Prepend (any) leading zeros for this digit group
3587 int numLeadingZeros = digitsPerLong[radix]-digitGroup[i].length();
3588 if (numLeadingZeros != 0) {
3589 buf.append(zeros[numLeadingZeros]);
3590 }
3591 buf.append(digitGroup[i]);
3592 }
3593 return buf.toString();
3594 }
3595
3596 /**
3597 * Converts the specified BigInteger to a string and appends to
3598 * {@code sb}. This implements the recursive Schoenhage algorithm
3599 * for base conversions.
3600 * <p/>
3601 * See Knuth, Donald, _The Art of Computer Programming_, Vol. 2,
3602 * Answers to Exercises (4.4) Question 14.
3603 *
3604 * @param u The number to convert to a string.
3605 * @param sb The StringBuilder that will be appended to in place.
3606 * @param radix The base to convert to.
3607 * @param digits The minimum number of digits to pad to.
3608 */
3609 private static void toString(BigInteger u, StringBuilder sb, int radix,
3610 int digits) {
3611 // If we're smaller than a certain threshold, use the smallToString
3612 // method, padding with leading zeroes when necessary.
3613 if (u.mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) {
3614 String s = u.smallToString(radix);
3615
3616 // Pad with internal zeros if necessary.
3617 // Don't pad if we're at the beginning of the string.
3618 if ((s.length() < digits) && (sb.length() > 0)) {
3619 for (int i=s.length(); i < digits; i++) {
3620 sb.append('0');
3629 b = u.bitLength();
3630
3631 // Calculate a value for n in the equation radix^(2^n) = u
3632 // and subtract 1 from that value. This is used to find the
3633 // cache index that contains the best value to divide u.
3634 n = (int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) / LOG_TWO - 1.0);
3635 BigInteger v = getRadixConversionCache(radix, n);
3636 BigInteger[] results;
3637 results = u.divideAndRemainder(v);
3638
3639 int expectedDigits = 1 << n;
3640
3641 // Now recursively build the two halves of each number.
3642 toString(results[0], sb, radix, digits-expectedDigits);
3643 toString(results[1], sb, radix, expectedDigits);
3644 }
3645
3646 /**
3647 * Returns the value radix^(2^exponent) from the cache.
3648 * If this value doesn't already exist in the cache, it is added.
3649 * <p/>
3650 * This could be changed to a more complicated caching method using
3651 * {@code Future}.
3652 */
3653 private static BigInteger getRadixConversionCache(int radix, int exponent) {
3654 BigInteger[] cacheLine = powerCache[radix]; // volatile read
3655 if (exponent < cacheLine.length) {
3656 return cacheLine[exponent];
3657 }
3658
3659 int oldLength = cacheLine.length;
3660 cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
3661 for (int i = oldLength; i <= exponent; i++) {
3662 cacheLine[i] = cacheLine[i - 1].pow(2);
3663 }
3664
3665 BigInteger[][] pc = powerCache; // volatile read again
3666 if (exponent >= pc[radix].length) {
3667 pc = pc.clone();
3668 pc[radix] = cacheLine;
3669 powerCache = pc; // volatile write, publish
|
3580 buf.append('-');
3581 }
3582 buf.append(digitGroup[numGroups-1]);
3583
3584 // Append remaining digit groups padded with leading zeros
3585 for (int i=numGroups-2; i >= 0; i--) {
3586 // Prepend (any) leading zeros for this digit group
3587 int numLeadingZeros = digitsPerLong[radix]-digitGroup[i].length();
3588 if (numLeadingZeros != 0) {
3589 buf.append(zeros[numLeadingZeros]);
3590 }
3591 buf.append(digitGroup[i]);
3592 }
3593 return buf.toString();
3594 }
3595
3596 /**
3597 * Converts the specified BigInteger to a string and appends to
3598 * {@code sb}. This implements the recursive Schoenhage algorithm
3599 * for base conversions.
3600 * <p>
3601 * See Knuth, Donald, _The Art of Computer Programming_, Vol. 2,
3602 * Answers to Exercises (4.4) Question 14.
3603 *
3604 * @param u The number to convert to a string.
3605 * @param sb The StringBuilder that will be appended to in place.
3606 * @param radix The base to convert to.
3607 * @param digits The minimum number of digits to pad to.
3608 */
3609 private static void toString(BigInteger u, StringBuilder sb, int radix,
3610 int digits) {
3611 // If we're smaller than a certain threshold, use the smallToString
3612 // method, padding with leading zeroes when necessary.
3613 if (u.mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) {
3614 String s = u.smallToString(radix);
3615
3616 // Pad with internal zeros if necessary.
3617 // Don't pad if we're at the beginning of the string.
3618 if ((s.length() < digits) && (sb.length() > 0)) {
3619 for (int i=s.length(); i < digits; i++) {
3620 sb.append('0');
3629 b = u.bitLength();
3630
3631 // Calculate a value for n in the equation radix^(2^n) = u
3632 // and subtract 1 from that value. This is used to find the
3633 // cache index that contains the best value to divide u.
3634 n = (int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) / LOG_TWO - 1.0);
3635 BigInteger v = getRadixConversionCache(radix, n);
3636 BigInteger[] results;
3637 results = u.divideAndRemainder(v);
3638
3639 int expectedDigits = 1 << n;
3640
3641 // Now recursively build the two halves of each number.
3642 toString(results[0], sb, radix, digits-expectedDigits);
3643 toString(results[1], sb, radix, expectedDigits);
3644 }
3645
3646 /**
3647 * Returns the value radix^(2^exponent) from the cache.
3648 * If this value doesn't already exist in the cache, it is added.
3649 * <p>
3650 * This could be changed to a more complicated caching method using
3651 * {@code Future}.
3652 */
3653 private static BigInteger getRadixConversionCache(int radix, int exponent) {
3654 BigInteger[] cacheLine = powerCache[radix]; // volatile read
3655 if (exponent < cacheLine.length) {
3656 return cacheLine[exponent];
3657 }
3658
3659 int oldLength = cacheLine.length;
3660 cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
3661 for (int i = oldLength; i <= exponent; i++) {
3662 cacheLine[i] = cacheLine[i - 1].pow(2);
3663 }
3664
3665 BigInteger[][] pc = powerCache; // volatile read again
3666 if (exponent >= pc[radix].length) {
3667 pc = pc.clone();
3668 pc[radix] = cacheLine;
3669 powerCache = pc; // volatile write, publish
|