Lines Matching defs:BigInteger
38 * primitive integer types). BigInteger provides analogues to all of Java's
40 * Additionally, BigInteger provides operations for modular arithmetic, GCD
75 * operations can produce a BigInteger with a different sign from the
76 * BigInteger being operated on, as they affect only a single bit, and the
78 * are infinitely many "virtual sign bits" preceding each BigInteger.
81 * descriptions of BigInteger methods. The pseudo-code expression
82 * {@code (i + j)} is shorthand for "a BigInteger whose value is
83 * that of the BigInteger {@code i} plus that of the BigInteger {@code j}."
85 * "{@code true} if and only if the BigInteger {@code i} represents the same
86 * value as the BigInteger {@code j}." Other pseudo-code expressions are
99 public class BigInteger extends Number implements Comparable<BigInteger> {
101 * The signum of this BigInteger: -1 for negative, 0 for zero, or
102 * 1 for positive. Note that the BigInteger zero <i>must</i> have
104 * representation for each BigInteger value.
111 * The magnitude of this BigInteger, in <i>big-endian</i> order: the
115 * ensure that there is exactly one representation for each BigInteger
116 * value. Note that this implies that the BigInteger zero has a
126 * One plus the bitCount of this BigInteger. Zeros means unitialized.
137 * One plus the bitLength of this BigInteger. Zeros means unitialized.
149 * Two plus the lowest set bit of this BigInteger, as returned by
162 * BigInteger that contains a nonzero int, or -2 (either value is acceptable).
180 * representation of a BigInteger into a BigInteger. The input array is
185 * BigInteger.
188 public BigInteger(byte[] val) {
190 throw new NumberFormatException("Zero length BigInteger");
203 * two's-complement binary representation of a BigInteger into a
204 * BigInteger. The input array is assumed to be in <i>big-endian</i>
207 private BigInteger(int[] val) {
209 throw new NumberFormatException("Zero length BigInteger");
221 * Translates the sign-magnitude representation of a BigInteger into a
222 * BigInteger. The sign is represented as an integer signum value: -1 for
226 * result in a BigInteger value of 0, whether signum is -1, 0 or 1.
236 public BigInteger(int signum, byte[] magnitude) {
253 * representation of a BigInteger into a BigInteger. It checks the
257 private BigInteger(int signum, int[] magnitude) {
273 * Translates the String representation of a BigInteger in the
274 * specified radix into a BigInteger. The String representation
281 * @param val String representation of BigInteger.
284 * of a BigInteger in the specified radix, or {@code radix} is
289 public BigInteger(String val, int radix) {
296 throw new NumberFormatException("Zero length BigInteger");
307 throw new NumberFormatException("Zero length BigInteger");
356 // Constructs a new BigInteger using a char array with radix=10
357 BigInteger(char[] val) {
365 throw new NumberFormatException("Zero length BigInteger");
370 throw new NumberFormatException("Zero length BigInteger");
463 * Translates the decimal String representation of a BigInteger into a
464 * BigInteger. The String representation consists of an optional minus
470 * @param val decimal String representation of BigInteger.
472 * of a BigInteger.
475 public BigInteger(String val) {
480 * Constructs a randomly generated BigInteger, uniformly distributed over
484 * constructs a non-negative BigInteger.
486 * @param numBits maximum bitLength of the new BigInteger.
488 * BigInteger.
492 public BigInteger(int numBits, Random rnd) {
512 * Constructs a randomly generated positive BigInteger that is probably
519 * @param bitLength bitLength of the returned BigInteger.
521 * willing to tolerate. The probability that the new BigInteger
530 public BigInteger(int bitLength, int certainty, Random rnd) {
531 BigInteger prime;
550 * Returns a positive BigInteger that is probably prime, with the
551 * specified bitLength. The probability that a BigInteger returned
554 * @param bitLength bitLength of the returned BigInteger.
557 * @return a BigInteger of {@code bitLength} bits that is probably prime
562 public static BigInteger probablePrime(int bitLength, Random rnd) {
579 private static BigInteger smallPrime(int bitLength, int certainty, Random rnd) {
593 BigInteger p = new BigInteger(temp, 1);
614 private static final BigInteger SMALL_PRIME_PRODUCT
623 private static BigInteger largePrime(int bitLength, int certainty, Random rnd) {
624 BigInteger p;
625 p = new BigInteger(bitLength, rnd).setBit(bitLength-1);
631 BigInteger candidate = searchSieve.retrieve(p, certainty, rnd);
634 p = p.add(BigInteger.valueOf(2*searchLen));
636 p = new BigInteger(bitLength, rnd).setBit(bitLength-1);
645 * Returns the first integer greater than this {@code BigInteger} that
651 * @return the first integer greater than this {@code BigInteger} that
656 public BigInteger nextProbablePrime() {
664 BigInteger result = this.add(ONE);
706 BigInteger candidate = searchSieve.retrieve(result,
710 result = result.add(BigInteger.valueOf(2 * searchLen));
715 * Returns {@code true} if this BigInteger is probably prime,
722 * the probability that this BigInteger is prime exceeds
725 * @return {@code true} if this BigInteger is probably prime,
759 * Returns true iff this BigInteger is a Lucas-Lehmer probable prime.
762 * This BigInteger is a positive, odd number.
765 BigInteger thisPlusOne = this.add(ONE);
775 BigInteger u = lucasLehmerSequence(d, thisPlusOne, this);
785 private static int jacobiSymbol(int p, BigInteger n) {
815 u = n.mod(BigInteger.valueOf(p)).intValue();
839 private static BigInteger lucasLehmerSequence(int z, BigInteger k, BigInteger n) {
840 BigInteger d = BigInteger.valueOf(z);
841 BigInteger u = ONE; BigInteger u2;
842 BigInteger v = ONE; BigInteger v2;
881 * Returns true iff this BigInteger passes the specified number of
886 * This BigInteger is a positive, odd number greater than 2.
891 BigInteger thisMinusOne = this.subtract(ONE);
892 BigInteger m = thisMinusOne;
902 BigInteger b;
904 b = new BigInteger(this.bitLength(), rnd);
908 BigInteger z = b.modPow(m, this);
923 BigInteger(int[] magnitude, int signum) {
932 private BigInteger(byte[] magnitude, int signum) {
940 * Returns a BigInteger whose value is equal to that of the
945 * @param val value of the BigInteger to return.
946 * @return a BigInteger with the specified value.
948 public static BigInteger valueOf(long val) {
957 return new BigInteger(val);
961 * Constructs a BigInteger with the specified value, which may not be zero.
963 private BigInteger(long val) {
983 * Returns a BigInteger with the given two's complement representation.
985 * BigInteger will reference the input array if feasible).
987 private static BigInteger valueOf(int val[]) {
988 return (val[0]>0 ? new BigInteger(val, 1) : new BigInteger(val));
997 private static BigInteger posConst[] = new BigInteger[MAX_CONSTANT+1];
998 private static BigInteger negConst[] = new BigInteger[MAX_CONSTANT+1];
1003 posConst[i] = new BigInteger(magnitude, 1);
1004 negConst[i] = new BigInteger(magnitude, -1);
1009 * The BigInteger constant zero.
1013 public static final BigInteger ZERO = new BigInteger(new int[0], 0);
1016 * The BigInteger constant one.
1020 public static final BigInteger ONE = valueOf(1);
1023 * The BigInteger constant two. (Not exported.)
1025 private static final BigInteger TWO = valueOf(2);
1028 * The BigInteger constant ten.
1032 public static final BigInteger TEN = valueOf(10);
1037 * Returns a BigInteger whose value is {@code (this + val)}.
1039 * @param val value to be added to this BigInteger.
1042 public BigInteger add(BigInteger val) {
1048 return new BigInteger(add(mag, val.mag), signum);
1057 return new BigInteger(resultMag, cmp == signum ? 1 : -1);
1105 * Returns a BigInteger whose value is {@code (this - val)}.
1107 * @param val value to be subtracted from this BigInteger.
1110 public BigInteger subtract(BigInteger val) {
1116 return new BigInteger(add(mag, val.mag), signum);
1124 return new BigInteger(resultMag, cmp == signum ? 1 : -1);
1160 * Returns a BigInteger whose value is {@code (this * val)}.
1162 * @param val value to be multiplied by this BigInteger.
1165 public BigInteger multiply(BigInteger val) {
1172 return new BigInteger(result, signum == val.signum ? 1 : -1);
1176 * Package private methods used by BigDecimal code to multiply a BigInteger
1179 BigInteger multiply(long v) {
1183 return multiply(BigInteger.valueOf(v));
1214 return new BigInteger(rmag, rsign);
1252 * Returns a BigInteger whose value is {@code (this<sup>2</sup>)}.
1256 private BigInteger square() {
1260 return new BigInteger(trustedStripLeadingZeroInts(z), 1);
1331 * Returns a BigInteger whose value is {@code (this / val)}.
1333 * @param val value by which this BigInteger is to be divided.
1337 public BigInteger divide(BigInteger val) {
1350 * @param val value by which this BigInteger is to be divided, and the
1357 public BigInteger[] divideAndRemainder(BigInteger val) {
1358 BigInteger[] result = new BigInteger[2];
1369 * Returns a BigInteger whose value is {@code (this % val)}.
1371 * @param val value by which this BigInteger is to be divided, and the
1376 public BigInteger remainder(BigInteger val) {
1385 * Returns a BigInteger whose value is <tt>(this<sup>exponent</sup>)</tt>.
1386 * Note that {@code exponent} is an integer rather than a BigInteger.
1388 * @param exponent exponent to which this BigInteger is to be raised.
1393 public BigInteger pow(int exponent) {
1415 return new BigInteger(result, newSign);
1419 * Returns a BigInteger whose value is the greatest common divisor of
1426 public BigInteger gcd(BigInteger val) {
1513 * Returns a BigInteger whose value is the absolute value of this
1514 * BigInteger.
1518 public BigInteger abs() {
1523 * Returns a BigInteger whose value is {@code (-this)}.
1527 public BigInteger negate() {
1528 return new BigInteger(this.mag, -this.signum);
1532 * Returns the signum function of this BigInteger.
1534 * @return -1, 0 or 1 as the value of this BigInteger is negative, zero or
1544 * Returns a BigInteger whose value is {@code (this mod m}). This method
1546 * <i>non-negative</i> BigInteger.
1553 public BigInteger mod(BigInteger m) {
1555 throw new ArithmeticException("BigInteger: modulus not positive");
1557 BigInteger result = this.remainder(m);
1562 * Returns a BigInteger whose value is
1570 * negative and this BigInteger is not <i>relatively
1574 public BigInteger modPow(BigInteger exponent, BigInteger m) {
1576 throw new ArithmeticException("BigInteger: modulus not positive");
1595 BigInteger base = (this.signum < 0 || this.compareTo(m) >= 0
1597 BigInteger result;
1610 BigInteger m1 = m.shiftRight(p); // m/2**p
1611 BigInteger m2 = ONE.shiftLeft(p); // 2**p
1614 BigInteger base2 = (this.signum < 0 || this.compareTo(m1) >= 0
1618 BigInteger a1 = (m1.equals(ONE) ? ZERO :
1622 BigInteger a2 = base.modPow2(exponent, p);
1625 BigInteger y1 = m2.modInverse(m1);
1626 BigInteger y2 = m1.modInverse(m2);
1639 * Returns a BigInteger whose value is x to the power of y mod z.
1642 private BigInteger oddModPow(BigInteger y, BigInteger z) {
1866 return new BigInteger(1, t2);
1967 * Returns a BigInteger whose value is (this ** exponent) mod (2**p)
1969 private BigInteger modPow2(BigInteger exponent, int p) {
1974 BigInteger result = valueOf(1);
1975 BigInteger baseToPow2 = this.mod2(p);
1995 * Returns a BigInteger whose value is this mod(2**p).
1996 * Assumes that this {@code BigInteger >= 0} and {@code p > 0}.
1998 private BigInteger mod2(int p) {
2012 return (mag[0]==0 ? new BigInteger(1, mag) : new BigInteger(mag, 1));
2016 * Returns a BigInteger whose value is {@code (this}<sup>-1</sup> {@code mod m)}.
2020 * @throws ArithmeticException {@code m} ≤ 0, or this BigInteger
2021 * has no multiplicative inverse mod m (that is, this BigInteger
2024 public BigInteger modInverse(BigInteger m) {
2026 throw new ArithmeticException("BigInteger: modulus not positive");
2032 BigInteger modVal = this;
2049 * Returns a BigInteger whose value is {@code (this << n)}.
2060 public BigInteger shiftLeft(int n) {
2098 return new BigInteger(newMag, signum);
2102 * Returns a BigInteger whose value is {@code (this >> n)}. Sign
2113 public BigInteger shiftRight(int n) {
2166 return new BigInteger(newMag, signum);
2183 * Returns a BigInteger whose value is {@code (this & val)}. (This
2184 * method returns a negative BigInteger if and only if this and val are
2187 * @param val value to be AND'ed with this BigInteger.
2190 public BigInteger and(BigInteger val) {
2200 * Returns a BigInteger whose value is {@code (this | val)}. (This method
2201 * returns a negative BigInteger if and only if either this or val is
2204 * @param val value to be OR'ed with this BigInteger.
2207 public BigInteger or(BigInteger val) {
2217 * Returns a BigInteger whose value is {@code (this ^ val)}. (This method
2218 * returns a negative BigInteger if and only if exactly one of this and
2221 * @param val value to be XOR'ed with this BigInteger.
2224 public BigInteger xor(BigInteger val) {
2234 * Returns a BigInteger whose value is {@code (~this)}. (This method
2235 * returns a negative value if and only if this BigInteger is
2240 public BigInteger not() {
2249 * Returns a BigInteger whose value is {@code (this & ~val)}. This
2252 * BigInteger if and only if {@code this} is negative and {@code val} is
2255 * @param val value to be complemented and AND'ed with this BigInteger.
2258 public BigInteger andNot(BigInteger val) {
2286 * Returns a BigInteger whose value is equivalent to this BigInteger
2293 public BigInteger setBit(int n) {
2309 * Returns a BigInteger whose value is equivalent to this BigInteger
2317 public BigInteger clearBit(int n) {
2333 * Returns a BigInteger whose value is equivalent to this BigInteger
2341 public BigInteger flipBit(int n) {
2358 * BigInteger (the number of zero bits to the right of the rightmost
2359 * one bit). Returns -1 if this BigInteger contains no one bits.
2362 * @return index of the rightmost one bit in this BigInteger.
2387 * representation of this BigInteger, <i>excluding</i> a sign bit.
2393 * representation of this BigInteger, <i>excluding</i> a sign bit.
2423 * of this BigInteger that differ from its sign bit. This method is
2427 * of this BigInteger that differ from its sign bit.
2452 * Returns {@code true} if this BigInteger is probably prime,
2459 * the probability that this BigInteger is prime exceeds
2462 * @return {@code true} if this BigInteger is probably prime,
2468 BigInteger w = this.abs();
2480 * Compares this BigInteger with the specified BigInteger. This
2488 * @param val BigInteger to which this BigInteger is to be compared.
2489 * @return -1, 0 or 1 as this BigInteger is numerically less than, equal
2492 public int compareTo(BigInteger val) {
2507 * Compares the magnitude array of this BigInteger with the specified
2508 * BigInteger's. This is the version of compareTo ignoring sign.
2510 * @param val BigInteger whose magnitude array to be compared.
2512 * greater than the magnitude aray for the specified BigInteger's.
2514 final int compareMagnitude(BigInteger val) {
2533 * Compares this BigInteger with the specified Object for equality.
2535 * @param x Object to which this BigInteger is to be compared.
2537 * BigInteger whose value is numerically equal to this BigInteger.
2544 if (!(x instanceof BigInteger))
2547 BigInteger xInt = (BigInteger) x;
2565 * Returns the minimum of this BigInteger and {@code val}.
2568 * @return the BigInteger whose value is the lesser of this BigInteger and
2571 public BigInteger min(BigInteger val) {
2576 * Returns the maximum of this BigInteger and {@code val}.
2579 * @return the BigInteger whose value is the greater of this and
2582 public BigInteger max(BigInteger val) {
2590 * Returns the hash code for this BigInteger.
2592 * @return hash code for this BigInteger.
2604 * Returns the String representation of this BigInteger in the
2611 * compatible with the {@link #BigInteger(String, int) (String,
2615 * @return String representation of this BigInteger in the given radix.
2618 * @see #BigInteger(java.lang.String, int)
2631 BigInteger tmp = this.abs();
2634 BigInteger d = longRadix[radix];
2640 BigInteger q2 = q.toBigInteger(tmp.signum * d.signum);
2641 BigInteger r2 = r.toBigInteger(tmp.signum * d.signum);
2674 * Returns the decimal String representation of this BigInteger.
2678 * with the {@link #BigInteger(String) (String)} constructor, and
2681 * @return decimal String representation of this BigInteger.
2683 * @see #BigInteger(java.lang.String)
2691 * representation of this BigInteger. The byte array will be in
2694 * of bytes required to represent this BigInteger, including at
2697 * {@link #BigInteger(byte[]) (byte[])} constructor.)
2700 * this BigInteger.
2701 * @see #BigInteger(byte[])
2721 * Converts this BigInteger to an {@code int}. This
2726 * if this BigInteger is too big to fit in an
2729 * overall magnitude of the BigInteger value as well as return a
2732 * @return this BigInteger converted to an {@code int}.
2741 * Converts this BigInteger to a {@code long}. This
2746 * if this BigInteger is too big to fit in a
2749 * overall magnitude of the BigInteger value as well as return a
2752 * @return this BigInteger converted to a {@code long}.
2763 * Converts this BigInteger to a {@code float}. This
2768 * if this BigInteger has too great a magnitude
2773 * information about the precision of the BigInteger value.
2775 * @return this BigInteger converted to a {@code float}.
2783 * Converts this BigInteger to a {@code double}. This
2788 * if this BigInteger has too great a magnitude
2793 * information about the precision of the BigInteger value.
2795 * @return this BigInteger converted to a {@code double}.
2947 private static BigInteger longRadix[] = {null, null,
3050 * Serializable fields for BigInteger.
3053 * signum of this BigInteger.
3055 * magnitude array of this BigInteger.
3057 * number of bits in this BigInteger
3060 * representation of this BigInteger
3074 * Reconstitute the {@code BigInteger} instance from a stream (that is,
3089 * the magnitude of a BigInteger is serialized as an array of bytes.
3104 String message = "BigInteger: Invalid signum value";
3106 message = "BigInteger: Signum not present in stream";
3110 String message = "BigInteger: signum-magnitude mismatch";
3112 message = "BigInteger: Magnitude not present in stream";
3131 (BigInteger.class.getDeclaredField("signum"));
3133 (BigInteger.class.getDeclaredField("mag"));
3140 * Save the {@code BigInteger} instance to a stream.
3141 * The magnitude of a BigInteger is serialized as a byte array for