612 // Create an integer with the digits between the two indexes
613 // Assumes start < end. The result may be negative, but it
614 // is to be treated as an unsigned value.
615 private int parseInt(char[] source, int start, int end) {
616 int result = Character.digit(source[start++], 10);
617 if (result == -1)
618 throw new NumberFormatException(new String(source));
619
620 for (int index = start; index < end; index++) {
621 int nextVal = Character.digit(source[index], 10);
622 if (nextVal == -1)
623 throw new NumberFormatException(new String(source));
624 result = 10*result + nextVal;
625 }
626
627 return result;
628 }
629
630 // bitsPerDigit in the given radix times 1024
631 // Rounded up to avoid underallocation.
632 private static long bitsPerDigit[] = { 0, 0,
633 1024, 1624, 2048, 2378, 2648, 2875, 3072, 3247, 3402, 3543, 3672,
634 3790, 3899, 4001, 4096, 4186, 4271, 4350, 4426, 4498, 4567, 4633,
635 4696, 4756, 4814, 4870, 4923, 4975, 5025, 5074, 5120, 5166, 5210,
636 5253, 5295};
637
638 // Multiply x array times word y in place, and add word z
639 private static void destructiveMulAdd(int[] x, int y, int z) {
640 // Perform the multiplication word by word
641 long ylong = y & LONG_MASK;
642 long zlong = z & LONG_MASK;
643 int len = x.length;
644
645 long product = 0;
646 long carry = 0;
647 for (int i = len-1; i >= 0; i--) {
648 product = ylong * (x[i] & LONG_MASK) + carry;
649 x[i] = (int)product;
650 carry = product >>> 32;
651 }
652
763 * @since 1.4
764 */
765 public static BigInteger probablePrime(int bitLength, Random rnd) {
766 if (bitLength < 2)
767 throw new ArithmeticException("bitLength < 2");
768
769 return (bitLength < SMALL_PRIME_THRESHOLD ?
770 smallPrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd) :
771 largePrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd));
772 }
773
774 /**
775 * Find a random number of the specified bitLength that is probably prime.
776 * This method is used for smaller primes, its performance degrades on
777 * larger bitlengths.
778 *
779 * This method assumes bitLength > 1.
780 */
781 private static BigInteger smallPrime(int bitLength, int certainty, Random rnd) {
782 int magLen = (bitLength + 31) >>> 5;
783 int temp[] = new int[magLen];
784 int highBit = 1 << ((bitLength+31) & 0x1f); // High bit of high int
785 int highMask = (highBit << 1) - 1; // Bits to keep in high int
786
787 while (true) {
788 // Construct a candidate
789 for (int i=0; i < magLen; i++)
790 temp[i] = rnd.nextInt();
791 temp[0] = (temp[0] & highMask) | highBit; // Ensure exact length
792 if (bitLength > 2)
793 temp[magLen-1] |= 1; // Make odd if bitlen > 2
794
795 BigInteger p = new BigInteger(temp, 1);
796
797 // Do cheap "pre-test" if applicable
798 if (bitLength > 6) {
799 long r = p.remainder(SMALL_PRIME_PRODUCT).longValue();
800 if ((r%3==0) || (r%5==0) || (r%7==0) || (r%11==0) ||
801 (r%13==0) || (r%17==0) || (r%19==0) || (r%23==0) ||
802 (r%29==0) || (r%31==0) || (r%37==0) || (r%41==0))
803 continue; // Candidate is composite; try another
1192 } else {
1193 signum = 1;
1194 }
1195
1196 int highWord = (int)(val >>> 32);
1197 if (highWord == 0) {
1198 mag = new int[1];
1199 mag[0] = (int)val;
1200 } else {
1201 mag = new int[2];
1202 mag[0] = highWord;
1203 mag[1] = (int)val;
1204 }
1205 }
1206
1207 /**
1208 * Returns a BigInteger with the given two's complement representation.
1209 * Assumes that the input array will not be modified (the returned
1210 * BigInteger will reference the input array if feasible).
1211 */
1212 private static BigInteger valueOf(int val[]) {
1213 return (val[0] > 0 ? new BigInteger(val, 1) : new BigInteger(val));
1214 }
1215
1216 // Constants
1217
1218 /**
1219 * Initialize static constant array when class is loaded.
1220 */
1221 private static final int MAX_CONSTANT = 16;
1222 private static BigInteger posConst[] = new BigInteger[MAX_CONSTANT+1];
1223 private static BigInteger negConst[] = new BigInteger[MAX_CONSTANT+1];
1224
1225 /**
1226 * The cache of powers of each radix. This allows us to not have to
1227 * recalculate powers of radix^(2^n) more than once. This speeds
1228 * Schoenhage recursive base conversion significantly.
1229 */
1230 private static volatile BigInteger[][] powerCache;
1231
1232 /** The cache of logarithms of radices for base conversion. */
1233 private static final double[] logCache;
1234
1235 /** The natural log of 2. This is used in computing cache indices. */
1236 private static final double LOG_TWO = Math.log(2.0);
1237
1238 static {
1239 for (int i = 1; i <= MAX_CONSTANT; i++) {
1240 int[] magnitude = new int[1];
1241 magnitude[0] = i;
1242 posConst[i] = new BigInteger(magnitude, 1);
1243 negConst[i] = new BigInteger(magnitude, -1);
1358 result[1] = (int)sum;
1359 result[0] = (int)(sum >>> 32);
1360 return result;
1361 } else {
1362 result = new int[xIndex];
1363 sum = (x[--xIndex] & LONG_MASK) + (val & LONG_MASK);
1364 result[xIndex] = (int)sum;
1365 sum = (x[--xIndex] & LONG_MASK) + (highWord & LONG_MASK) + (sum >>> 32);
1366 result[xIndex] = (int)sum;
1367 }
1368 }
1369 // Copy remainder of longer number while carry propagation is required
1370 boolean carry = (sum >>> 32 != 0);
1371 while (xIndex > 0 && carry)
1372 carry = ((result[--xIndex] = x[xIndex] + 1) == 0);
1373 // Copy remainder of longer number
1374 while (xIndex > 0)
1375 result[--xIndex] = x[xIndex];
1376 // Grow result if necessary
1377 if (carry) {
1378 int bigger[] = new int[result.length + 1];
1379 System.arraycopy(result, 0, bigger, 1, result.length);
1380 bigger[0] = 0x01;
1381 return bigger;
1382 }
1383 return result;
1384 }
1385
1386 /**
1387 * Adds the contents of the int arrays x and y. This method allocates
1388 * a new int array to hold the answer and returns a reference to that
1389 * array.
1390 */
1391 private static int[] add(int[] x, int[] y) {
1392 // If x is shorter, swap the two arrays
1393 if (x.length < y.length) {
1394 int[] tmp = x;
1395 x = y;
1396 y = tmp;
1397 }
1398
1399 int xIndex = x.length;
1400 int yIndex = y.length;
1401 int result[] = new int[xIndex];
1402 long sum = 0;
1403 if (yIndex == 1) {
1404 sum = (x[--xIndex] & LONG_MASK) + (y[0] & LONG_MASK) ;
1405 result[xIndex] = (int)sum;
1406 } else {
1407 // Add common parts of both numbers
1408 while (yIndex > 0) {
1409 sum = (x[--xIndex] & LONG_MASK) +
1410 (y[--yIndex] & LONG_MASK) + (sum >>> 32);
1411 result[xIndex] = (int)sum;
1412 }
1413 }
1414 // Copy remainder of longer number while carry propagation is required
1415 boolean carry = (sum >>> 32 != 0);
1416 while (xIndex > 0 && carry)
1417 carry = ((result[--xIndex] = x[xIndex] + 1) == 0);
1418
1419 // Copy remainder of longer number
1420 while (xIndex > 0)
1421 result[--xIndex] = x[xIndex];
1422
1423 // Grow result if necessary
1424 if (carry) {
1425 int bigger[] = new int[result.length + 1];
1426 System.arraycopy(result, 0, bigger, 1, result.length);
1427 bigger[0] = 0x01;
1428 return bigger;
1429 }
1430 return result;
1431 }
1432
1433 private static int[] subtract(long val, int[] little) {
1434 int highWord = (int)(val >>> 32);
1435 if (highWord == 0) {
1436 int result[] = new int[1];
1437 result[0] = (int)(val - (little[0] & LONG_MASK));
1438 return result;
1439 } else {
1440 int result[] = new int[2];
1441 if (little.length == 1) {
1442 long difference = ((int)val & LONG_MASK) - (little[0] & LONG_MASK);
1443 result[1] = (int)difference;
1444 // Subtract remainder of longer number while borrow propagates
1445 boolean borrow = (difference >> 32 != 0);
1446 if (borrow) {
1447 result[0] = highWord - 1;
1448 } else { // Copy remainder of longer number
1449 result[0] = highWord;
1450 }
1451 return result;
1452 } else { // little.length == 2
1453 long difference = ((int)val & LONG_MASK) - (little[1] & LONG_MASK);
1454 result[1] = (int)difference;
1455 difference = (highWord & LONG_MASK) - (little[0] & LONG_MASK) + (difference >> 32);
1456 result[0] = (int)difference;
1457 return result;
1458 }
1459 }
1460 }
1461
1462 /**
1463 * Subtracts the contents of the second argument (val) from the
1464 * first (big). The first int array (big) must represent a larger number
1465 * than the second. This method allocates the space necessary to hold the
1466 * answer.
1467 * assumes val >= 0
1468 */
1469 private static int[] subtract(int[] big, long val) {
1470 int highWord = (int)(val >>> 32);
1471 int bigIndex = big.length;
1472 int result[] = new int[bigIndex];
1473 long difference = 0;
1474
1475 if (highWord == 0) {
1476 difference = (big[--bigIndex] & LONG_MASK) - val;
1477 result[bigIndex] = (int)difference;
1478 } else {
1479 difference = (big[--bigIndex] & LONG_MASK) - (val & LONG_MASK);
1480 result[bigIndex] = (int)difference;
1481 difference = (big[--bigIndex] & LONG_MASK) - (highWord & LONG_MASK) + (difference >> 32);
1482 result[bigIndex] = (int)difference;
1483 }
1484
1485 // Subtract remainder of longer number while borrow propagates
1486 boolean borrow = (difference >> 32 != 0);
1487 while (bigIndex > 0 && borrow)
1488 borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);
1489
1490 // Copy remainder of longer number
1491 while (bigIndex > 0)
1492 result[--bigIndex] = big[bigIndex];
1508 if (val.signum != signum)
1509 return new BigInteger(add(mag, val.mag), signum);
1510
1511 int cmp = compareMagnitude(val);
1512 if (cmp == 0)
1513 return ZERO;
1514 int[] resultMag = (cmp > 0 ? subtract(mag, val.mag)
1515 : subtract(val.mag, mag));
1516 resultMag = trustedStripLeadingZeroInts(resultMag);
1517 return new BigInteger(resultMag, cmp == signum ? 1 : -1);
1518 }
1519
1520 /**
1521 * Subtracts the contents of the second int arrays (little) from the
1522 * first (big). The first int array (big) must represent a larger number
1523 * than the second. This method allocates the space necessary to hold the
1524 * answer.
1525 */
1526 private static int[] subtract(int[] big, int[] little) {
1527 int bigIndex = big.length;
1528 int result[] = new int[bigIndex];
1529 int littleIndex = little.length;
1530 long difference = 0;
1531
1532 // Subtract common parts of both numbers
1533 while (littleIndex > 0) {
1534 difference = (big[--bigIndex] & LONG_MASK) -
1535 (little[--littleIndex] & LONG_MASK) +
1536 (difference >> 32);
1537 result[bigIndex] = (int)difference;
1538 }
1539
1540 // Subtract remainder of longer number while borrow propagates
1541 boolean borrow = (difference >> 32 != 0);
1542 while (bigIndex > 0 && borrow)
1543 borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);
1544
1545 // Copy remainder of longer number
1546 while (bigIndex > 0)
1547 result[--bigIndex] = big[bigIndex];
1548
1873
1874 if (start < 0) {
1875 start = 0;
1876 }
1877 if (end < 0) {
1878 return ZERO;
1879 }
1880
1881 sliceSize = (end-start) + 1;
1882
1883 if (sliceSize <= 0) {
1884 return ZERO;
1885 }
1886
1887 // While performing Toom-Cook, all slices are positive and
1888 // the sign is adjusted when the final number is composed.
1889 if (start == 0 && sliceSize >= len) {
1890 return this.abs();
1891 }
1892
1893 int intSlice[] = new int[sliceSize];
1894 System.arraycopy(mag, start, intSlice, 0, sliceSize);
1895
1896 return new BigInteger(trustedStripLeadingZeroInts(intSlice), 1);
1897 }
1898
1899 /**
1900 * Does an exact division (that is, the remainder is known to be zero)
1901 * of the specified number by 3. This is used in Toom-Cook
1902 * multiplication. This is an efficient algorithm that runs in linear
1903 * time. If the argument is not exactly divisible by 3, results are
1904 * undefined. Note that this is expected to be called with positive
1905 * arguments only.
1906 */
1907 private BigInteger exactDivideBy3() {
1908 int len = mag.length;
1909 int[] result = new int[len];
1910 long x, w, q, borrow;
1911 borrow = 0L;
1912 for (int i=len-1; i >= 0; i--) {
1913 x = (mag[i] & LONG_MASK);
1930 borrow++;
1931 if (q >= 0xAAAAAAABL)
1932 borrow++;
1933 }
1934 }
1935 result = trustedStripLeadingZeroInts(result);
1936 return new BigInteger(result, signum);
1937 }
1938
1939 /**
1940 * Returns a new BigInteger representing n lower ints of the number.
1941 * This is used by Karatsuba multiplication and Karatsuba squaring.
1942 */
1943 private BigInteger getLower(int n) {
1944 int len = mag.length;
1945
1946 if (len <= n) {
1947 return abs();
1948 }
1949
1950 int lowerInts[] = new int[n];
1951 System.arraycopy(mag, len-n, lowerInts, 0, n);
1952
1953 return new BigInteger(trustedStripLeadingZeroInts(lowerInts), 1);
1954 }
1955
1956 /**
1957 * Returns a new BigInteger representing mag.length-n upper
1958 * ints of the number. This is used by Karatsuba multiplication and
1959 * Karatsuba squaring.
1960 */
1961 private BigInteger getUpper(int n) {
1962 int len = mag.length;
1963
1964 if (len <= n) {
1965 return ZERO;
1966 }
1967
1968 int upperLen = len - n;
1969 int upperInts[] = new int[upperLen];
1970 System.arraycopy(mag, 0, upperInts, 0, upperLen);
1971
1972 return new BigInteger(trustedStripLeadingZeroInts(upperInts), 1);
1973 }
1974
1975 // Squaring
1976
1977 /**
1978 * Returns a BigInteger whose value is {@code (this<sup>2</sup>)}.
1979 *
1980 * @return {@code this<sup>2</sup>}
1981 */
1982 private BigInteger square() {
1983 if (signum == 0) {
1984 return ZERO;
1985 }
1986 int len = mag.length;
1987
1988 if (len < KARATSUBA_SQUARE_THRESHOLD) {
1989 int[] z = squareToLen(mag, len, null);
2491 */
2492 static int bitLengthForInt(int n) {
2493 return 32 - Integer.numberOfLeadingZeros(n);
2494 }
2495
2496 /**
2497 * Left shift int array a up to len by n bits. Returns the array that
2498 * results from the shift since space may have to be reallocated.
2499 */
2500 private static int[] leftShift(int[] a, int len, int n) {
2501 int nInts = n >>> 5;
2502 int nBits = n&0x1F;
2503 int bitsInHighWord = bitLengthForInt(a[0]);
2504
2505 // If shift can be done without recopy, do so
2506 if (n <= (32-bitsInHighWord)) {
2507 primitiveLeftShift(a, len, nBits);
2508 return a;
2509 } else { // Array must be resized
2510 if (nBits <= (32-bitsInHighWord)) {
2511 int result[] = new int[nInts+len];
2512 System.arraycopy(a, 0, result, 0, len);
2513 primitiveLeftShift(result, result.length, nBits);
2514 return result;
2515 } else {
2516 int result[] = new int[nInts+len+1];
2517 System.arraycopy(a, 0, result, 0, len);
2518 primitiveRightShift(result, result.length, 32 - nBits);
2519 return result;
2520 }
2521 }
2522 }
2523
2524 // shifts a up to len right n bits assumes no leading zeros, 0<n<32
2525 static void primitiveRightShift(int[] a, int len, int n) {
2526 int n2 = 32 - n;
2527 for (int i=len-1, c=a[i]; i > 0; i--) {
2528 int b = c;
2529 c = a[i-1];
2530 a[i] = (c << n2) | (b >>> n);
2531 }
2532 a[0] >>>= n;
2533 }
2534
2535 // shifts a up to len left n bits assumes no leading zeros, 0<=n<32
2536 static void primitiveLeftShift(int[] a, int len, int n) {
3223 } else {
3224 // Possible int overflow in (-n) is not a trouble,
3225 // because shiftRightImpl considers its argument unsigned
3226 return shiftRightImpl(-n);
3227 }
3228 }
3229
3230 /**
3231 * Returns a magnitude array whose value is {@code (mag << n)}.
3232 * The shift distance, {@code n}, is considered unnsigned.
3233 * (Computes <code>this * 2<sup>n</sup></code>.)
3234 *
3235 * @param mag magnitude, the most-significant int ({@code mag[0]}) must be non-zero.
3236 * @param n unsigned shift distance, in bits.
3237 * @return {@code mag << n}
3238 */
3239 private static int[] shiftLeft(int[] mag, int n) {
3240 int nInts = n >>> 5;
3241 int nBits = n & 0x1f;
3242 int magLen = mag.length;
3243 int newMag[] = null;
3244
3245 if (nBits == 0) {
3246 newMag = new int[magLen + nInts];
3247 System.arraycopy(mag, 0, newMag, 0, magLen);
3248 } else {
3249 int i = 0;
3250 int nBits2 = 32 - nBits;
3251 int highBits = mag[0] >>> nBits2;
3252 if (highBits != 0) {
3253 newMag = new int[magLen + nInts + 1];
3254 newMag[i++] = highBits;
3255 } else {
3256 newMag = new int[magLen + nInts];
3257 }
3258 int j=0;
3259 while (j < magLen-1)
3260 newMag[i++] = mag[j++] << nBits | mag[j] >>> nBits2;
3261 newMag[i] = mag[j] << nBits;
3262 }
3263 return newMag;
3282 return this;
3283 } else {
3284 // Possible int overflow in {@code -n} is not a trouble,
3285 // because shiftLeft considers its argument unsigned
3286 return new BigInteger(shiftLeft(mag, -n), signum);
3287 }
3288 }
3289
3290 /**
3291 * Returns a BigInteger whose value is {@code (this >> n)}. The shift
3292 * distance, {@code n}, is considered unsigned.
3293 * (Computes <code>floor(this * 2<sup>-n</sup>)</code>.)
3294 *
3295 * @param n unsigned shift distance, in bits.
3296 * @return {@code this >> n}
3297 */
3298 private BigInteger shiftRightImpl(int n) {
3299 int nInts = n >>> 5;
3300 int nBits = n & 0x1f;
3301 int magLen = mag.length;
3302 int newMag[] = null;
3303
3304 // Special case: entire contents shifted off the end
3305 if (nInts >= magLen)
3306 return (signum >= 0 ? ZERO : negConst[1]);
3307
3308 if (nBits == 0) {
3309 int newMagLen = magLen - nInts;
3310 newMag = Arrays.copyOf(mag, newMagLen);
3311 } else {
3312 int i = 0;
3313 int highBits = mag[0] >>> nBits;
3314 if (highBits != 0) {
3315 newMag = new int[magLen - nInts];
3316 newMag[i++] = highBits;
3317 } else {
3318 newMag = new int[magLen - nInts -1];
3319 }
3320
3321 int nBits2 = 32 - nBits;
3322 int j=0;
3847 // The results will be concatenated into this StringBuilder
3848 StringBuilder sb = new StringBuilder();
3849 if (signum < 0) {
3850 toString(this.negate(), sb, radix, 0);
3851 sb.insert(0, '-');
3852 }
3853 else
3854 toString(this, sb, radix, 0);
3855
3856 return sb.toString();
3857 }
3858
3859 /** This method is used to perform toString when arguments are small. */
3860 private String smallToString(int radix) {
3861 if (signum == 0) {
3862 return "0";
3863 }
3864
3865 // Compute upper bound on number of digit groups and allocate space
3866 int maxNumDigitGroups = (4*mag.length + 6)/7;
3867 String digitGroup[] = new String[maxNumDigitGroups];
3868
3869 // Translate number to string, a digit group at a time
3870 BigInteger tmp = this.abs();
3871 int numGroups = 0;
3872 while (tmp.signum != 0) {
3873 BigInteger d = longRadix[radix];
3874
3875 MutableBigInteger q = new MutableBigInteger(),
3876 a = new MutableBigInteger(tmp.mag),
3877 b = new MutableBigInteger(d.mag);
3878 MutableBigInteger r = a.divide(b, q);
3879 BigInteger q2 = q.toBigInteger(tmp.signum * d.signum);
3880 BigInteger r2 = r.toBigInteger(tmp.signum * d.signum);
3881
3882 digitGroup[numGroups++] = Long.toString(r2.longValue(), radix);
3883 tmp = q2;
3884 }
3885
3886 // Put sign (if any) and first digit group into result buffer
3887 StringBuilder buf = new StringBuilder(numGroups*digitsPerLong[radix]+1);
3964 if (exponent < cacheLine.length) {
3965 return cacheLine[exponent];
3966 }
3967
3968 int oldLength = cacheLine.length;
3969 cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
3970 for (int i = oldLength; i <= exponent; i++) {
3971 cacheLine[i] = cacheLine[i - 1].pow(2);
3972 }
3973
3974 BigInteger[][] pc = powerCache; // volatile read again
3975 if (exponent >= pc[radix].length) {
3976 pc = pc.clone();
3977 pc[radix] = cacheLine;
3978 powerCache = pc; // volatile write, publish
3979 }
3980 return cacheLine[exponent];
3981 }
3982
3983 /* zero[i] is a string of i consecutive zeros. */
3984 private static String zeros[] = new String[64];
3985 static {
3986 zeros[63] =
3987 "000000000000000000000000000000000000000000000000000000000000000";
3988 for (int i=0; i < 63; i++)
3989 zeros[i] = zeros[63].substring(0, i);
3990 }
3991
3992 /**
3993 * Returns the decimal String representation of this BigInteger.
3994 * The digit-to-character mapping provided by
3995 * {@code Character.forDigit} is used, and a minus sign is
3996 * prepended if appropriate. (This representation is compatible
3997 * with the {@link #BigInteger(String) (String)} constructor, and
3998 * allows for String concatenation with Java's + operator.)
3999 *
4000 * @return decimal String representation of this BigInteger.
4001 * @see Character#forDigit
4002 * @see #BigInteger(java.lang.String)
4003 */
4004 public String toString() {
4246 boolean increment = (twiceSignifFloor & 1) != 0
4247 && ((signifFloor & 1) != 0 || abs().getLowestSetBit() < shift);
4248 long signifRounded = increment ? signifFloor + 1 : signifFloor;
4249 long bits = (long) ((exponent + DoubleConsts.EXP_BIAS))
4250 << (DoubleConsts.SIGNIFICAND_WIDTH - 1);
4251 bits += signifRounded;
4252 /*
4253 * If signifRounded == 2^53, we'd need to set all of the significand
4254 * bits to zero and add 1 to the exponent. This is exactly the behavior
4255 * we get from just adding signifRounded to bits directly. If the
4256 * exponent is Double.MAX_EXPONENT, we round up (correctly) to
4257 * Double.POSITIVE_INFINITY.
4258 */
4259 bits |= signum & DoubleConsts.SIGN_BIT_MASK;
4260 return Double.longBitsToDouble(bits);
4261 }
4262
4263 /**
4264 * Returns a copy of the input array stripped of any leading zero bytes.
4265 */
4266 private static int[] stripLeadingZeroInts(int val[]) {
4267 int vlen = val.length;
4268 int keep;
4269
4270 // Find first nonzero byte
4271 for (keep = 0; keep < vlen && val[keep] == 0; keep++)
4272 ;
4273 return java.util.Arrays.copyOfRange(val, keep, vlen);
4274 }
4275
4276 /**
4277 * Returns the input array stripped of any leading zero bytes.
4278 * Since the source is trusted the copying may be skipped.
4279 */
4280 private static int[] trustedStripLeadingZeroInts(int val[]) {
4281 int vlen = val.length;
4282 int keep;
4283
4284 // Find first nonzero byte
4285 for (keep = 0; keep < vlen && val[keep] == 0; keep++)
4286 ;
4287 return keep == 0 ? val : java.util.Arrays.copyOfRange(val, keep, vlen);
4288 }
4289
4290 /**
4291 * Returns a copy of the input array stripped of any leading zero bytes.
4292 */
4293 private static int[] stripLeadingZeroBytes(byte a[], int off, int len) {
4294 int indexBound = off + len;
4295 int keep;
4296
4297 // Find first nonzero byte
4298 for (keep = off; keep < indexBound && a[keep] == 0; keep++)
4299 ;
4300
4301 // Allocate new array and copy relevant part of input array
4302 int intLength = ((indexBound - keep) + 3) >>> 2;
4303 int[] result = new int[intLength];
4304 int b = indexBound - 1;
4305 for (int i = intLength-1; i >= 0; i--) {
4306 result[i] = a[b--] & 0xff;
4307 int bytesRemaining = b - keep + 1;
4308 int bytesToTransfer = Math.min(3, bytesRemaining);
4309 for (int j=8; j <= (bytesToTransfer << 3); j += 8)
4310 result[i] |= ((a[b--] & 0xff) << j);
4311 }
4312 return result;
4313 }
4314
4315 /**
4316 * Takes an array a representing a negative 2's-complement number and
4317 * returns the minimal (no leading zero bytes) unsigned whose value is -a.
4318 */
4319 private static int[] makePositive(byte a[], int off, int len) {
4320 int keep, k;
4321 int indexBound = off + len;
4322
4323 // Find first non-sign (0xff) byte of input
4324 for (keep=off; keep < indexBound && a[keep] == -1; keep++)
4325 ;
4326
4327
4328 /* Allocate output array. If all non-sign bytes are 0x00, we must
4329 * allocate space for one extra output byte. */
4330 for (k=keep; k < indexBound && a[k] == 0; k++)
4331 ;
4332
4333 int extraByte = (k == indexBound) ? 1 : 0;
4334 int intLength = ((indexBound - keep + extraByte) + 3) >>> 2;
4335 int result[] = new int[intLength];
4336
4337 /* Copy one's complement of input into output, leaving extra
4338 * byte (if it exists) == 0x00 */
4339 int b = indexBound - 1;
4340 for (int i = intLength-1; i >= 0; i--) {
4341 result[i] = a[b--] & 0xff;
4342 int numBytesToTransfer = Math.min(3, b-keep+1);
4343 if (numBytesToTransfer < 0)
4344 numBytesToTransfer = 0;
4345 for (int j=8; j <= 8*numBytesToTransfer; j += 8)
4346 result[i] |= ((a[b--] & 0xff) << j);
4347
4348 // Mask indicates which bits must be complemented
4349 int mask = -1 >>> (8*(3-numBytesToTransfer));
4350 result[i] = ~result[i] & mask;
4351 }
4352
4353 // Add one to one's complement to generate two's complement
4354 for (int i=result.length-1; i >= 0; i--) {
4355 result[i] = (int)((result[i] & LONG_MASK) + 1);
4356 if (result[i] != 0)
4357 break;
4358 }
4359
4360 return result;
4361 }
4362
4363 /**
4364 * Takes an array a representing a negative 2's-complement number and
4365 * returns the minimal (no leading zero ints) unsigned whose value is -a.
4366 */
4367 private static int[] makePositive(int a[]) {
4368 int keep, j;
4369
4370 // Find first non-sign (0xffffffff) int of input
4371 for (keep=0; keep < a.length && a[keep] == -1; keep++)
4372 ;
4373
4374 /* Allocate output array. If all non-sign ints are 0x00, we must
4375 * allocate space for one extra output int. */
4376 for (j=keep; j < a.length && a[j] == 0; j++)
4377 ;
4378 int extraInt = (j == a.length ? 1 : 0);
4379 int result[] = new int[a.length - keep + extraInt];
4380
4381 /* Copy one's complement of input into output, leaving extra
4382 * int (if it exists) == 0x00 */
4383 for (int i = keep; i < a.length; i++)
4384 result[i - keep + extraInt] = ~a[i];
4385
4386 // Add one to one's complement to generate two's complement
4387 for (int i=result.length-1; ++result[i] == 0; i--)
4388 ;
4389
4390 return result;
4391 }
4392
4393 /*
4394 * The following two arrays are used for fast String conversions. Both
4395 * are indexed by radix. The first is the number of digits of the given
4396 * radix that can fit in a Java long without "going negative", i.e., the
4397 * highest integer n such that radix**n < 2**63. The second is the
4398 * "long radix" that tears each number into "long digits", each of which
4399 * consists of the number of digits in the corresponding element in
4400 * digitsPerLong (longRadix[i] = i**digitPerLong[i]). Both arrays have
4401 * nonsense values in their 0 and 1 elements, as radixes 0 and 1 are not
4402 * used.
4403 */
4404 private static int digitsPerLong[] = {0, 0,
4405 62, 39, 31, 27, 24, 22, 20, 19, 18, 18, 17, 17, 16, 16, 15, 15, 15, 14,
4406 14, 14, 14, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12};
4407
4408 private static BigInteger longRadix[] = {null, null,
4409 valueOf(0x4000000000000000L), valueOf(0x383d9170b85ff80bL),
4410 valueOf(0x4000000000000000L), valueOf(0x6765c793fa10079dL),
4411 valueOf(0x41c21cb8e1000000L), valueOf(0x3642798750226111L),
4412 valueOf(0x1000000000000000L), valueOf(0x12bf307ae81ffd59L),
4413 valueOf( 0xde0b6b3a7640000L), valueOf(0x4d28cb56c33fa539L),
4414 valueOf(0x1eca170c00000000L), valueOf(0x780c7372621bd74dL),
4415 valueOf(0x1e39a5057d810000L), valueOf(0x5b27ac993df97701L),
4416 valueOf(0x1000000000000000L), valueOf(0x27b95e997e21d9f1L),
4417 valueOf(0x5da0e1e53c5c8000L), valueOf( 0xb16a458ef403f19L),
4418 valueOf(0x16bcc41e90000000L), valueOf(0x2d04b7fdd9c0ef49L),
4419 valueOf(0x5658597bcaa24000L), valueOf( 0x6feb266931a75b7L),
4420 valueOf( 0xc29e98000000000L), valueOf(0x14adf4b7320334b9L),
4421 valueOf(0x226ed36478bfa000L), valueOf(0x383d9170b85ff80bL),
4422 valueOf(0x5a3c23e39c000000L), valueOf( 0x4e900abb53e6b71L),
4423 valueOf( 0x7600ec618141000L), valueOf( 0xaee5720ee830681L),
4424 valueOf(0x1000000000000000L), valueOf(0x172588ad4f5f0981L),
4425 valueOf(0x211e44f7d02c1000L), valueOf(0x2ee56725f06e5c71L),
4426 valueOf(0x41c21cb8e1000000L)};
4427
4428 /*
4429 * These two arrays are the integer analogue of above.
4430 */
4431 private static int digitsPerInt[] = {0, 0, 30, 19, 15, 13, 11,
4432 11, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6,
4433 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5};
4434
4435 private static int intRadix[] = {0, 0,
4436 0x40000000, 0x4546b3db, 0x40000000, 0x48c27395, 0x159fd800,
4437 0x75db9c97, 0x40000000, 0x17179149, 0x3b9aca00, 0xcc6db61,
4438 0x19a10000, 0x309f1021, 0x57f6c100, 0xa2f1b6f, 0x10000000,
4439 0x18754571, 0x247dbc80, 0x3547667b, 0x4c4b4000, 0x6b5a6e1d,
4440 0x6c20a40, 0x8d2d931, 0xb640000, 0xe8d4a51, 0x1269ae40,
4441 0x17179149, 0x1cb91000, 0x23744899, 0x2b73a840, 0x34e63b41,
4442 0x40000000, 0x4cfa3cc1, 0x5c13d840, 0x6d91b519, 0x39aa400
4443 };
4444
4445 /**
4446 * These routines provide access to the two's complement representation
4447 * of BigIntegers.
4448 */
4449
4450 /**
4451 * Returns the length of the two's complement representation in ints,
4452 * including space for at least one sign bit.
4453 */
4454 private int intLength() {
4455 return (bitLength() >>> 5) + 1;
|
612 // Create an integer with the digits between the two indexes
613 // Assumes start < end. The result may be negative, but it
614 // is to be treated as an unsigned value.
615 private int parseInt(char[] source, int start, int end) {
616 int result = Character.digit(source[start++], 10);
617 if (result == -1)
618 throw new NumberFormatException(new String(source));
619
620 for (int index = start; index < end; index++) {
621 int nextVal = Character.digit(source[index], 10);
622 if (nextVal == -1)
623 throw new NumberFormatException(new String(source));
624 result = 10*result + nextVal;
625 }
626
627 return result;
628 }
629
630 // bitsPerDigit in the given radix times 1024
631 // Rounded up to avoid underallocation.
632 private static long[] bitsPerDigit = { 0, 0,
633 1024, 1624, 2048, 2378, 2648, 2875, 3072, 3247, 3402, 3543, 3672,
634 3790, 3899, 4001, 4096, 4186, 4271, 4350, 4426, 4498, 4567, 4633,
635 4696, 4756, 4814, 4870, 4923, 4975, 5025, 5074, 5120, 5166, 5210,
636 5253, 5295};
637
638 // Multiply x array times word y in place, and add word z
639 private static void destructiveMulAdd(int[] x, int y, int z) {
640 // Perform the multiplication word by word
641 long ylong = y & LONG_MASK;
642 long zlong = z & LONG_MASK;
643 int len = x.length;
644
645 long product = 0;
646 long carry = 0;
647 for (int i = len-1; i >= 0; i--) {
648 product = ylong * (x[i] & LONG_MASK) + carry;
649 x[i] = (int)product;
650 carry = product >>> 32;
651 }
652
763 * @since 1.4
764 */
765 public static BigInteger probablePrime(int bitLength, Random rnd) {
766 if (bitLength < 2)
767 throw new ArithmeticException("bitLength < 2");
768
769 return (bitLength < SMALL_PRIME_THRESHOLD ?
770 smallPrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd) :
771 largePrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd));
772 }
773
774 /**
775 * Find a random number of the specified bitLength that is probably prime.
776 * This method is used for smaller primes, its performance degrades on
777 * larger bitlengths.
778 *
779 * This method assumes bitLength > 1.
780 */
781 private static BigInteger smallPrime(int bitLength, int certainty, Random rnd) {
782 int magLen = (bitLength + 31) >>> 5;
783 int[] temp = new int[magLen];
784 int highBit = 1 << ((bitLength+31) & 0x1f); // High bit of high int
785 int highMask = (highBit << 1) - 1; // Bits to keep in high int
786
787 while (true) {
788 // Construct a candidate
789 for (int i=0; i < magLen; i++)
790 temp[i] = rnd.nextInt();
791 temp[0] = (temp[0] & highMask) | highBit; // Ensure exact length
792 if (bitLength > 2)
793 temp[magLen-1] |= 1; // Make odd if bitlen > 2
794
795 BigInteger p = new BigInteger(temp, 1);
796
797 // Do cheap "pre-test" if applicable
798 if (bitLength > 6) {
799 long r = p.remainder(SMALL_PRIME_PRODUCT).longValue();
800 if ((r%3==0) || (r%5==0) || (r%7==0) || (r%11==0) ||
801 (r%13==0) || (r%17==0) || (r%19==0) || (r%23==0) ||
802 (r%29==0) || (r%31==0) || (r%37==0) || (r%41==0))
803 continue; // Candidate is composite; try another
1192 } else {
1193 signum = 1;
1194 }
1195
1196 int highWord = (int)(val >>> 32);
1197 if (highWord == 0) {
1198 mag = new int[1];
1199 mag[0] = (int)val;
1200 } else {
1201 mag = new int[2];
1202 mag[0] = highWord;
1203 mag[1] = (int)val;
1204 }
1205 }
1206
1207 /**
1208 * Returns a BigInteger with the given two's complement representation.
1209 * Assumes that the input array will not be modified (the returned
1210 * BigInteger will reference the input array if feasible).
1211 */
1212 private static BigInteger valueOf(int[] val) {
1213 return (val[0] > 0 ? new BigInteger(val, 1) : new BigInteger(val));
1214 }
1215
1216 // Constants
1217
1218 /**
1219 * Initialize static constant array when class is loaded.
1220 */
1221 private static final int MAX_CONSTANT = 16;
1222 private static BigInteger[] posConst = new BigInteger[MAX_CONSTANT+1];
1223 private static BigInteger[] negConst = new BigInteger[MAX_CONSTANT+1];
1224
1225 /**
1226 * The cache of powers of each radix. This allows us to not have to
1227 * recalculate powers of radix^(2^n) more than once. This speeds
1228 * Schoenhage recursive base conversion significantly.
1229 */
1230 private static volatile BigInteger[][] powerCache;
1231
1232 /** The cache of logarithms of radices for base conversion. */
1233 private static final double[] logCache;
1234
1235 /** The natural log of 2. This is used in computing cache indices. */
1236 private static final double LOG_TWO = Math.log(2.0);
1237
1238 static {
1239 for (int i = 1; i <= MAX_CONSTANT; i++) {
1240 int[] magnitude = new int[1];
1241 magnitude[0] = i;
1242 posConst[i] = new BigInteger(magnitude, 1);
1243 negConst[i] = new BigInteger(magnitude, -1);
1358 result[1] = (int)sum;
1359 result[0] = (int)(sum >>> 32);
1360 return result;
1361 } else {
1362 result = new int[xIndex];
1363 sum = (x[--xIndex] & LONG_MASK) + (val & LONG_MASK);
1364 result[xIndex] = (int)sum;
1365 sum = (x[--xIndex] & LONG_MASK) + (highWord & LONG_MASK) + (sum >>> 32);
1366 result[xIndex] = (int)sum;
1367 }
1368 }
1369 // Copy remainder of longer number while carry propagation is required
1370 boolean carry = (sum >>> 32 != 0);
1371 while (xIndex > 0 && carry)
1372 carry = ((result[--xIndex] = x[xIndex] + 1) == 0);
1373 // Copy remainder of longer number
1374 while (xIndex > 0)
1375 result[--xIndex] = x[xIndex];
1376 // Grow result if necessary
1377 if (carry) {
1378 int[] bigger = new int[result.length + 1];
1379 System.arraycopy(result, 0, bigger, 1, result.length);
1380 bigger[0] = 0x01;
1381 return bigger;
1382 }
1383 return result;
1384 }
1385
1386 /**
1387 * Adds the contents of the int arrays x and y. This method allocates
1388 * a new int array to hold the answer and returns a reference to that
1389 * array.
1390 */
1391 private static int[] add(int[] x, int[] y) {
1392 // If x is shorter, swap the two arrays
1393 if (x.length < y.length) {
1394 int[] tmp = x;
1395 x = y;
1396 y = tmp;
1397 }
1398
1399 int xIndex = x.length;
1400 int yIndex = y.length;
1401 int[] result = new int[xIndex];
1402 long sum = 0;
1403 if (yIndex == 1) {
1404 sum = (x[--xIndex] & LONG_MASK) + (y[0] & LONG_MASK) ;
1405 result[xIndex] = (int)sum;
1406 } else {
1407 // Add common parts of both numbers
1408 while (yIndex > 0) {
1409 sum = (x[--xIndex] & LONG_MASK) +
1410 (y[--yIndex] & LONG_MASK) + (sum >>> 32);
1411 result[xIndex] = (int)sum;
1412 }
1413 }
1414 // Copy remainder of longer number while carry propagation is required
1415 boolean carry = (sum >>> 32 != 0);
1416 while (xIndex > 0 && carry)
1417 carry = ((result[--xIndex] = x[xIndex] + 1) == 0);
1418
1419 // Copy remainder of longer number
1420 while (xIndex > 0)
1421 result[--xIndex] = x[xIndex];
1422
1423 // Grow result if necessary
1424 if (carry) {
1425 int[] bigger = new int[result.length + 1];
1426 System.arraycopy(result, 0, bigger, 1, result.length);
1427 bigger[0] = 0x01;
1428 return bigger;
1429 }
1430 return result;
1431 }
1432
1433 private static int[] subtract(long val, int[] little) {
1434 int highWord = (int)(val >>> 32);
1435 if (highWord == 0) {
1436 int[] result = new int[1];
1437 result[0] = (int)(val - (little[0] & LONG_MASK));
1438 return result;
1439 } else {
1440 int[] result = new int[2];
1441 if (little.length == 1) {
1442 long difference = ((int)val & LONG_MASK) - (little[0] & LONG_MASK);
1443 result[1] = (int)difference;
1444 // Subtract remainder of longer number while borrow propagates
1445 boolean borrow = (difference >> 32 != 0);
1446 if (borrow) {
1447 result[0] = highWord - 1;
1448 } else { // Copy remainder of longer number
1449 result[0] = highWord;
1450 }
1451 return result;
1452 } else { // little.length == 2
1453 long difference = ((int)val & LONG_MASK) - (little[1] & LONG_MASK);
1454 result[1] = (int)difference;
1455 difference = (highWord & LONG_MASK) - (little[0] & LONG_MASK) + (difference >> 32);
1456 result[0] = (int)difference;
1457 return result;
1458 }
1459 }
1460 }
1461
1462 /**
1463 * Subtracts the contents of the second argument (val) from the
1464 * first (big). The first int array (big) must represent a larger number
1465 * than the second. This method allocates the space necessary to hold the
1466 * answer.
1467 * assumes val >= 0
1468 */
1469 private static int[] subtract(int[] big, long val) {
1470 int highWord = (int)(val >>> 32);
1471 int bigIndex = big.length;
1472 int[] result = new int[bigIndex];
1473 long difference = 0;
1474
1475 if (highWord == 0) {
1476 difference = (big[--bigIndex] & LONG_MASK) - val;
1477 result[bigIndex] = (int)difference;
1478 } else {
1479 difference = (big[--bigIndex] & LONG_MASK) - (val & LONG_MASK);
1480 result[bigIndex] = (int)difference;
1481 difference = (big[--bigIndex] & LONG_MASK) - (highWord & LONG_MASK) + (difference >> 32);
1482 result[bigIndex] = (int)difference;
1483 }
1484
1485 // Subtract remainder of longer number while borrow propagates
1486 boolean borrow = (difference >> 32 != 0);
1487 while (bigIndex > 0 && borrow)
1488 borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);
1489
1490 // Copy remainder of longer number
1491 while (bigIndex > 0)
1492 result[--bigIndex] = big[bigIndex];
1508 if (val.signum != signum)
1509 return new BigInteger(add(mag, val.mag), signum);
1510
1511 int cmp = compareMagnitude(val);
1512 if (cmp == 0)
1513 return ZERO;
1514 int[] resultMag = (cmp > 0 ? subtract(mag, val.mag)
1515 : subtract(val.mag, mag));
1516 resultMag = trustedStripLeadingZeroInts(resultMag);
1517 return new BigInteger(resultMag, cmp == signum ? 1 : -1);
1518 }
1519
1520 /**
1521 * Subtracts the contents of the second int arrays (little) from the
1522 * first (big). The first int array (big) must represent a larger number
1523 * than the second. This method allocates the space necessary to hold the
1524 * answer.
1525 */
1526 private static int[] subtract(int[] big, int[] little) {
1527 int bigIndex = big.length;
1528 int[] result = new int[bigIndex];
1529 int littleIndex = little.length;
1530 long difference = 0;
1531
1532 // Subtract common parts of both numbers
1533 while (littleIndex > 0) {
1534 difference = (big[--bigIndex] & LONG_MASK) -
1535 (little[--littleIndex] & LONG_MASK) +
1536 (difference >> 32);
1537 result[bigIndex] = (int)difference;
1538 }
1539
1540 // Subtract remainder of longer number while borrow propagates
1541 boolean borrow = (difference >> 32 != 0);
1542 while (bigIndex > 0 && borrow)
1543 borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);
1544
1545 // Copy remainder of longer number
1546 while (bigIndex > 0)
1547 result[--bigIndex] = big[bigIndex];
1548
1873
1874 if (start < 0) {
1875 start = 0;
1876 }
1877 if (end < 0) {
1878 return ZERO;
1879 }
1880
1881 sliceSize = (end-start) + 1;
1882
1883 if (sliceSize <= 0) {
1884 return ZERO;
1885 }
1886
1887 // While performing Toom-Cook, all slices are positive and
1888 // the sign is adjusted when the final number is composed.
1889 if (start == 0 && sliceSize >= len) {
1890 return this.abs();
1891 }
1892
1893 int[] intSlice = new int[sliceSize];
1894 System.arraycopy(mag, start, intSlice, 0, sliceSize);
1895
1896 return new BigInteger(trustedStripLeadingZeroInts(intSlice), 1);
1897 }
1898
1899 /**
1900 * Does an exact division (that is, the remainder is known to be zero)
1901 * of the specified number by 3. This is used in Toom-Cook
1902 * multiplication. This is an efficient algorithm that runs in linear
1903 * time. If the argument is not exactly divisible by 3, results are
1904 * undefined. Note that this is expected to be called with positive
1905 * arguments only.
1906 */
1907 private BigInteger exactDivideBy3() {
1908 int len = mag.length;
1909 int[] result = new int[len];
1910 long x, w, q, borrow;
1911 borrow = 0L;
1912 for (int i=len-1; i >= 0; i--) {
1913 x = (mag[i] & LONG_MASK);
1930 borrow++;
1931 if (q >= 0xAAAAAAABL)
1932 borrow++;
1933 }
1934 }
1935 result = trustedStripLeadingZeroInts(result);
1936 return new BigInteger(result, signum);
1937 }
1938
1939 /**
1940 * Returns a new BigInteger representing n lower ints of the number.
1941 * This is used by Karatsuba multiplication and Karatsuba squaring.
1942 */
1943 private BigInteger getLower(int n) {
1944 int len = mag.length;
1945
1946 if (len <= n) {
1947 return abs();
1948 }
1949
1950 int[] lowerInts = new int[n];
1951 System.arraycopy(mag, len-n, lowerInts, 0, n);
1952
1953 return new BigInteger(trustedStripLeadingZeroInts(lowerInts), 1);
1954 }
1955
1956 /**
1957 * Returns a new BigInteger representing mag.length-n upper
1958 * ints of the number. This is used by Karatsuba multiplication and
1959 * Karatsuba squaring.
1960 */
1961 private BigInteger getUpper(int n) {
1962 int len = mag.length;
1963
1964 if (len <= n) {
1965 return ZERO;
1966 }
1967
1968 int upperLen = len - n;
1969 int[] upperInts = new int[upperLen];
1970 System.arraycopy(mag, 0, upperInts, 0, upperLen);
1971
1972 return new BigInteger(trustedStripLeadingZeroInts(upperInts), 1);
1973 }
1974
1975 // Squaring
1976
1977 /**
1978 * Returns a BigInteger whose value is {@code (this<sup>2</sup>)}.
1979 *
1980 * @return {@code this<sup>2</sup>}
1981 */
1982 private BigInteger square() {
1983 if (signum == 0) {
1984 return ZERO;
1985 }
1986 int len = mag.length;
1987
1988 if (len < KARATSUBA_SQUARE_THRESHOLD) {
1989 int[] z = squareToLen(mag, len, null);
2491 */
2492 static int bitLengthForInt(int n) {
2493 return 32 - Integer.numberOfLeadingZeros(n);
2494 }
2495
2496 /**
2497 * Left shift int array a up to len by n bits. Returns the array that
2498 * results from the shift since space may have to be reallocated.
2499 */
2500 private static int[] leftShift(int[] a, int len, int n) {
2501 int nInts = n >>> 5;
2502 int nBits = n&0x1F;
2503 int bitsInHighWord = bitLengthForInt(a[0]);
2504
2505 // If shift can be done without recopy, do so
2506 if (n <= (32-bitsInHighWord)) {
2507 primitiveLeftShift(a, len, nBits);
2508 return a;
2509 } else { // Array must be resized
2510 if (nBits <= (32-bitsInHighWord)) {
2511 int[] result = new int[nInts+len];
2512 System.arraycopy(a, 0, result, 0, len);
2513 primitiveLeftShift(result, result.length, nBits);
2514 return result;
2515 } else {
2516 int[] result = new int[nInts+len+1];
2517 System.arraycopy(a, 0, result, 0, len);
2518 primitiveRightShift(result, result.length, 32 - nBits);
2519 return result;
2520 }
2521 }
2522 }
2523
2524 // shifts a up to len right n bits assumes no leading zeros, 0<n<32
2525 static void primitiveRightShift(int[] a, int len, int n) {
2526 int n2 = 32 - n;
2527 for (int i=len-1, c=a[i]; i > 0; i--) {
2528 int b = c;
2529 c = a[i-1];
2530 a[i] = (c << n2) | (b >>> n);
2531 }
2532 a[0] >>>= n;
2533 }
2534
2535 // shifts a up to len left n bits assumes no leading zeros, 0<=n<32
2536 static void primitiveLeftShift(int[] a, int len, int n) {
3223 } else {
3224 // Possible int overflow in (-n) is not a trouble,
3225 // because shiftRightImpl considers its argument unsigned
3226 return shiftRightImpl(-n);
3227 }
3228 }
3229
3230 /**
3231 * Returns a magnitude array whose value is {@code (mag << n)}.
3232 * The shift distance, {@code n}, is considered unnsigned.
3233 * (Computes <code>this * 2<sup>n</sup></code>.)
3234 *
3235 * @param mag magnitude, the most-significant int ({@code mag[0]}) must be non-zero.
3236 * @param n unsigned shift distance, in bits.
3237 * @return {@code mag << n}
3238 */
3239 private static int[] shiftLeft(int[] mag, int n) {
3240 int nInts = n >>> 5;
3241 int nBits = n & 0x1f;
3242 int magLen = mag.length;
3243 int[] newMag = null;
3244
3245 if (nBits == 0) {
3246 newMag = new int[magLen + nInts];
3247 System.arraycopy(mag, 0, newMag, 0, magLen);
3248 } else {
3249 int i = 0;
3250 int nBits2 = 32 - nBits;
3251 int highBits = mag[0] >>> nBits2;
3252 if (highBits != 0) {
3253 newMag = new int[magLen + nInts + 1];
3254 newMag[i++] = highBits;
3255 } else {
3256 newMag = new int[magLen + nInts];
3257 }
3258 int j=0;
3259 while (j < magLen-1)
3260 newMag[i++] = mag[j++] << nBits | mag[j] >>> nBits2;
3261 newMag[i] = mag[j] << nBits;
3262 }
3263 return newMag;
3282 return this;
3283 } else {
3284 // Possible int overflow in {@code -n} is not a trouble,
3285 // because shiftLeft considers its argument unsigned
3286 return new BigInteger(shiftLeft(mag, -n), signum);
3287 }
3288 }
3289
3290 /**
3291 * Returns a BigInteger whose value is {@code (this >> n)}. The shift
3292 * distance, {@code n}, is considered unsigned.
3293 * (Computes <code>floor(this * 2<sup>-n</sup>)</code>.)
3294 *
3295 * @param n unsigned shift distance, in bits.
3296 * @return {@code this >> n}
3297 */
3298 private BigInteger shiftRightImpl(int n) {
3299 int nInts = n >>> 5;
3300 int nBits = n & 0x1f;
3301 int magLen = mag.length;
3302 int[] newMag = null;
3303
3304 // Special case: entire contents shifted off the end
3305 if (nInts >= magLen)
3306 return (signum >= 0 ? ZERO : negConst[1]);
3307
3308 if (nBits == 0) {
3309 int newMagLen = magLen - nInts;
3310 newMag = Arrays.copyOf(mag, newMagLen);
3311 } else {
3312 int i = 0;
3313 int highBits = mag[0] >>> nBits;
3314 if (highBits != 0) {
3315 newMag = new int[magLen - nInts];
3316 newMag[i++] = highBits;
3317 } else {
3318 newMag = new int[magLen - nInts -1];
3319 }
3320
3321 int nBits2 = 32 - nBits;
3322 int j=0;
3847 // The results will be concatenated into this StringBuilder
3848 StringBuilder sb = new StringBuilder();
3849 if (signum < 0) {
3850 toString(this.negate(), sb, radix, 0);
3851 sb.insert(0, '-');
3852 }
3853 else
3854 toString(this, sb, radix, 0);
3855
3856 return sb.toString();
3857 }
3858
3859 /** This method is used to perform toString when arguments are small. */
3860 private String smallToString(int radix) {
3861 if (signum == 0) {
3862 return "0";
3863 }
3864
3865 // Compute upper bound on number of digit groups and allocate space
3866 int maxNumDigitGroups = (4*mag.length + 6)/7;
3867 String[] digitGroup = new String[maxNumDigitGroups];
3868
3869 // Translate number to string, a digit group at a time
3870 BigInteger tmp = this.abs();
3871 int numGroups = 0;
3872 while (tmp.signum != 0) {
3873 BigInteger d = longRadix[radix];
3874
3875 MutableBigInteger q = new MutableBigInteger(),
3876 a = new MutableBigInteger(tmp.mag),
3877 b = new MutableBigInteger(d.mag);
3878 MutableBigInteger r = a.divide(b, q);
3879 BigInteger q2 = q.toBigInteger(tmp.signum * d.signum);
3880 BigInteger r2 = r.toBigInteger(tmp.signum * d.signum);
3881
3882 digitGroup[numGroups++] = Long.toString(r2.longValue(), radix);
3883 tmp = q2;
3884 }
3885
3886 // Put sign (if any) and first digit group into result buffer
3887 StringBuilder buf = new StringBuilder(numGroups*digitsPerLong[radix]+1);
3964 if (exponent < cacheLine.length) {
3965 return cacheLine[exponent];
3966 }
3967
3968 int oldLength = cacheLine.length;
3969 cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
3970 for (int i = oldLength; i <= exponent; i++) {
3971 cacheLine[i] = cacheLine[i - 1].pow(2);
3972 }
3973
3974 BigInteger[][] pc = powerCache; // volatile read again
3975 if (exponent >= pc[radix].length) {
3976 pc = pc.clone();
3977 pc[radix] = cacheLine;
3978 powerCache = pc; // volatile write, publish
3979 }
3980 return cacheLine[exponent];
3981 }
3982
3983 /* zero[i] is a string of i consecutive zeros. */
3984 private static String[] zeros = new String[64];
3985 static {
3986 zeros[63] =
3987 "000000000000000000000000000000000000000000000000000000000000000";
3988 for (int i=0; i < 63; i++)
3989 zeros[i] = zeros[63].substring(0, i);
3990 }
3991
3992 /**
3993 * Returns the decimal String representation of this BigInteger.
3994 * The digit-to-character mapping provided by
3995 * {@code Character.forDigit} is used, and a minus sign is
3996 * prepended if appropriate. (This representation is compatible
3997 * with the {@link #BigInteger(String) (String)} constructor, and
3998 * allows for String concatenation with Java's + operator.)
3999 *
4000 * @return decimal String representation of this BigInteger.
4001 * @see Character#forDigit
4002 * @see #BigInteger(java.lang.String)
4003 */
4004 public String toString() {
4246 boolean increment = (twiceSignifFloor & 1) != 0
4247 && ((signifFloor & 1) != 0 || abs().getLowestSetBit() < shift);
4248 long signifRounded = increment ? signifFloor + 1 : signifFloor;
4249 long bits = (long) ((exponent + DoubleConsts.EXP_BIAS))
4250 << (DoubleConsts.SIGNIFICAND_WIDTH - 1);
4251 bits += signifRounded;
4252 /*
4253 * If signifRounded == 2^53, we'd need to set all of the significand
4254 * bits to zero and add 1 to the exponent. This is exactly the behavior
4255 * we get from just adding signifRounded to bits directly. If the
4256 * exponent is Double.MAX_EXPONENT, we round up (correctly) to
4257 * Double.POSITIVE_INFINITY.
4258 */
4259 bits |= signum & DoubleConsts.SIGN_BIT_MASK;
4260 return Double.longBitsToDouble(bits);
4261 }
4262
4263 /**
4264 * Returns a copy of the input array stripped of any leading zero bytes.
4265 */
4266 private static int[] stripLeadingZeroInts(int[] val) {
4267 int vlen = val.length;
4268 int keep;
4269
4270 // Find first nonzero byte
4271 for (keep = 0; keep < vlen && val[keep] == 0; keep++)
4272 ;
4273 return java.util.Arrays.copyOfRange(val, keep, vlen);
4274 }
4275
4276 /**
4277 * Returns the input array stripped of any leading zero bytes.
4278 * Since the source is trusted the copying may be skipped.
4279 */
4280 private static int[] trustedStripLeadingZeroInts(int[] val) {
4281 int vlen = val.length;
4282 int keep;
4283
4284 // Find first nonzero byte
4285 for (keep = 0; keep < vlen && val[keep] == 0; keep++)
4286 ;
4287 return keep == 0 ? val : java.util.Arrays.copyOfRange(val, keep, vlen);
4288 }
4289
4290 /**
4291 * Returns a copy of the input array stripped of any leading zero bytes.
4292 */
4293 private static int[] stripLeadingZeroBytes(byte[] a, int off, int len) {
4294 int indexBound = off + len;
4295 int keep;
4296
4297 // Find first nonzero byte
4298 for (keep = off; keep < indexBound && a[keep] == 0; keep++)
4299 ;
4300
4301 // Allocate new array and copy relevant part of input array
4302 int intLength = ((indexBound - keep) + 3) >>> 2;
4303 int[] result = new int[intLength];
4304 int b = indexBound - 1;
4305 for (int i = intLength-1; i >= 0; i--) {
4306 result[i] = a[b--] & 0xff;
4307 int bytesRemaining = b - keep + 1;
4308 int bytesToTransfer = Math.min(3, bytesRemaining);
4309 for (int j=8; j <= (bytesToTransfer << 3); j += 8)
4310 result[i] |= ((a[b--] & 0xff) << j);
4311 }
4312 return result;
4313 }
4314
4315 /**
4316 * Takes an array a representing a negative 2's-complement number and
4317 * returns the minimal (no leading zero bytes) unsigned whose value is -a.
4318 */
4319 private static int[] makePositive(byte[] a, int off, int len) {
4320 int keep, k;
4321 int indexBound = off + len;
4322
4323 // Find first non-sign (0xff) byte of input
4324 for (keep=off; keep < indexBound && a[keep] == -1; keep++)
4325 ;
4326
4327
4328 /* Allocate output array. If all non-sign bytes are 0x00, we must
4329 * allocate space for one extra output byte. */
4330 for (k=keep; k < indexBound && a[k] == 0; k++)
4331 ;
4332
4333 int extraByte = (k == indexBound) ? 1 : 0;
4334 int intLength = ((indexBound - keep + extraByte) + 3) >>> 2;
4335 int[] result = new int[intLength];
4336
4337 /* Copy one's complement of input into output, leaving extra
4338 * byte (if it exists) == 0x00 */
4339 int b = indexBound - 1;
4340 for (int i = intLength-1; i >= 0; i--) {
4341 result[i] = a[b--] & 0xff;
4342 int numBytesToTransfer = Math.min(3, b-keep+1);
4343 if (numBytesToTransfer < 0)
4344 numBytesToTransfer = 0;
4345 for (int j=8; j <= 8*numBytesToTransfer; j += 8)
4346 result[i] |= ((a[b--] & 0xff) << j);
4347
4348 // Mask indicates which bits must be complemented
4349 int mask = -1 >>> (8*(3-numBytesToTransfer));
4350 result[i] = ~result[i] & mask;
4351 }
4352
4353 // Add one to one's complement to generate two's complement
4354 for (int i=result.length-1; i >= 0; i--) {
4355 result[i] = (int)((result[i] & LONG_MASK) + 1);
4356 if (result[i] != 0)
4357 break;
4358 }
4359
4360 return result;
4361 }
4362
4363 /**
4364 * Takes an array a representing a negative 2's-complement number and
4365 * returns the minimal (no leading zero ints) unsigned whose value is -a.
4366 */
4367 private static int[] makePositive(int[] a) {
4368 int keep, j;
4369
4370 // Find first non-sign (0xffffffff) int of input
4371 for (keep=0; keep < a.length && a[keep] == -1; keep++)
4372 ;
4373
4374 /* Allocate output array. If all non-sign ints are 0x00, we must
4375 * allocate space for one extra output int. */
4376 for (j=keep; j < a.length && a[j] == 0; j++)
4377 ;
4378 int extraInt = (j == a.length ? 1 : 0);
4379 int[] result = new int[a.length - keep + extraInt];
4380
4381 /* Copy one's complement of input into output, leaving extra
4382 * int (if it exists) == 0x00 */
4383 for (int i = keep; i < a.length; i++)
4384 result[i - keep + extraInt] = ~a[i];
4385
4386 // Add one to one's complement to generate two's complement
4387 for (int i=result.length-1; ++result[i] == 0; i--)
4388 ;
4389
4390 return result;
4391 }
4392
4393 /*
4394 * The following two arrays are used for fast String conversions. Both
4395 * are indexed by radix. The first is the number of digits of the given
4396 * radix that can fit in a Java long without "going negative", i.e., the
4397 * highest integer n such that radix**n < 2**63. The second is the
4398 * "long radix" that tears each number into "long digits", each of which
4399 * consists of the number of digits in the corresponding element in
4400 * digitsPerLong (longRadix[i] = i**digitPerLong[i]). Both arrays have
4401 * nonsense values in their 0 and 1 elements, as radixes 0 and 1 are not
4402 * used.
4403 */
4404 private static int[] digitsPerLong = {0, 0,
4405 62, 39, 31, 27, 24, 22, 20, 19, 18, 18, 17, 17, 16, 16, 15, 15, 15, 14,
4406 14, 14, 14, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12};
4407
4408 private static BigInteger[] longRadix = {null, null,
4409 valueOf(0x4000000000000000L), valueOf(0x383d9170b85ff80bL),
4410 valueOf(0x4000000000000000L), valueOf(0x6765c793fa10079dL),
4411 valueOf(0x41c21cb8e1000000L), valueOf(0x3642798750226111L),
4412 valueOf(0x1000000000000000L), valueOf(0x12bf307ae81ffd59L),
4413 valueOf( 0xde0b6b3a7640000L), valueOf(0x4d28cb56c33fa539L),
4414 valueOf(0x1eca170c00000000L), valueOf(0x780c7372621bd74dL),
4415 valueOf(0x1e39a5057d810000L), valueOf(0x5b27ac993df97701L),
4416 valueOf(0x1000000000000000L), valueOf(0x27b95e997e21d9f1L),
4417 valueOf(0x5da0e1e53c5c8000L), valueOf( 0xb16a458ef403f19L),
4418 valueOf(0x16bcc41e90000000L), valueOf(0x2d04b7fdd9c0ef49L),
4419 valueOf(0x5658597bcaa24000L), valueOf( 0x6feb266931a75b7L),
4420 valueOf( 0xc29e98000000000L), valueOf(0x14adf4b7320334b9L),
4421 valueOf(0x226ed36478bfa000L), valueOf(0x383d9170b85ff80bL),
4422 valueOf(0x5a3c23e39c000000L), valueOf( 0x4e900abb53e6b71L),
4423 valueOf( 0x7600ec618141000L), valueOf( 0xaee5720ee830681L),
4424 valueOf(0x1000000000000000L), valueOf(0x172588ad4f5f0981L),
4425 valueOf(0x211e44f7d02c1000L), valueOf(0x2ee56725f06e5c71L),
4426 valueOf(0x41c21cb8e1000000L)};
4427
4428 /*
4429 * These two arrays are the integer analogue of above.
4430 */
4431 private static int[] digitsPerInt = {0, 0, 30, 19, 15, 13, 11,
4432 11, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6,
4433 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5};
4434
4435 private static int[] intRadix = {0, 0,
4436 0x40000000, 0x4546b3db, 0x40000000, 0x48c27395, 0x159fd800,
4437 0x75db9c97, 0x40000000, 0x17179149, 0x3b9aca00, 0xcc6db61,
4438 0x19a10000, 0x309f1021, 0x57f6c100, 0xa2f1b6f, 0x10000000,
4439 0x18754571, 0x247dbc80, 0x3547667b, 0x4c4b4000, 0x6b5a6e1d,
4440 0x6c20a40, 0x8d2d931, 0xb640000, 0xe8d4a51, 0x1269ae40,
4441 0x17179149, 0x1cb91000, 0x23744899, 0x2b73a840, 0x34e63b41,
4442 0x40000000, 0x4cfa3cc1, 0x5c13d840, 0x6d91b519, 0x39aa400
4443 };
4444
4445 /**
4446 * These routines provide access to the two's complement representation
4447 * of BigIntegers.
4448 */
4449
4450 /**
4451 * Returns the length of the two's complement representation in ints,
4452 * including space for at least one sign bit.
4453 */
4454 private int intLength() {
4455 return (bitLength() >>> 5) + 1;
|