24 */
25
26 /*
27 * Portions Copyright (c) 1995 Colin Plumb. All rights reserved.
28 */
29
30 package java.math;
31
32 import java.io.IOException;
33 import java.io.ObjectInputStream;
34 import java.io.ObjectOutputStream;
35 import java.io.ObjectStreamField;
36 import java.util.Arrays;
37 import java.util.Objects;
38 import java.util.Random;
39 import java.util.concurrent.ThreadLocalRandom;
40
41 import jdk.internal.math.DoubleConsts;
42 import jdk.internal.math.FloatConsts;
43 import jdk.internal.HotSpotIntrinsicCandidate;
44 import jdk.internal.vm.annotation.Stable;
45
46 /**
47 * Immutable arbitrary-precision integers. All operations behave as if
48 * BigIntegers were represented in two's-complement notation (like Java's
49 * primitive integer types). BigInteger provides analogues to all of Java's
50 * primitive integer operators, and all relevant methods from java.lang.Math.
51 * Additionally, BigInteger provides operations for modular arithmetic, GCD
52 * calculation, primality testing, prime generation, bit manipulation,
53 * and a few other miscellaneous operations.
54 *
55 * <p>Semantics of arithmetic operations exactly mimic those of Java's integer
56 * arithmetic operators, as defined in <i>The Java™ Language Specification</i>.
57 * For example, division by zero throws an {@code ArithmeticException}, and
58 * division of a negative by a positive yields a negative (or zero) remainder.
59 *
60 * <p>Semantics of shift operations extend those of Java's shift operators
61 * to allow for negative shift distances. A right-shift with a negative
62 * shift distance results in a left shift, and vice-versa. The unsigned
63 * right shift operator ({@code >>>}) is omitted since this operation
511
512 if (cursor == len) {
513 signum = 0;
514 mag = ZERO.mag;
515 return;
516 }
517
518 numDigits = len - cursor;
519 signum = sign;
520
521 // Pre-allocate array of expected size. May be too large but can
522 // never be too small. Typically exact.
523 long numBits = ((numDigits * bitsPerDigit[radix]) >>> 10) + 1;
524 if (numBits + 31 >= (1L << 32)) {
525 reportOverflow();
526 }
527 int numWords = (int) (numBits + 31) >>> 5;
528 int[] magnitude = new int[numWords];
529
530 // Process first (potentially short) digit group
531 int firstGroupLen = numDigits % digitsPerInt[radix];
532 if (firstGroupLen == 0)
533 firstGroupLen = digitsPerInt[radix];
534 String group = val.substring(cursor, cursor += firstGroupLen);
535 magnitude[numWords - 1] = Integer.parseInt(group, radix);
536 if (magnitude[numWords - 1] < 0)
537 throw new NumberFormatException("Illegal digit");
538
539 // Process remaining digit groups
540 int superRadix = intRadix[radix];
541 int groupVal = 0;
542 while (cursor < len) {
543 group = val.substring(cursor, cursor += digitsPerInt[radix]);
544 groupVal = Integer.parseInt(group, radix);
545 if (groupVal < 0)
546 throw new NumberFormatException("Illegal digit");
547 destructiveMulAdd(magnitude, superRadix, groupVal);
548 }
549 // Required for cases where the array was overallocated.
550 mag = trustedStripLeadingZeroInts(magnitude);
551 if (mag.length >= MAX_MAG_LENGTH) {
552 checkRange();
553 }
554 }
555
556 /*
557 * Constructs a new BigInteger using a char array with radix=10.
558 * Sign is precalculated outside and not allowed in the val. The {@code val}
559 * array is assumed to be unchanged for the duration of the constructor
560 * call.
561 */
562 BigInteger(char[] val, int sign, int len) {
563 int cursor = 0, numDigits;
571 mag = ZERO.mag;
572 return;
573 }
574
575 numDigits = len - cursor;
576 signum = sign;
577 // Pre-allocate array of expected size
578 int numWords;
579 if (len < 10) {
580 numWords = 1;
581 } else {
582 long numBits = ((numDigits * bitsPerDigit[10]) >>> 10) + 1;
583 if (numBits + 31 >= (1L << 32)) {
584 reportOverflow();
585 }
586 numWords = (int) (numBits + 31) >>> 5;
587 }
588 int[] magnitude = new int[numWords];
589
590 // Process first (potentially short) digit group
591 int firstGroupLen = numDigits % digitsPerInt[10];
592 if (firstGroupLen == 0)
593 firstGroupLen = digitsPerInt[10];
594 magnitude[numWords - 1] = parseInt(val, cursor, cursor += firstGroupLen);
595
596 // Process remaining digit groups
597 while (cursor < len) {
598 int groupVal = parseInt(val, cursor, cursor += digitsPerInt[10]);
599 destructiveMulAdd(magnitude, intRadix[10], groupVal);
600 }
601 mag = trustedStripLeadingZeroInts(magnitude);
602 if (mag.length >= MAX_MAG_LENGTH) {
603 checkRange();
604 }
605 }
606
607 // Create an integer with the digits between the two indexes
608 // Assumes start < end. The result may be negative, but it
609 // is to be treated as an unsigned value.
610 private int parseInt(char[] source, int start, int end) {
611 int result = Character.digit(source[start++], 10);
612 if (result == -1)
613 throw new NumberFormatException(new String(source));
614
615 for (int index = start; index < end; index++) {
616 int nextVal = Character.digit(source[index], 10);
617 if (nextVal == -1)
618 throw new NumberFormatException(new String(source));
619 result = 10*result + nextVal;
1153 }
1154
1155 //Static Factory Methods
1156
1157 /**
1158 * Returns a BigInteger whose value is equal to that of the
1159 * specified {@code long}.
1160 *
1161 * @apiNote This static factory method is provided in preference
1162 * to a ({@code long}) constructor because it allows for reuse of
1163 * frequently used BigIntegers.
1164 *
1165 * @param val value of the BigInteger to return.
1166 * @return a BigInteger with the specified value.
1167 */
1168 public static BigInteger valueOf(long val) {
1169 // If -MAX_CONSTANT < val < MAX_CONSTANT, return stashed constant
1170 if (val == 0)
1171 return ZERO;
1172 if (val > 0 && val <= MAX_CONSTANT)
1173 return posConst[(int) val];
1174 else if (val < 0 && val >= -MAX_CONSTANT)
1175 return negConst[(int) -val];
1176
1177 return new BigInteger(val);
1178 }
1179
1180 /**
1181 * Constructs a BigInteger with the specified value, which may not be zero.
1182 */
1183 private BigInteger(long val) {
1184 if (val < 0) {
1185 val = -val;
1186 signum = -1;
1187 } else {
1188 signum = 1;
1189 }
1190
1191 int highWord = (int)(val >>> 32);
1192 if (highWord == 0) {
1193 mag = new int[1];
1194 mag[0] = (int)val;
1195 } else {
1198 mag[1] = (int)val;
1199 }
1200 }
1201
1202 /**
1203 * Returns a BigInteger with the given two's complement representation.
1204 * Assumes that the input array will not be modified (the returned
1205 * BigInteger will reference the input array if feasible).
1206 */
1207 private static BigInteger valueOf(int val[]) {
1208 return (val[0] > 0 ? new BigInteger(val, 1) : new BigInteger(val));
1209 }
1210
1211 // Constants
1212
1213 /**
1214 * Initialize static constant array when class is loaded.
1215 */
1216 private static final int MAX_CONSTANT = 16;
1217 @Stable
1218 private static final BigInteger[] posConst = new BigInteger[MAX_CONSTANT+1];
1219 @Stable
1220 private static final BigInteger[] negConst = new BigInteger[MAX_CONSTANT+1];
1221
1222 /**
1223 * The cache of powers of each radix. This allows us to not have to
1224 * recalculate powers of radix^(2^n) more than once. This speeds
1225 * Schoenhage recursive base conversion significantly.
1226 */
1227 private static volatile BigInteger[][] powerCache;
1228
1229 /** The cache of logarithms of radices for base conversion. */
1230 private static final double[] logCache;
1231
1232 /** The natural log of 2. This is used in computing cache indices. */
1233 private static final double LOG_TWO = Math.log(2.0);
1234
1235 static {
1236 assert 0 < KARATSUBA_THRESHOLD
1237 && KARATSUBA_THRESHOLD < TOOM_COOK_THRESHOLD
1238 && TOOM_COOK_THRESHOLD < Integer.MAX_VALUE
1239 && 0 < KARATSUBA_SQUARE_THRESHOLD
1240 && KARATSUBA_SQUARE_THRESHOLD < TOOM_COOK_SQUARE_THRESHOLD
1241 && TOOM_COOK_SQUARE_THRESHOLD < Integer.MAX_VALUE :
1242 "Algorithm thresholds are inconsistent";
1243
1244 for (int i = 1; i <= MAX_CONSTANT; i++) {
1245 int[] magnitude = new int[1];
1246 magnitude[0] = i;
1247 posConst[i] = new BigInteger(magnitude, 1);
1248 negConst[i] = new BigInteger(magnitude, -1);
1249 }
1250
1251 /*
1252 * Initialize the cache of radix^(2^x) values used for base conversion
1253 * with just the very first value. Additional values will be created
1254 * on demand.
1255 */
1256 powerCache = new BigInteger[Character.MAX_RADIX+1][];
1257 logCache = new double[Character.MAX_RADIX+1];
1258
1259 for (int i=Character.MIN_RADIX; i <= Character.MAX_RADIX; i++) {
1260 powerCache[i] = new BigInteger[] { BigInteger.valueOf(i) };
1261 logCache[i] = Math.log(i);
1262 }
1263 }
1264
1265 /**
1266 * The BigInteger constant zero.
1267 *
1268 * @since 1.2
1269 */
1270 public static final BigInteger ZERO = new BigInteger(new int[0], 0);
1271
1272 /**
1273 * The BigInteger constant one.
1274 *
1275 * @since 1.2
1276 */
1277 public static final BigInteger ONE = valueOf(1);
1278
1279 /**
1280 * The BigInteger constant two.
1281 *
1282 * @since 9
1283 */
1284 public static final BigInteger TWO = valueOf(2);
1285
1286 /**
1287 * The BigInteger constant -1. (Not exported.)
1288 */
1289 private static final BigInteger NEGATIVE_ONE = valueOf(-1);
1290
1291 /**
1292 * The BigInteger constant ten.
1293 *
1294 * @since 1.5
1295 */
1296 public static final BigInteger TEN = valueOf(10);
1297
1298 // Arithmetic Operations
1299
1300 /**
1301 * Returns a BigInteger whose value is {@code (this + val)}.
1302 *
1303 * @param val value to be added to this BigInteger.
1304 * @return {@code this + val}
1305 */
1306 public BigInteger add(BigInteger val) {
1307 if (val.signum == 0)
1308 return this;
1309 if (signum == 0)
1310 return val;
1311 if (val.signum == signum)
1312 return new BigInteger(add(mag, val.mag), signum);
1313
1314 int cmp = compareMagnitude(val);
1315 if (cmp == 0)
1316 return ZERO;
2713 * @return <code>this<sup>exponent</sup> mod m</code>
2714 * @throws ArithmeticException {@code m} ≤ 0 or the exponent is
2715 * negative and this BigInteger is not <i>relatively
2716 * prime</i> to {@code m}.
2717 * @see #modInverse
2718 */
2719 public BigInteger modPow(BigInteger exponent, BigInteger m) {
2720 if (m.signum <= 0)
2721 throw new ArithmeticException("BigInteger: modulus not positive");
2722
2723 // Trivial cases
2724 if (exponent.signum == 0)
2725 return (m.equals(ONE) ? ZERO : ONE);
2726
2727 if (this.equals(ONE))
2728 return (m.equals(ONE) ? ZERO : ONE);
2729
2730 if (this.equals(ZERO) && exponent.signum >= 0)
2731 return ZERO;
2732
2733 if (this.equals(negConst[1]) && (!exponent.testBit(0)))
2734 return (m.equals(ONE) ? ZERO : ONE);
2735
2736 boolean invertResult;
2737 if ((invertResult = (exponent.signum < 0)))
2738 exponent = exponent.negate();
2739
2740 BigInteger base = (this.signum < 0 || this.compareTo(m) >= 0
2741 ? this.mod(m) : this);
2742 BigInteger result;
2743 if (m.testBit(0)) { // odd modulus
2744 result = base.oddModPow(exponent, m);
2745 } else {
2746 /*
2747 * Even modulus. Tear it into an "odd part" (m1) and power of two
2748 * (m2), exponentiate mod m1, manually exponentiate mod m2, and
2749 * use Chinese Remainder Theorem to combine results.
2750 */
2751
2752 // Tear m apart into odd part (m1) and power of 2 (m2)
2753 int p = m.getLowestSetBit(); // Max pow of 2 that divides m
3384 return new BigInteger(shiftLeft(mag, -n), signum);
3385 }
3386 }
3387
3388 /**
3389 * Returns a BigInteger whose value is {@code (this >> n)}. The shift
3390 * distance, {@code n}, is considered unsigned.
3391 * (Computes <code>floor(this * 2<sup>-n</sup>)</code>.)
3392 *
3393 * @param n unsigned shift distance, in bits.
3394 * @return {@code this >> n}
3395 */
3396 private BigInteger shiftRightImpl(int n) {
3397 int nInts = n >>> 5;
3398 int nBits = n & 0x1f;
3399 int magLen = mag.length;
3400 int newMag[] = null;
3401
3402 // Special case: entire contents shifted off the end
3403 if (nInts >= magLen)
3404 return (signum >= 0 ? ZERO : negConst[1]);
3405
3406 if (nBits == 0) {
3407 int newMagLen = magLen - nInts;
3408 newMag = Arrays.copyOf(mag, newMagLen);
3409 } else {
3410 int i = 0;
3411 int highBits = mag[0] >>> nBits;
3412 if (highBits != 0) {
3413 newMag = new int[magLen - nInts];
3414 newMag[i++] = highBits;
3415 } else {
3416 newMag = new int[magLen - nInts -1];
3417 }
3418
3419 int nBits2 = 32 - nBits;
3420 int j=0;
3421 while (j < magLen - nInts - 1)
3422 newMag[i++] = (mag[j++] << nBits2) | (mag[j] >>> nBits);
3423 }
3424
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,
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
4109 * <i>big-endian</i> byte-order: the most significant byte is in
4471
4472 /* Allocate output array. If all non-sign ints are 0x00, we must
4473 * allocate space for one extra output int. */
4474 for (j=keep; j < a.length && a[j] == 0; j++)
4475 ;
4476 int extraInt = (j == a.length ? 1 : 0);
4477 int result[] = new int[a.length - keep + extraInt];
4478
4479 /* Copy one's complement of input into output, leaving extra
4480 * int (if it exists) == 0x00 */
4481 for (int i = keep; i < a.length; i++)
4482 result[i - keep + extraInt] = ~a[i];
4483
4484 // Add one to one's complement to generate two's complement
4485 for (int i=result.length-1; ++result[i] == 0; i--)
4486 ;
4487
4488 return result;
4489 }
4490
4491 /*
4492 * The following two arrays are used for fast String conversions. Both
4493 * are indexed by radix. The first is the number of digits of the given
4494 * radix that can fit in a Java long without "going negative", i.e., the
4495 * highest integer n such that radix**n < 2**63. The second is the
4496 * "long radix" that tears each number into "long digits", each of which
4497 * consists of the number of digits in the corresponding element in
4498 * digitsPerLong (longRadix[i] = i**digitPerLong[i]). Both arrays have
4499 * nonsense values in their 0 and 1 elements, as radixes 0 and 1 are not
4500 * used.
4501 */
4502 private static int digitsPerLong[] = {0, 0,
4503 62, 39, 31, 27, 24, 22, 20, 19, 18, 18, 17, 17, 16, 16, 15, 15, 15, 14,
4504 14, 14, 14, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12};
4505
4506 private static BigInteger longRadix[] = {null, null,
4507 valueOf(0x4000000000000000L), valueOf(0x383d9170b85ff80bL),
4508 valueOf(0x4000000000000000L), valueOf(0x6765c793fa10079dL),
4509 valueOf(0x41c21cb8e1000000L), valueOf(0x3642798750226111L),
4510 valueOf(0x1000000000000000L), valueOf(0x12bf307ae81ffd59L),
4511 valueOf( 0xde0b6b3a7640000L), valueOf(0x4d28cb56c33fa539L),
4512 valueOf(0x1eca170c00000000L), valueOf(0x780c7372621bd74dL),
4513 valueOf(0x1e39a5057d810000L), valueOf(0x5b27ac993df97701L),
4514 valueOf(0x1000000000000000L), valueOf(0x27b95e997e21d9f1L),
4515 valueOf(0x5da0e1e53c5c8000L), valueOf( 0xb16a458ef403f19L),
4516 valueOf(0x16bcc41e90000000L), valueOf(0x2d04b7fdd9c0ef49L),
4517 valueOf(0x5658597bcaa24000L), valueOf( 0x6feb266931a75b7L),
4518 valueOf( 0xc29e98000000000L), valueOf(0x14adf4b7320334b9L),
4519 valueOf(0x226ed36478bfa000L), valueOf(0x383d9170b85ff80bL),
4520 valueOf(0x5a3c23e39c000000L), valueOf( 0x4e900abb53e6b71L),
4521 valueOf( 0x7600ec618141000L), valueOf( 0xaee5720ee830681L),
4522 valueOf(0x1000000000000000L), valueOf(0x172588ad4f5f0981L),
4523 valueOf(0x211e44f7d02c1000L), valueOf(0x2ee56725f06e5c71L),
4524 valueOf(0x41c21cb8e1000000L)};
4525
4526 /*
4527 * These two arrays are the integer analogue of above.
4528 */
4529 private static int digitsPerInt[] = {0, 0, 30, 19, 15, 13, 11,
4530 11, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6,
4531 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5};
4532
4533 private static int intRadix[] = {0, 0,
4534 0x40000000, 0x4546b3db, 0x40000000, 0x48c27395, 0x159fd800,
4535 0x75db9c97, 0x40000000, 0x17179149, 0x3b9aca00, 0xcc6db61,
4536 0x19a10000, 0x309f1021, 0x57f6c100, 0xa2f1b6f, 0x10000000,
4537 0x18754571, 0x247dbc80, 0x3547667b, 0x4c4b4000, 0x6b5a6e1d,
4538 0x6c20a40, 0x8d2d931, 0xb640000, 0xe8d4a51, 0x1269ae40,
4539 0x17179149, 0x1cb91000, 0x23744899, 0x2b73a840, 0x34e63b41,
4540 0x40000000, 0x4cfa3cc1, 0x5c13d840, 0x6d91b519, 0x39aa400
4541 };
4542
4543 /**
4544 * These routines provide access to the two's complement representation
4545 * of BigIntegers.
4546 */
4547
4548 /**
4549 * Returns the length of the two's complement representation in ints,
4550 * including space for at least one sign bit.
4551 */
4552 private int intLength() {
4553 return (bitLength() >>> 5) + 1;
4554 }
4555
4556 /* Returns sign bit */
4557 private int signBit() {
4558 return signum < 0 ? 1 : 0;
4559 }
4560
4561 /* Returns an int of sign bits */
4562 private int signInt() {
4563 return signum < 0 ? -1 : 0;
4564 }
4565
4566 /**
4567 * Returns the specified int of the little-endian two's complement
4568 * representation (int 0 is the least significant). The int number can
4569 * be arbitrarily high (values are logically preceded by infinitely many
4570 * sign ints).
4571 */
4572 private int getInt(int n) {
4573 if (n < 0)
4574 return 0;
4575 if (n >= mag.length)
4576 return signInt();
4577
4578 int magInt = mag[mag.length-n-1];
|
24 */
25
26 /*
27 * Portions Copyright (c) 1995 Colin Plumb. All rights reserved.
28 */
29
30 package java.math;
31
32 import java.io.IOException;
33 import java.io.ObjectInputStream;
34 import java.io.ObjectOutputStream;
35 import java.io.ObjectStreamField;
36 import java.util.Arrays;
37 import java.util.Objects;
38 import java.util.Random;
39 import java.util.concurrent.ThreadLocalRandom;
40
41 import jdk.internal.math.DoubleConsts;
42 import jdk.internal.math.FloatConsts;
43 import jdk.internal.HotSpotIntrinsicCandidate;
44 import jdk.internal.misc.VM;
45 import jdk.internal.vm.annotation.Stable;
46
47 /**
48 * Immutable arbitrary-precision integers. All operations behave as if
49 * BigIntegers were represented in two's-complement notation (like Java's
50 * primitive integer types). BigInteger provides analogues to all of Java's
51 * primitive integer operators, and all relevant methods from java.lang.Math.
52 * Additionally, BigInteger provides operations for modular arithmetic, GCD
53 * calculation, primality testing, prime generation, bit manipulation,
54 * and a few other miscellaneous operations.
55 *
56 * <p>Semantics of arithmetic operations exactly mimic those of Java's integer
57 * arithmetic operators, as defined in <i>The Java™ Language Specification</i>.
58 * For example, division by zero throws an {@code ArithmeticException}, and
59 * division of a negative by a positive yields a negative (or zero) remainder.
60 *
61 * <p>Semantics of shift operations extend those of Java's shift operators
62 * to allow for negative shift distances. A right-shift with a negative
63 * shift distance results in a left shift, and vice-versa. The unsigned
64 * right shift operator ({@code >>>}) is omitted since this operation
512
513 if (cursor == len) {
514 signum = 0;
515 mag = ZERO.mag;
516 return;
517 }
518
519 numDigits = len - cursor;
520 signum = sign;
521
522 // Pre-allocate array of expected size. May be too large but can
523 // never be too small. Typically exact.
524 long numBits = ((numDigits * bitsPerDigit[radix]) >>> 10) + 1;
525 if (numBits + 31 >= (1L << 32)) {
526 reportOverflow();
527 }
528 int numWords = (int) (numBits + 31) >>> 5;
529 int[] magnitude = new int[numWords];
530
531 // Process first (potentially short) digit group
532 int firstGroupLen = numDigits % DIGITS_PER_INT[radix];
533 if (firstGroupLen == 0)
534 firstGroupLen = DIGITS_PER_INT[radix];
535 String group = val.substring(cursor, cursor += firstGroupLen);
536 magnitude[numWords - 1] = Integer.parseInt(group, radix);
537 if (magnitude[numWords - 1] < 0)
538 throw new NumberFormatException("Illegal digit");
539
540 // Process remaining digit groups
541 int superRadix = INT_RADIX[radix];
542 int groupVal = 0;
543 while (cursor < len) {
544 group = val.substring(cursor, cursor += DIGITS_PER_INT[radix]);
545 groupVal = Integer.parseInt(group, radix);
546 if (groupVal < 0)
547 throw new NumberFormatException("Illegal digit");
548 destructiveMulAdd(magnitude, superRadix, groupVal);
549 }
550 // Required for cases where the array was overallocated.
551 mag = trustedStripLeadingZeroInts(magnitude);
552 if (mag.length >= MAX_MAG_LENGTH) {
553 checkRange();
554 }
555 }
556
557 /*
558 * Constructs a new BigInteger using a char array with radix=10.
559 * Sign is precalculated outside and not allowed in the val. The {@code val}
560 * array is assumed to be unchanged for the duration of the constructor
561 * call.
562 */
563 BigInteger(char[] val, int sign, int len) {
564 int cursor = 0, numDigits;
572 mag = ZERO.mag;
573 return;
574 }
575
576 numDigits = len - cursor;
577 signum = sign;
578 // Pre-allocate array of expected size
579 int numWords;
580 if (len < 10) {
581 numWords = 1;
582 } else {
583 long numBits = ((numDigits * bitsPerDigit[10]) >>> 10) + 1;
584 if (numBits + 31 >= (1L << 32)) {
585 reportOverflow();
586 }
587 numWords = (int) (numBits + 31) >>> 5;
588 }
589 int[] magnitude = new int[numWords];
590
591 // Process first (potentially short) digit group
592 int firstGroupLen = numDigits % DIGITS_PER_INT[10];
593 if (firstGroupLen == 0)
594 firstGroupLen = DIGITS_PER_INT[10];
595 magnitude[numWords - 1] = parseInt(val, cursor, cursor += firstGroupLen);
596
597 // Process remaining digit groups
598 while (cursor < len) {
599 int groupVal = parseInt(val, cursor, cursor += DIGITS_PER_INT[10]);
600 destructiveMulAdd(magnitude, INT_RADIX[10], groupVal);
601 }
602 mag = trustedStripLeadingZeroInts(magnitude);
603 if (mag.length >= MAX_MAG_LENGTH) {
604 checkRange();
605 }
606 }
607
608 // Create an integer with the digits between the two indexes
609 // Assumes start < end. The result may be negative, but it
610 // is to be treated as an unsigned value.
611 private int parseInt(char[] source, int start, int end) {
612 int result = Character.digit(source[start++], 10);
613 if (result == -1)
614 throw new NumberFormatException(new String(source));
615
616 for (int index = start; index < end; index++) {
617 int nextVal = Character.digit(source[index], 10);
618 if (nextVal == -1)
619 throw new NumberFormatException(new String(source));
620 result = 10*result + nextVal;
1154 }
1155
1156 //Static Factory Methods
1157
1158 /**
1159 * Returns a BigInteger whose value is equal to that of the
1160 * specified {@code long}.
1161 *
1162 * @apiNote This static factory method is provided in preference
1163 * to a ({@code long}) constructor because it allows for reuse of
1164 * frequently used BigIntegers.
1165 *
1166 * @param val value of the BigInteger to return.
1167 * @return a BigInteger with the specified value.
1168 */
1169 public static BigInteger valueOf(long val) {
1170 // If -MAX_CONSTANT < val < MAX_CONSTANT, return stashed constant
1171 if (val == 0)
1172 return ZERO;
1173 if (val > 0 && val <= MAX_CONSTANT)
1174 return POS_CONST[(int) val];
1175 else if (val < 0 && val >= -MAX_CONSTANT)
1176 return NEG_CONST[(int) -val];
1177
1178 return new BigInteger(val);
1179 }
1180
1181 /**
1182 * Constructs a BigInteger with the specified value, which may not be zero.
1183 */
1184 private BigInteger(long val) {
1185 if (val < 0) {
1186 val = -val;
1187 signum = -1;
1188 } else {
1189 signum = 1;
1190 }
1191
1192 int highWord = (int)(val >>> 32);
1193 if (highWord == 0) {
1194 mag = new int[1];
1195 mag[0] = (int)val;
1196 } else {
1199 mag[1] = (int)val;
1200 }
1201 }
1202
1203 /**
1204 * Returns a BigInteger with the given two's complement representation.
1205 * Assumes that the input array will not be modified (the returned
1206 * BigInteger will reference the input array if feasible).
1207 */
1208 private static BigInteger valueOf(int val[]) {
1209 return (val[0] > 0 ? new BigInteger(val, 1) : new BigInteger(val));
1210 }
1211
1212 // Constants
1213
1214 /**
1215 * Initialize static constant array when class is loaded.
1216 */
1217 private static final int MAX_CONSTANT = 16;
1218 @Stable
1219 private static final BigInteger[] POS_CONST;
1220 @Stable
1221 private static final BigInteger[] NEG_CONST;
1222
1223 /**
1224 * The cache of powers of each radix. This allows us to not have to
1225 * recalculate powers of radix^(2^n) more than once. This speeds
1226 * Schoenhage recursive base conversion significantly.
1227 */
1228 private static volatile BigInteger[][] powerCache;
1229
1230 /** The cache of logarithms of radices for base conversion. */
1231 private static final double[] LOG_CACHE;
1232
1233 /** The natural log of 2. This is used in computing cache indices. */
1234 private static final double LOG_TWO = Math.log(2.0);
1235
1236 /** Precalculated strings of consecutive zeros of index length */
1237 private static final String[] ZEROS;
1238
1239 /*
1240 * The following two arrays are used for fast String conversions. Both
1241 * are indexed by radix. The first is the number of digits of the given
1242 * radix that can fit in a Java long without "going negative", i.e., the
1243 * highest integer n such that radix**n < 2**63. The second is the
1244 * "long radix" that tears each number into "long digits", each of which
1245 * consists of the number of digits in the corresponding element in
1246 * DIGITS_PER_LONG (longRadix[i] = i**digitPerLong[i]). Both arrays have
1247 * nonsense values in their 0 and 1 elements, as radixes 0 and 1 are not
1248 * used.
1249 */
1250 private static final int[] DIGITS_PER_LONG;
1251
1252 // Initialized in static initializer
1253 private static final BigInteger[] LONG_RADIX;
1254
1255 /*
1256 * These two arrays are the integer analogue of above.
1257 */
1258 private static final int[] DIGITS_PER_INT;
1259
1260 private static final int[] INT_RADIX;
1261
1262 /** Archiving proxy */
1263 private static Object[] archivedCaches;
1264
1265 static {
1266 assert 0 < KARATSUBA_THRESHOLD
1267 && KARATSUBA_THRESHOLD < TOOM_COOK_THRESHOLD
1268 && TOOM_COOK_THRESHOLD < Integer.MAX_VALUE
1269 && 0 < KARATSUBA_SQUARE_THRESHOLD
1270 && KARATSUBA_SQUARE_THRESHOLD < TOOM_COOK_SQUARE_THRESHOLD
1271 && TOOM_COOK_SQUARE_THRESHOLD < Integer.MAX_VALUE :
1272 "Algorithm thresholds are inconsistent";
1273
1274 VM.initializeFromArchive(BigInteger.class);
1275 Object[] caches = archivedCaches;
1276 if (caches == null) {
1277 BigInteger zero = new BigInteger(new int[0], 0);
1278 String[] zeros = new String[64];
1279 BigInteger[] posConst = new BigInteger[MAX_CONSTANT+1];
1280 BigInteger[] negConst = new BigInteger[MAX_CONSTANT+1];
1281
1282 for (int i = 1; i <= MAX_CONSTANT; i++) {
1283 int[] magnitude = new int[1];
1284 magnitude[0] = i;
1285 posConst[i] = new BigInteger(magnitude, 1);
1286 negConst[i] = new BigInteger(magnitude, -1);
1287 }
1288
1289 // Need to set these early to allow BigInteger.valueOf to work in
1290 // subsequent code.
1291 POS_CONST = posConst;
1292 NEG_CONST = negConst;
1293 /*
1294 * Initialize the cache of radix^(2^x) values used for base conversion
1295 * with just the very first value. Additional values will be created
1296 * on demand.
1297 */
1298 BigInteger[][] initialPowerCache = new BigInteger[Character.MAX_RADIX + 1][];
1299 double[] logCache = new double[Character.MAX_RADIX + 1];
1300
1301 for (int i = Character.MIN_RADIX; i <= Character.MAX_RADIX; i++) {
1302 initialPowerCache[i] = new BigInteger[]{ BigInteger.valueOf(i) };
1303 logCache[i] = Math.log(i);
1304 }
1305
1306 // Initialize caches used for fast String conversion
1307
1308 zeros[63] = "000000000000000000000000000000000000000000000000000000000000000";
1309 for (int i = 0; i < 63; i++) {
1310 zeros[i] = zeros[63].substring(0, i);
1311 }
1312
1313 BigInteger x1 = valueOf(0x1000000000000000L);
1314 BigInteger x4 = valueOf(0x4000000000000000L);
1315 BigInteger[] longRadix = {null, null,
1316 x4, valueOf(0x383d9170b85ff80bL),
1317 x4, valueOf(0x6765c793fa10079dL),
1318 valueOf(0x41c21cb8e1000000L), valueOf(0x3642798750226111L),
1319 x1, valueOf(0x12bf307ae81ffd59L),
1320 valueOf( 0xde0b6b3a7640000L), valueOf(0x4d28cb56c33fa539L),
1321 valueOf(0x1eca170c00000000L), valueOf(0x780c7372621bd74dL),
1322 valueOf(0x1e39a5057d810000L), valueOf(0x5b27ac993df97701L),
1323 x1, valueOf(0x27b95e997e21d9f1L),
1324 valueOf(0x5da0e1e53c5c8000L), valueOf( 0xb16a458ef403f19L),
1325 valueOf(0x16bcc41e90000000L), valueOf(0x2d04b7fdd9c0ef49L),
1326 valueOf(0x5658597bcaa24000L), valueOf( 0x6feb266931a75b7L),
1327 valueOf( 0xc29e98000000000L), valueOf(0x14adf4b7320334b9L),
1328 valueOf(0x226ed36478bfa000L), valueOf(0x383d9170b85ff80bL),
1329 valueOf(0x5a3c23e39c000000L), valueOf( 0x4e900abb53e6b71L),
1330 valueOf( 0x7600ec618141000L), valueOf( 0xaee5720ee830681L),
1331 x1, valueOf(0x172588ad4f5f0981L),
1332 valueOf(0x211e44f7d02c1000L), valueOf(0x2ee56725f06e5c71L),
1333 valueOf(0x41c21cb8e1000000L)};
1334
1335 int[] digitsPerLong = {0, 0,
1336 62, 39, 31, 27, 24, 22, 20, 19, 18, 18, 17, 17, 16, 16, 15, 15, 15, 14,
1337 14, 14, 14, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12};
1338
1339 int digitsPerInt[] = {0, 0, 30, 19, 15, 13, 11,
1340 11, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6,
1341 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5};
1342
1343 int intRadix[] = {0, 0,
1344 0x40000000, 0x4546b3db, 0x40000000, 0x48c27395, 0x159fd800,
1345 0x75db9c97, 0x40000000, 0x17179149, 0x3b9aca00, 0xcc6db61,
1346 0x19a10000, 0x309f1021, 0x57f6c100, 0xa2f1b6f, 0x10000000,
1347 0x18754571, 0x247dbc80, 0x3547667b, 0x4c4b4000, 0x6b5a6e1d,
1348 0x6c20a40, 0x8d2d931, 0xb640000, 0xe8d4a51, 0x1269ae40,
1349 0x17179149, 0x1cb91000, 0x23744899, 0x2b73a840, 0x34e63b41,
1350 0x40000000, 0x4cfa3cc1, 0x5c13d840, 0x6d91b519, 0x39aa400
1351 };
1352
1353 archivedCaches = caches = new Object[] {
1354 posConst,
1355 negConst,
1356 zero,
1357 zeros,
1358 initialPowerCache,
1359 logCache,
1360 longRadix,
1361 digitsPerLong,
1362 digitsPerInt,
1363 intRadix
1364 };
1365
1366 } else {
1367 POS_CONST = (BigInteger[])caches[0];
1368 NEG_CONST = (BigInteger[])caches[1];
1369 }
1370
1371 ZERO = (BigInteger)caches[2];
1372 ONE = POS_CONST[1];
1373 TWO = POS_CONST[2];
1374 TEN = POS_CONST[10];
1375 NEGATIVE_ONE = NEG_CONST[1];
1376 ZEROS = (String[])caches[3];
1377 powerCache = (BigInteger[][])caches[4];
1378 LOG_CACHE = (double[])caches[5];
1379 LONG_RADIX = (BigInteger[])caches[6];
1380 DIGITS_PER_LONG = (int[])caches[7];
1381 DIGITS_PER_INT = (int[])caches[8];
1382 INT_RADIX = (int[])caches[9];
1383 }
1384
1385 /**
1386 * The BigInteger constant zero.
1387 *
1388 * @since 1.2
1389 */
1390 public static final BigInteger ZERO;
1391
1392 /**
1393 * The BigInteger constant one.
1394 *
1395 * @since 1.2
1396 */
1397 public static final BigInteger ONE;
1398
1399 /**
1400 * The BigInteger constant two.
1401 *
1402 * @since 9
1403 */
1404 public static final BigInteger TWO;
1405
1406 /**
1407 * The BigInteger constant -1. (Not exported.)
1408 */
1409 private static final BigInteger NEGATIVE_ONE;
1410
1411 /**
1412 * The BigInteger constant ten.
1413 *
1414 * @since 1.5
1415 */
1416 public static final BigInteger TEN;
1417
1418 // Arithmetic Operations
1419
1420 /**
1421 * Returns a BigInteger whose value is {@code (this + val)}.
1422 *
1423 * @param val value to be added to this BigInteger.
1424 * @return {@code this + val}
1425 */
1426 public BigInteger add(BigInteger val) {
1427 if (val.signum == 0)
1428 return this;
1429 if (signum == 0)
1430 return val;
1431 if (val.signum == signum)
1432 return new BigInteger(add(mag, val.mag), signum);
1433
1434 int cmp = compareMagnitude(val);
1435 if (cmp == 0)
1436 return ZERO;
2833 * @return <code>this<sup>exponent</sup> mod m</code>
2834 * @throws ArithmeticException {@code m} ≤ 0 or the exponent is
2835 * negative and this BigInteger is not <i>relatively
2836 * prime</i> to {@code m}.
2837 * @see #modInverse
2838 */
2839 public BigInteger modPow(BigInteger exponent, BigInteger m) {
2840 if (m.signum <= 0)
2841 throw new ArithmeticException("BigInteger: modulus not positive");
2842
2843 // Trivial cases
2844 if (exponent.signum == 0)
2845 return (m.equals(ONE) ? ZERO : ONE);
2846
2847 if (this.equals(ONE))
2848 return (m.equals(ONE) ? ZERO : ONE);
2849
2850 if (this.equals(ZERO) && exponent.signum >= 0)
2851 return ZERO;
2852
2853 if (this.equals(NEG_CONST[1]) && (!exponent.testBit(0)))
2854 return (m.equals(ONE) ? ZERO : ONE);
2855
2856 boolean invertResult;
2857 if ((invertResult = (exponent.signum < 0)))
2858 exponent = exponent.negate();
2859
2860 BigInteger base = (this.signum < 0 || this.compareTo(m) >= 0
2861 ? this.mod(m) : this);
2862 BigInteger result;
2863 if (m.testBit(0)) { // odd modulus
2864 result = base.oddModPow(exponent, m);
2865 } else {
2866 /*
2867 * Even modulus. Tear it into an "odd part" (m1) and power of two
2868 * (m2), exponentiate mod m1, manually exponentiate mod m2, and
2869 * use Chinese Remainder Theorem to combine results.
2870 */
2871
2872 // Tear m apart into odd part (m1) and power of 2 (m2)
2873 int p = m.getLowestSetBit(); // Max pow of 2 that divides m
3504 return new BigInteger(shiftLeft(mag, -n), signum);
3505 }
3506 }
3507
3508 /**
3509 * Returns a BigInteger whose value is {@code (this >> n)}. The shift
3510 * distance, {@code n}, is considered unsigned.
3511 * (Computes <code>floor(this * 2<sup>-n</sup>)</code>.)
3512 *
3513 * @param n unsigned shift distance, in bits.
3514 * @return {@code this >> n}
3515 */
3516 private BigInteger shiftRightImpl(int n) {
3517 int nInts = n >>> 5;
3518 int nBits = n & 0x1f;
3519 int magLen = mag.length;
3520 int newMag[] = null;
3521
3522 // Special case: entire contents shifted off the end
3523 if (nInts >= magLen)
3524 return (signum >= 0 ? ZERO : NEG_CONST[1]);
3525
3526 if (nBits == 0) {
3527 int newMagLen = magLen - nInts;
3528 newMag = Arrays.copyOf(mag, newMagLen);
3529 } else {
3530 int i = 0;
3531 int highBits = mag[0] >>> nBits;
3532 if (highBits != 0) {
3533 newMag = new int[magLen - nInts];
3534 newMag[i++] = highBits;
3535 } else {
3536 newMag = new int[magLen - nInts -1];
3537 }
3538
3539 int nBits2 = 32 - nBits;
3540 int j=0;
3541 while (j < magLen - nInts - 1)
3542 newMag[i++] = (mag[j++] << nBits2) | (mag[j] >>> nBits);
3543 }
3544
4071 else
4072 toString(this, sb, radix, 0);
4073
4074 return sb.toString();
4075 }
4076
4077 /** This method is used to perform toString when arguments are small. */
4078 private String smallToString(int radix) {
4079 if (signum == 0) {
4080 return "0";
4081 }
4082
4083 // Compute upper bound on number of digit groups and allocate space
4084 int maxNumDigitGroups = (4*mag.length + 6)/7;
4085 String digitGroup[] = new String[maxNumDigitGroups];
4086
4087 // Translate number to string, a digit group at a time
4088 BigInteger tmp = this.abs();
4089 int numGroups = 0;
4090 while (tmp.signum != 0) {
4091 BigInteger d = LONG_RADIX[radix];
4092
4093 MutableBigInteger q = new MutableBigInteger(),
4094 a = new MutableBigInteger(tmp.mag),
4095 b = new MutableBigInteger(d.mag);
4096 MutableBigInteger r = a.divide(b, q);
4097 BigInteger q2 = q.toBigInteger(tmp.signum * d.signum);
4098 BigInteger r2 = r.toBigInteger(tmp.signum * d.signum);
4099
4100 digitGroup[numGroups++] = Long.toString(r2.longValue(), radix);
4101 tmp = q2;
4102 }
4103
4104 // Put sign (if any) and first digit group into result buffer
4105 StringBuilder buf = new StringBuilder(numGroups* DIGITS_PER_LONG[radix]+1);
4106 if (signum < 0) {
4107 buf.append('-');
4108 }
4109 buf.append(digitGroup[numGroups-1]);
4110
4111 // Append remaining digit groups padded with leading zeros
4112 for (int i = numGroups-2; i >= 0; i--) {
4113 // Prepend (any) leading zeros for this digit group
4114 int numLeadingZeros = DIGITS_PER_LONG[radix]-digitGroup[i].length();
4115 if (numLeadingZeros != 0) {
4116 buf.append(ZEROS[numLeadingZeros]);
4117 }
4118 buf.append(digitGroup[i]);
4119 }
4120 return buf.toString();
4121 }
4122
4123 /**
4124 * Converts the specified BigInteger to a string and appends to
4125 * {@code sb}. This implements the recursive Schoenhage algorithm
4126 * for base conversions.
4127 * <p>
4128 * See Knuth, Donald, _The Art of Computer Programming_, Vol. 2,
4129 * Answers to Exercises (4.4) Question 14.
4130 *
4131 * @param u The number to convert to a string.
4132 * @param sb The StringBuilder that will be appended to in place.
4133 * @param radix The base to convert to.
4134 * @param digits The minimum number of digits to pad to.
4135 */
4136 private static void toString(BigInteger u, StringBuilder sb, int radix,
4141 String s = u.smallToString(radix);
4142
4143 // Pad with internal zeros if necessary.
4144 // Don't pad if we're at the beginning of the string.
4145 if ((s.length() < digits) && (sb.length() > 0)) {
4146 for (int i=s.length(); i < digits; i++) {
4147 sb.append('0');
4148 }
4149 }
4150
4151 sb.append(s);
4152 return;
4153 }
4154
4155 int b, n;
4156 b = u.bitLength();
4157
4158 // Calculate a value for n in the equation radix^(2^n) = u
4159 // and subtract 1 from that value. This is used to find the
4160 // cache index that contains the best value to divide u.
4161 n = (int) Math.round(Math.log(b * LOG_TWO / LOG_CACHE[radix]) / LOG_TWO - 1.0);
4162 BigInteger v = getRadixConversionCache(radix, n);
4163 BigInteger[] results;
4164 results = u.divideAndRemainder(v);
4165
4166 int expectedDigits = 1 << n;
4167
4168 // Now recursively build the two halves of each number.
4169 toString(results[0], sb, radix, digits-expectedDigits);
4170 toString(results[1], sb, radix, expectedDigits);
4171 }
4172
4173 /**
4174 * Returns the value radix^(2^exponent) from the cache.
4175 * If this value doesn't already exist in the cache, it is added.
4176 * <p>
4177 * This could be changed to a more complicated caching method using
4178 * {@code Future}.
4179 */
4180 private static BigInteger getRadixConversionCache(int radix, int exponent) {
4181 BigInteger[] cacheLine = powerCache[radix]; // volatile read
4182 if (exponent < cacheLine.length) {
4183 return cacheLine[exponent];
4184 }
4185
4186 int oldLength = cacheLine.length;
4187 cacheLine = Arrays.copyOf(cacheLine, exponent + 1);
4188 for (int i = oldLength; i <= exponent; i++) {
4189 cacheLine[i] = cacheLine[i - 1].pow(2);
4190 }
4191
4192 BigInteger[][] pc = powerCache; // volatile read again
4193 if (exponent >= pc[radix].length) {
4194 pc = pc.clone();
4195 pc[radix] = cacheLine;
4196 powerCache = pc; // volatile write, publish
4197 }
4198 return cacheLine[exponent];
4199 }
4200
4201 /**
4202 * Returns the decimal String representation of this BigInteger.
4203 * The digit-to-character mapping provided by
4204 * {@code Character.forDigit} is used, and a minus sign is
4205 * prepended if appropriate. (This representation is compatible
4206 * with the {@link #BigInteger(String) (String)} constructor, and
4207 * allows for String concatenation with Java's + operator.)
4208 *
4209 * @return decimal String representation of this BigInteger.
4210 * @see Character#forDigit
4211 * @see #BigInteger(java.lang.String)
4212 */
4213 public String toString() {
4214 return toString(10);
4215 }
4216
4217 /**
4218 * Returns a byte array containing the two's-complement
4219 * representation of this BigInteger. The byte array will be in
4220 * <i>big-endian</i> byte-order: the most significant byte is in
4582
4583 /* Allocate output array. If all non-sign ints are 0x00, we must
4584 * allocate space for one extra output int. */
4585 for (j=keep; j < a.length && a[j] == 0; j++)
4586 ;
4587 int extraInt = (j == a.length ? 1 : 0);
4588 int result[] = new int[a.length - keep + extraInt];
4589
4590 /* Copy one's complement of input into output, leaving extra
4591 * int (if it exists) == 0x00 */
4592 for (int i = keep; i < a.length; i++)
4593 result[i - keep + extraInt] = ~a[i];
4594
4595 // Add one to one's complement to generate two's complement
4596 for (int i=result.length-1; ++result[i] == 0; i--)
4597 ;
4598
4599 return result;
4600 }
4601
4602 /**
4603 * These routines provide access to the two's complement representation
4604 * of BigIntegers.
4605 */
4606
4607 /**
4608 * Returns the length of the two's complement representation in ints,
4609 * including space for at least one sign bit.
4610 */
4611 private int intLength() {
4612 return (bitLength() >>> 5) + 1;
4613 }
4614
4615 /* Returns an int of sign bits */
4616 private int signInt() {
4617 return signum < 0 ? -1 : 0;
4618 }
4619
4620 /**
4621 * Returns the specified int of the little-endian two's complement
4622 * representation (int 0 is the least significant). The int number can
4623 * be arbitrarily high (values are logically preceded by infinitely many
4624 * sign ints).
4625 */
4626 private int getInt(int n) {
4627 if (n < 0)
4628 return 0;
4629 if (n >= mag.length)
4630 return signInt();
4631
4632 int magInt = mag[mag.length-n-1];
|