< 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,3973 **** 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) { BigInteger d = longRadix[radix]; MutableBigInteger q = new MutableBigInteger(), --- 3935,4008 ---- if (signum == 0) return "0"; if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) radix = 10; ! BigInteger abs = this.abs(); ! ! // 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 = abs.bitLength(); ! int numChars = (int)(Math.floor(b*LOG_TWO/logCache[radix]) + 1) + ! (signum < 0 ? 1 : 0); ! StringBuilder sb = new StringBuilder(numChars); ! if (signum < 0) { ! sb.append('-'); } ! ! // Use recursive toString. ! toString(abs, sb, radix, 0); return sb.toString(); } ! /** ! * If {@code numZeros > 0}, appends that many zeros to the ! * specified StringBuilder; otherwise, does nothing. ! * ! * @param sb The StringBuilder that will be appended to. ! * @param numZeros The number of zeros to append. ! */ ! private static void padWithZeros(StringBuilder buf, int numZeros) { ! while (numZeros >= NUM_ZEROS) { ! buf.append(ZEROS); ! numZeros -= NUM_ZEROS; ! } ! if (numZeros > 0) { ! buf.append(ZEROS, 0, numZeros); ! } ! } ! ! /** ! * This method is used to perform toString when arguments are small. ! * The value must be non-negative. If {@code digits <= 0} no padding ! * (pre-pending with zeros) will be effected. ! * ! * @param radix The base to convert to. ! * @param sb The StringBuilder that will be appended to in place. ! * @param digits The minimum number of digits to pad to. ! */ ! private void smallToString(int radix, StringBuilder buf, int digits) { ! assert signum >= 0; ! if (signum == 0) { ! if (digits > 0) { ! padWithZeros(buf, digits); ! } else { ! buf.append('0'); ! } ! return; } // 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; int numGroups = 0; while (tmp.signum != 0) { BigInteger d = longRadix[radix]; MutableBigInteger q = new MutableBigInteger(),
*** 3975,4054 **** 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 ! * for base conversions. * <p> * See Knuth, Donald, _The Art of Computer Programming_, Vol. 2, * Answers to Exercises (4.4) Question 14. * * @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; // Now recursively build the two halves of each number. ! toString(results[0], sb, radix, digits-expectedDigits); toString(results[1], sb, radix, expectedDigits); } /** * Returns the value radix^(2^exponent) from the cache. --- 4010,4087 ---- 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; } ! // Get string version of first digit group ! String s = Long.toString(digitGroups[numGroups-1], radix); ! ! // Pad with internal zeros if necessary. ! padWithZeros(buf, digits - (s.length() + ! (numGroups - 1)*digitsPerLong[radix])); ! ! // Put first digit group into result buffer ! buf.append(s); ! // Append remaining digit groups each 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); } ! buf.append(s); } } /** * Converts the specified BigInteger to a string and appends to * {@code sb}. This implements the recursive Schoenhage algorithm ! * for base conversions. This method can only be called for non-negative ! * numbers. * <p> * See Knuth, Donald, _The Art of Computer Programming_, Vol. 2, * Answers to Exercises (4.4) Question 14. * * @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) { ! assert u.signum() >= 0; ! // If we're smaller than a certain threshold, use the smallToString ! // method, padding with leading zeroes when necessary unless we're ! // at the beginning of the string or digits <= 0. As u.signum() >= 0, ! // smallToString() will not prepend a negative sign. if (u.mag.length <= SCHOENHAGE_BASE_CONVERSION_THRESHOLD) { ! u.smallToString(radix, sb, digits); return; } // 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 b = u.bitLength(); ! 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; // Now recursively build the two halves of each number. ! toString(results[0], sb, radix, digits - expectedDigits); toString(results[1], sb, radix, expectedDigits); } /** * Returns the value radix^(2^exponent) from the cache.
*** 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 --- 4109,4123 ---- powerCache = pc; // volatile write, publish } return cacheLine[exponent]; } ! /* Size of ZEROS string. */ ! private static int NUM_ZEROS = 63; ! ! /* ZEROS 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 >