243 private static final int TOOM_COOK_SQUARE_THRESHOLD = 140;
244
245 /**
246 * The threshold value for using Burnikel-Ziegler division. If the number
247 * of ints in the number are larger than this value,
248 * Burnikel-Ziegler division will be used. This value is found
249 * experimentally to work well.
250 */
251 static final int BURNIKEL_ZIEGLER_THRESHOLD = 50;
252
253 /**
254 * The threshold value for using Schoenhage recursive base conversion. If
255 * the number of ints in the number are larger than this value,
256 * the Schoenhage algorithm will be used. In practice, it appears that the
257 * Schoenhage routine is faster for any threshold down to 2, and is
258 * relatively flat for thresholds between 2-25, so this choice may be
259 * varied within this range for very small effect.
260 */
261 private static final int SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 8;
262
263 //Constructors
264
265 /**
266 * Translates a byte array containing the two's-complement binary
267 * representation of a BigInteger into a BigInteger. The input array is
268 * assumed to be in <i>big-endian</i> byte-order: the most significant
269 * byte is in the zeroth element.
270 *
271 * @param val big-endian two's-complement binary representation of
272 * BigInteger.
273 * @throws NumberFormatException {@code val} is zero bytes long.
274 */
275 public BigInteger(byte[] val) {
276 if (val.length == 0)
277 throw new NumberFormatException("Zero length BigInteger");
278
279 if (val[0] < 0) {
280 mag = makePositive(val);
281 signum = -1;
282 } else {
283 mag = stripLeadingZeroBytes(val);
1433 (little[--littleIndex] & LONG_MASK) +
1434 (difference >> 32);
1435 result[bigIndex] = (int)difference;
1436 }
1437
1438 // Subtract remainder of longer number while borrow propagates
1439 boolean borrow = (difference >> 32 != 0);
1440 while (bigIndex > 0 && borrow)
1441 borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);
1442
1443 // Copy remainder of longer number
1444 while (bigIndex > 0)
1445 result[--bigIndex] = big[bigIndex];
1446
1447 return result;
1448 }
1449
1450 /**
1451 * Returns a BigInteger whose value is {@code (this * val)}.
1452 *
1453 * @param val value to be multiplied by this BigInteger.
1454 * @return {@code this * val}
1455 */
1456 public BigInteger multiply(BigInteger val) {
1457 if (val.signum == 0 || signum == 0)
1458 return ZERO;
1459
1460 int xlen = mag.length;
1461 int ylen = val.mag.length;
1462
1463 if ((xlen < KARATSUBA_THRESHOLD) || (ylen < KARATSUBA_THRESHOLD)) {
1464 int resultSign = signum == val.signum ? 1 : -1;
1465 if (val.mag.length == 1) {
1466 return multiplyByInt(mag,val.mag[0], resultSign);
1467 }
1468 if (mag.length == 1) {
1469 return multiplyByInt(val.mag,mag[0], resultSign);
1470 }
1471 int[] result = multiplyToLen(mag, xlen,
1472 val.mag, ylen, null);
1473 result = trustedStripLeadingZeroInts(result);
1474 return new BigInteger(result, resultSign);
1475 } else {
1476 if ((xlen < TOOM_COOK_THRESHOLD) && (ylen < TOOM_COOK_THRESHOLD)) {
1477 return multiplyKaratsuba(this, val);
1478 } else {
1479 return multiplyToomCook3(this, val);
1480 }
|
243 private static final int TOOM_COOK_SQUARE_THRESHOLD = 140;
244
245 /**
246 * The threshold value for using Burnikel-Ziegler division. If the number
247 * of ints in the number are larger than this value,
248 * Burnikel-Ziegler division will be used. This value is found
249 * experimentally to work well.
250 */
251 static final int BURNIKEL_ZIEGLER_THRESHOLD = 50;
252
253 /**
254 * The threshold value for using Schoenhage recursive base conversion. If
255 * the number of ints in the number are larger than this value,
256 * the Schoenhage algorithm will be used. In practice, it appears that the
257 * Schoenhage routine is faster for any threshold down to 2, and is
258 * relatively flat for thresholds between 2-25, so this choice may be
259 * varied within this range for very small effect.
260 */
261 private static final int SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 8;
262
263 /**
264 * The threshold value for using squaring code to perform multiplication
265 * of a {@code BigInteger} instance by itself. If the number of ints in
266 * the number are larger than this value, {@code multiply(this)} will
267 * return {@code square()}.
268 */
269 private static final int MULTIPLY_SQUARE_THRESHOLD = 20;
270
271 // Constructors
272
273 /**
274 * Translates a byte array containing the two's-complement binary
275 * representation of a BigInteger into a BigInteger. The input array is
276 * assumed to be in <i>big-endian</i> byte-order: the most significant
277 * byte is in the zeroth element.
278 *
279 * @param val big-endian two's-complement binary representation of
280 * BigInteger.
281 * @throws NumberFormatException {@code val} is zero bytes long.
282 */
283 public BigInteger(byte[] val) {
284 if (val.length == 0)
285 throw new NumberFormatException("Zero length BigInteger");
286
287 if (val[0] < 0) {
288 mag = makePositive(val);
289 signum = -1;
290 } else {
291 mag = stripLeadingZeroBytes(val);
1441 (little[--littleIndex] & LONG_MASK) +
1442 (difference >> 32);
1443 result[bigIndex] = (int)difference;
1444 }
1445
1446 // Subtract remainder of longer number while borrow propagates
1447 boolean borrow = (difference >> 32 != 0);
1448 while (bigIndex > 0 && borrow)
1449 borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);
1450
1451 // Copy remainder of longer number
1452 while (bigIndex > 0)
1453 result[--bigIndex] = big[bigIndex];
1454
1455 return result;
1456 }
1457
1458 /**
1459 * Returns a BigInteger whose value is {@code (this * val)}.
1460 *
1461 * @implNote An implementation may offer better algorithmic
1462 * performance when {@code val == this}.
1463 *
1464 * @param val value to be multiplied by this BigInteger.
1465 * @return {@code this * val}
1466 */
1467 public BigInteger multiply(BigInteger val) {
1468 if (val.signum == 0 || signum == 0)
1469 return ZERO;
1470
1471 int xlen = mag.length;
1472
1473 if (val == this && xlen > MULTIPLY_SQUARE_THRESHOLD) {
1474 return square();
1475 }
1476
1477 int ylen = val.mag.length;
1478
1479 if ((xlen < KARATSUBA_THRESHOLD) || (ylen < KARATSUBA_THRESHOLD)) {
1480 int resultSign = signum == val.signum ? 1 : -1;
1481 if (val.mag.length == 1) {
1482 return multiplyByInt(mag,val.mag[0], resultSign);
1483 }
1484 if (mag.length == 1) {
1485 return multiplyByInt(val.mag,mag[0], resultSign);
1486 }
1487 int[] result = multiplyToLen(mag, xlen,
1488 val.mag, ylen, null);
1489 result = trustedStripLeadingZeroInts(result);
1490 return new BigInteger(result, resultSign);
1491 } else {
1492 if ((xlen < TOOM_COOK_THRESHOLD) && (ylen < TOOM_COOK_THRESHOLD)) {
1493 return multiplyKaratsuba(this, val);
1494 } else {
1495 return multiplyToomCook3(this, val);
1496 }
|