Immutable arbitrary-precision integers. All operations behave as if
BigIntegers were represented in two's-complement notation (like Java's
primitive integer types). BigIntegers provide analogues to all of Java's
primitive integer operators, and all relevant static methods from
java.lang.Math. Additionally, BigIntegers provide operations for modular
arithmetic, GCD calculation, primality testing, prime generation,
single-bit manipulation, and a few other odds and ends.
Semantics of arithmetic operations exactly mimic those of java's integer
arithmetic operators, as defined in The Java Language Specification. For
example, division by zero throws an ArithmeticException, and division of
a negative by a positive yields a negative (or zero) remainder. All of
the details in the Spec concerning overflow are ignored, as BigIntegers
are made as large as necessary to accommodate the results of an operation.
Semantics of shift operations extend those of Java's shift operators
to allow for negative shift distances. A right-shift with a negative
shift distance results in a left shift, and vice-versa. The unsigned
right shift operator (>>>) is omitted, as this operation makes little
sense in combination with the "infinite word size" abstraction provided
by this class.
Semantics of bitwise logical operations are are exactly mimic those of
Java's bitwise integer operators. The Binary operators (and, or, xor)
implicitly perform sign extension on the shorter of the two operands
prior to performing the operation.
Comparison operations perform signed integer comparisons, analogous to
those performed by java's relational and equality operators.
Modular arithmetic operations are provided to compute residues, perform
exponentiation, and compute multiplicative inverses. These methods always
return a non-negative result, between 0 and (modulus - 1), inclusive.
Single-bit operations operate on a single bit of the two's-complement
representation of their operand. If necessary, the operand is sign
extended so that it contains the designated bit. None of the single-bit
operations can produce a number with a different sign from the the
BigInteger being operated on, as they affect only a single bit, and the
"infinite word size" abstraction provided by this class ensures that there
are infinitely many "virtual sign bits" preceding each BigInteger.
Returns the number of bits in the minimal two's-complement
representation of this number, *excluding* a sign bit, i.e.,
(ceil(log2(this < 0 ? -this : this + 1))).
Translates a byte array containing the two's-complement representation
of a (signed) integer into a BigInteger. The input array is assumed to
be big-endian (i.e., the most significant byte is in the [0] position).
(The most significant bit of the most significant byte is the sign bit.)
The array must contain at least one byte or a NumberFormatException
will be thrown.
BigInteger
public BigInteger(int signum,
byte magnitude[]) throws NumberFormatException
Translates the sign-magnitude representation of an integer into a
BigInteger. The sign is represented as an integer signum value (-1 for
negative, 0 for zero, 1 for positive). The magnitude is represented
as a big-endian byte array (i.e., the most significant byte is in the
[0] position). An invalid signum value or a 0 signum value coupled
with a nonzero magnitude will result in a NumberFormatException.
A zero length magnitude array is permissible, and will result in
in a value of 0 (irrespective of the given signum value).
Translates a string containing an optional minus sign followed by a
sequence of one or more digits in the specified radix into a BigInteger.
The character-to-digit mapping is provided by Character.digit.
Any extraneous characters (including whitespace), or a radix outside
the range from Character.MIN_RADIX(2) to Character.MAX_RADIX(36),
inclusive, will result in a NumberFormatException.
Translates a string containing an optional minus sign followed by a
sequence of one or more decimal digits into a BigInteger. The
character-to-digit mapping is provided by Character.digit.
Any extraneous characters (including whitespace) will result in a
NumberFormatException.
Returns a random number uniformly distributed on [0, 2**numBits - 1]
(assuming a fair source of random bits is provided in rndSrc).
Note that this constructor always returns a non-negative BigInteger.
Throws an IllegalArgumentException if numBits < 0.
BigInteger
public BigInteger(int bitLength,
int certainty,
Random rnd)
Returns a randomly selected BigInteger with the specified bitLength
that is probably prime. The certainty parameter is a measure of
the uncertainty that the caller is willing to tolerate: the probability
that the number is prime will exceed 1 - 1/2**certainty. The execution
time is proportional to the value of the certainty parameter. The
given random number generator is used to select candidates to be
tested for primality. Throws an ArithmeticException if bitLength < 2.
Returns a BigInteger with the specified value. This factory is provided
in preference to a (long) constructor because it allows for reuse
of frequently used BigIntegers (like 0 and 1), obviating the need for
exported constants.
Returns an array of two BigIntegers. The first ([0]) element of
the return value is the quotient (this / val), and the second ([1])
element is the remainder (this % val). Throws an ArithmeticException
if val == 0.
Returns a BigInteger whose value is (this ** exponent). Throws
an ArithmeticException if exponent < 0 (as the operation would yield
a non-integer value). Note that exponent is an integer rather than
a BigInteger.
Returns a BigInteger whose value is (this ** exponent) mod m. (If
exponent == 1, the returned value is (this mod m). If exponent < 0,
the returned value is the modular multiplicative inverse of
(this ** -exponent).) Throws an ArithmeticException if m <= 0.
Returns modular multiplicative inverse of this, mod m. Throws an
ArithmeticException if m <= 0 or this has no multiplicative inverse
mod m (i.e., gcd(this, m) != 1).
Returns a BigInteger whose value is (this & ~val). This method,
which is equivalent to and(val.not()), is provided as a convenience
for masking operations. (This method returns a negative number iff
this is negative and val is positive.)
Returns the index of the rightmost (lowest-order) one bit in this
number (i.e., the number of zero bits to the right of the rightmost
one bit). Returns -1 if this number contains no one bits.
(Computes (this==0? -1 : log2(this & -this)).)
Returns the number of bits in the minimal two's-complement
representation of this number, *excluding* a sign bit, i.e.,
(ceil(log2(this < 0 ? -this : this + 1))). (For positive
numbers, this is equivalent to the number of bits in the
ordinary binary representation.)
Returns the number of bits in the two's complement representation
of this number that differ from its sign bit. This method is
useful when implementing bit-vector style sets atop BigIntegers.
isProbablePrime
public boolean isProbablePrime(int certainty)
Returns true if this BigInteger is probably prime, false if it's
definitely composite. The certainty parameter is a measure
of the uncertainty that the caller is willing to tolerate:
the method returns true if the probability that this number is
is prime exceeds 1 - 1/2**certainty. The execution time is
proportional to the value of the certainty parameter.
Returns -1, 0 or 1 as this number is less than, equal to, or
greater than val. This method is provided in preference to
individual methods for each of the six boolean comparison operators
(<, ==, >, >=, !=, <=). The suggested idiom for performing these
comparisons is: (x.compareTo(y) 0), where is one of the
six comparison operators.
Returns the string representation of this number in the given radix.
If the radix is outside the range from Character.MIN_RADIX(2) to
Character.MAX_RADIX(36) inclusive, it will default to 10 (as is the
case for Integer.toString). The digit-to-character mapping provided
by Character.forDigit is used, and a minus sign is prepended if
appropriate. (This representation is compatible with the (String, int)
constructor.)
Returns the string representation of this number, radix 10. The
digit-to-character mapping provided by Character.forDigit is used,
and a minus sign is prepended if appropriate. (This representation
is compatible with the (String) constructor, and allows for string
concatenation with Java's + operator.)
Returns the two's-complement representation of this number. The array
is big-endian (i.e., the most significant byte is in the [0] position).
The array contains the minimum number of bytes required to represent
the number (ceil((this.bitLength() + 1)/8)). (This representation is
compatible with the (byte[]) constructor.)
Converts this number to a float. Similar to the double-to-float
narrowing primitive conversion defined in The Java Language
Specification: if the number has too great a magnitude to represent
as a float, it will be converted to infinity or negative infinity,
as appropriate.
Converts the number to a double. Similar to the double-to-float
narrowing primitive conversion defined in The Java Language
Specification: if the number has too great a magnitude to represent
as a double, it will be converted to infinity or negative infinity,
as appropriate.