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
64 * only makes sense for a fixed sized word and not for a
2604 if (n <= (32-bitsInHighWord)) {
2605 primitiveLeftShift(a, len, nBits);
2606 return a;
2607 } else { // Array must be resized
2608 if (nBits <= (32-bitsInHighWord)) {
2609 int result[] = new int[nInts+len];
2610 System.arraycopy(a, 0, result, 0, len);
2611 primitiveLeftShift(result, result.length, nBits);
2612 return result;
2613 } else {
2614 int result[] = new int[nInts+len+1];
2615 System.arraycopy(a, 0, result, 0, len);
2616 primitiveRightShift(result, result.length, 32 - nBits);
2617 return result;
2618 }
2619 }
2620 }
2621
2622 // shifts a up to len right n bits assumes no leading zeros, 0<n<32
2623 static void primitiveRightShift(int[] a, int len, int n) {
2624 int n2 = 32 - n;
2625 for (int i=len-1, c=a[i]; i > 0; i--) {
2626 int b = c;
2627 c = a[i-1];
2628 a[i] = (c << n2) | (b >>> n);
2629 }
2630 a[0] >>>= n;
2631 }
2632
2633 // shifts a up to len left n bits assumes no leading zeros, 0<=n<32
2634 static void primitiveLeftShift(int[] a, int len, int n) {
2635 if (len == 0 || n == 0)
2636 return;
2637
2638 int n2 = 32 - n;
2639 for (int i=0, c=a[i], m=i+len-1; i < m; i++) {
2640 int b = c;
2641 c = a[i+1];
2642 a[i] = (b << n) | (c >>> n2);
2643 }
2644 a[len-1] <<= n;
2645 }
2646
2647 /**
2648 * Calculate bitlength of contents of the first len elements an int array,
2649 * assuming there are no leading zero ints.
2650 */
2651 private static int bitLength(int[] val, int len) {
2652 if (len == 0)
2653 return 0;
2654 return ((len - 1) << 5) + bitLengthForInt(val[0]);
2655 }
2656
2657 /**
2658 * Returns a BigInteger whose value is the absolute value of this
2659 * BigInteger.
2660 *
2661 * @return {@code abs(this)}
2662 */
2663 public BigInteger abs() {
3336 */
3337 private static int[] shiftLeft(int[] mag, int n) {
3338 int nInts = n >>> 5;
3339 int nBits = n & 0x1f;
3340 int magLen = mag.length;
3341 int newMag[] = null;
3342
3343 if (nBits == 0) {
3344 newMag = new int[magLen + nInts];
3345 System.arraycopy(mag, 0, newMag, 0, magLen);
3346 } else {
3347 int i = 0;
3348 int nBits2 = 32 - nBits;
3349 int highBits = mag[0] >>> nBits2;
3350 if (highBits != 0) {
3351 newMag = new int[magLen + nInts + 1];
3352 newMag[i++] = highBits;
3353 } else {
3354 newMag = new int[magLen + nInts];
3355 }
3356 int j=0;
3357 while (j < magLen-1)
3358 newMag[i++] = mag[j++] << nBits | mag[j] >>> nBits2;
3359 newMag[i] = mag[j] << nBits;
3360 }
3361 return newMag;
3362 }
3363
3364 /**
3365 * Returns a BigInteger whose value is {@code (this >> n)}. Sign
3366 * extension is performed. The shift distance, {@code n}, may be
3367 * negative, in which case this method performs a left shift.
3368 * (Computes <code>floor(this / 2<sup>n</sup>)</code>.)
3369 *
3370 * @param n shift distance, in bits.
3371 * @return {@code this >> n}
3372 * @see #shiftLeft
3373 */
3374 public BigInteger shiftRight(int n) {
3375 if (signum == 0)
3376 return ZERO;
3377 if (n > 0) {
3378 return shiftRightImpl(n);
3379 } else if (n == 0) {
3380 return this;
3381 } else {
3382 // Possible int overflow in {@code -n} is not a trouble,
3383 // because shiftLeft considers its argument unsigned
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
3425 if (signum < 0) {
3426 // Find out whether any one-bits were shifted off the end.
3427 boolean onesLost = false;
3428 for (int i=magLen-1, j=magLen-nInts; i >= j && !onesLost; i--)
3429 onesLost = (mag[i] != 0);
3430 if (!onesLost && nBits != 0)
3431 onesLost = (mag[magLen - nInts - 1] << (32 - nBits) != 0);
3432
3433 if (onesLost)
3434 newMag = javaIncrement(newMag);
3435 }
3436
3437 return new BigInteger(newMag, signum);
3438 }
3439
3440 int[] javaIncrement(int[] val) {
3441 int lastSum = 0;
3442 for (int i=val.length-1; i >= 0 && lastSum == 0; i--)
3443 lastSum = (val[i] += 1);
3444 if (lastSum == 0) {
3445 val = new int[val.length+1];
3446 val[0] = 1;
3447 }
3448 return val;
3449 }
3450
3451 // Bitwise Operations
3452
3453 /**
3454 * Returns a BigInteger whose value is {@code (this & val)}. (This
3455 * method returns a negative BigInteger if and only if this and val are
3456 * both negative.)
3457 *
|
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 import jdk.internal.vm.annotation.ForceInline;
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
65 * only makes sense for a fixed sized word and not for a
2605 if (n <= (32-bitsInHighWord)) {
2606 primitiveLeftShift(a, len, nBits);
2607 return a;
2608 } else { // Array must be resized
2609 if (nBits <= (32-bitsInHighWord)) {
2610 int result[] = new int[nInts+len];
2611 System.arraycopy(a, 0, result, 0, len);
2612 primitiveLeftShift(result, result.length, nBits);
2613 return result;
2614 } else {
2615 int result[] = new int[nInts+len+1];
2616 System.arraycopy(a, 0, result, 0, len);
2617 primitiveRightShift(result, result.length, 32 - nBits);
2618 return result;
2619 }
2620 }
2621 }
2622
2623 // shifts a up to len right n bits assumes no leading zeros, 0<n<32
2624 static void primitiveRightShift(int[] a, int len, int n) {
2625 Objects.checkFromToIndex(0, len, a.length);
2626 shiftRightImplWorker(a, a, 1, n, len-1);
2627 a[0] >>>= n;
2628 }
2629
2630 // shifts a up to len left n bits assumes no leading zeros, 0<=n<32
2631 static void primitiveLeftShift(int[] a, int len, int n) {
2632 if (len == 0 || n == 0)
2633 return;
2634 Objects.checkFromToIndex(0, len, a.length);
2635 shiftLeftImplWorker(a, a, 0, n, len-1);
2636 a[len-1] <<= n;
2637 }
2638
2639 /**
2640 * Calculate bitlength of contents of the first len elements an int array,
2641 * assuming there are no leading zero ints.
2642 */
2643 private static int bitLength(int[] val, int len) {
2644 if (len == 0)
2645 return 0;
2646 return ((len - 1) << 5) + bitLengthForInt(val[0]);
2647 }
2648
2649 /**
2650 * Returns a BigInteger whose value is the absolute value of this
2651 * BigInteger.
2652 *
2653 * @return {@code abs(this)}
2654 */
2655 public BigInteger abs() {
3328 */
3329 private static int[] shiftLeft(int[] mag, int n) {
3330 int nInts = n >>> 5;
3331 int nBits = n & 0x1f;
3332 int magLen = mag.length;
3333 int newMag[] = null;
3334
3335 if (nBits == 0) {
3336 newMag = new int[magLen + nInts];
3337 System.arraycopy(mag, 0, newMag, 0, magLen);
3338 } else {
3339 int i = 0;
3340 int nBits2 = 32 - nBits;
3341 int highBits = mag[0] >>> nBits2;
3342 if (highBits != 0) {
3343 newMag = new int[magLen + nInts + 1];
3344 newMag[i++] = highBits;
3345 } else {
3346 newMag = new int[magLen + nInts];
3347 }
3348 int numIter = magLen - 1;
3349 Objects.checkFromToIndex(0, numIter + 1, mag.length);
3350 Objects.checkFromToIndex(i, numIter + i + 1, newMag.length);
3351 shiftLeftImplWorker(newMag, mag, i, nBits, numIter);
3352 newMag[numIter + i] = mag[numIter] << nBits;
3353 }
3354 return newMag;
3355 }
3356
3357 @ForceInline
3358 @HotSpotIntrinsicCandidate
3359 private static void shiftLeftImplWorker(int[] newArr, int[] oldArr, int newIdx, int shiftCount, int numIter) {
3360 int shiftCountRight = 32 - shiftCount;
3361 int oldIdx = 0;
3362 while (oldIdx < numIter) {
3363 newArr[newIdx++] = (oldArr[oldIdx++] << shiftCount) | (oldArr[oldIdx] >>> shiftCountRight);
3364 }
3365 }
3366
3367 /**
3368 * Returns a BigInteger whose value is {@code (this >> n)}. Sign
3369 * extension is performed. The shift distance, {@code n}, may be
3370 * negative, in which case this method performs a left shift.
3371 * (Computes <code>floor(this / 2<sup>n</sup>)</code>.)
3372 *
3373 * @param n shift distance, in bits.
3374 * @return {@code this >> n}
3375 * @see #shiftLeft
3376 */
3377 public BigInteger shiftRight(int n) {
3378 if (signum == 0)
3379 return ZERO;
3380 if (n > 0) {
3381 return shiftRightImpl(n);
3382 } else if (n == 0) {
3383 return this;
3384 } else {
3385 // Possible int overflow in {@code -n} is not a trouble,
3386 // because shiftLeft considers its argument unsigned
3401 int nBits = n & 0x1f;
3402 int magLen = mag.length;
3403 int newMag[] = null;
3404
3405 // Special case: entire contents shifted off the end
3406 if (nInts >= magLen)
3407 return (signum >= 0 ? ZERO : negConst[1]);
3408
3409 if (nBits == 0) {
3410 int newMagLen = magLen - nInts;
3411 newMag = Arrays.copyOf(mag, newMagLen);
3412 } else {
3413 int i = 0;
3414 int highBits = mag[0] >>> nBits;
3415 if (highBits != 0) {
3416 newMag = new int[magLen - nInts];
3417 newMag[i++] = highBits;
3418 } else {
3419 newMag = new int[magLen - nInts -1];
3420 }
3421 int numIter = magLen - nInts - 1;
3422 Objects.checkFromToIndex(0, numIter + 1, mag.length);
3423 Objects.checkFromToIndex(i, numIter + i, newMag.length);
3424 shiftRightImplWorker(newMag, mag, i, nBits, numIter);
3425 }
3426
3427 if (signum < 0) {
3428 // Find out whether any one-bits were shifted off the end.
3429 boolean onesLost = false;
3430 for (int i=magLen-1, j=magLen-nInts; i >= j && !onesLost; i--)
3431 onesLost = (mag[i] != 0);
3432 if (!onesLost && nBits != 0)
3433 onesLost = (mag[magLen - nInts - 1] << (32 - nBits) != 0);
3434
3435 if (onesLost)
3436 newMag = javaIncrement(newMag);
3437 }
3438
3439 return new BigInteger(newMag, signum);
3440 }
3441
3442 @ForceInline
3443 @HotSpotIntrinsicCandidate
3444 private static void shiftRightImplWorker(int[] newArr, int[] oldArr, int newIdx, int shiftCount, int numIter) {
3445 int shiftCountLeft = 32 - shiftCount;
3446 int idx = numIter;
3447 int nidx = (newIdx == 0) ? numIter - 1 : numIter;
3448 while (nidx >= newIdx) {
3449 newArr[nidx--] = (oldArr[idx--] >>> shiftCount) | (oldArr[idx] << shiftCountLeft);
3450 }
3451 }
3452
3453 int[] javaIncrement(int[] val) {
3454 int lastSum = 0;
3455 for (int i=val.length-1; i >= 0 && lastSum == 0; i--)
3456 lastSum = (val[i] += 1);
3457 if (lastSum == 0) {
3458 val = new int[val.length+1];
3459 val[0] = 1;
3460 }
3461 return val;
3462 }
3463
3464 // Bitwise Operations
3465
3466 /**
3467 * Returns a BigInteger whose value is {@code (this & val)}. (This
3468 * method returns a negative BigInteger if and only if this and val are
3469 * both negative.)
3470 *
|