java.math
Class BigInteger

java.lang.Object
  java.lang.Number
      java.math.BigInteger

All Implemented Interfaces:

Serializable, Comparable<BigInteger>

public class BigInteger
extends Number
implements Comparable<BigInteger>, Serializable

Class which represents immutable arbitrary precision integer numbers. This class provides methods for arithmetic operations and methods for the comparison of two instances.

See Also:

Serialized Form

Field Summary

(package private) BigInt	bigInt
(package private) int[]	digits The magnitude of this in the little-endian representation.
(package private) static int	EQUALS The BigInteger constant 0 used for comparison.
(package private) static int	GREATER The BigInteger constant 1 used for comparison.
(package private) static int	LESS The BigInteger constant -1 used for comparison.
(package private) static BigInteger	MINUS_ONE The BigInteger constant -1.
(package private) int	numberLength The length of this in measured in ints.
static BigInteger	ONE The BigInteger constatn 1.
(package private) int	sign The sign of this.
(package private) static BigInteger[]	SMALL_VALUES All the BigInteger numbers in the range [0,10] are cached.
static BigInteger	TEN The BigInteger constant 10.
static BigInteger	ZERO The BigInteger constant 0.

Constructor Summary

BigInteger(BigInt a)

BigInteger(byte[] val)
Constructs a new BigInteger from the given two's complement representation.

BigInteger(int signum, byte[] magnitude)
Constructs a new BigInteger instance with the given sign and the given magnitude.

BigInteger(int sign, int numberLength, int[] digits)
Constructs a number without to create new space.

BigInteger(int bitLength, int certainty, Random rnd)
Constructs a random positive BigInteger instance in the range [0, 2^(bitLength)-1] which is probably prime.

BigInteger(int sign, long value)

BigInteger(int numBits, Random rnd)
Constructs a random non-negative BigInteger instance in the range [0, 2^(numBits)-1].

BigInteger(String val)
Constructs a new BigInteger instance from the string representation.

BigInteger(String val, int radix)
Constructs a new BigInteger instance from the string representation.

Method Summary

BigInteger	abs() Returns a (new) BigInteger whose value is the absolute value of this.
BigInteger	add(BigInteger val) Returns a new BigInteger whose value is this + val.
BigInteger	and(BigInteger val) Returns a new BigInteger whose value is this & val.
BigInteger	andNot(BigInteger val) Returns a new BigInteger whose value is this & ~val.
int	bitCount() Returns the number of bits in the binary representation of this wich differ from the sign bit.
int	bitLength() Returns the number of bits of the binary representation of this without the sign bit.
BigInteger	clearBit(int n) Returns a new BigInteger which has the same binary representation as this but with the bit at position n cleared.
int	compareTo(BigInteger val) Compares this BigInteger with val.
(package private) BigInteger	copy()
(package private) void	cutOffLeadingZeroes() Decreases numberLength if there are zero high elements.
BigInteger	divide(BigInteger divisor) Returns a new BigInteger whose value is this / divisor.
BigInteger[]	divideAndRemainder(BigInteger divisor) Returns a BigInteger array which contains this / divisor at index 0 and this % divisor at index 1.
double	doubleValue() Returns this BigInteger as an double value.
boolean	equals(Object x) Returns true if x is a BigInteger instance and if this instance is equal to this BigInteger.
(package private) void	establishOldRepresentation(String caller)
BigInteger	flipBit(int n) Returns a new BigInteger which has the same binary representation as this but with the bit at position n flipped.
float	floatValue() Returns this BigInteger as an float value.
BigInteger	gcd(BigInteger val) Returns a new BigInteger whose value is greatest common divisor of this and val.
(package private) int	getFirstNonzeroDigit()
int	getLowestSetBit() Returns the position of the lowest set bit in the two's complement representation of this BigInteger.
int	hashCode() Returns a hash code for this BigInteger.
(package private) static int	inplaceAdd(int[] a, int aSize, int addend)
int	intValue() Returns this BigInteger as an int value.
(package private) boolean	isOne() Tests if this.abs() is equals to ONE
boolean	isProbablePrime(int certainty) Tests whether this BigInteger is probably prime.
long	longValue() Returns this BigInteger as an long value.
BigInteger	max(BigInteger val) Returns the maximum of this BigInteger and val.
BigInteger	min(BigInteger val) Returns the minimum of this BigInteger and val.
BigInteger	mod(BigInteger m) Returns a new BigInteger whose value is this mod m.
BigInteger	modInverse(BigInteger m) Returns a new BigInteger whose value is 1/this mod m.
BigInteger	modPow(BigInteger exponent, BigInteger m) Returns a new BigInteger whose value is this^exponent mod m.
BigInteger	multiply(BigInteger val) Returns a new BigInteger whose value is this * val.
(package private) static int	multiplyByInt(int[] res, int[] a, int aSize, int factor)
BigInteger	negate() Returns a new BigInteger whose value is the -this.
BigInteger	nextProbablePrime() Returns the smallest integer x > this which is probably prime as a BigInteger instance.
BigInteger	not() Returns a new BigInteger whose value is ~this.
BigInteger	or(BigInteger val) Returns a new BigInteger whose value is this | val.
BigInteger	pow(int exp) Returns a new BigInteger whose value is this ^ exp.
static BigInteger	probablePrime(int bitLength, Random rnd) Returns a random positive BigInteger instance in the range [0, 2^(bitLength)-1] which is probably prime.
BigInteger	remainder(BigInteger divisor) Returns a new BigInteger whose value is this % divisor.
BigInteger	setBit(int n) Returns a new BigInteger which has the same binary representation as this but with the bit at position n set.
BigInteger	shiftLeft(int n) Returns a new BigInteger whose value is this << n.
BigInteger	shiftRight(int n) Returns a new BigInteger whose value is this >> n.
int	signum() Returns the sign of this BigInteger.
BigInteger	subtract(BigInteger val) Returns a new BigInteger whose value is this - val.
boolean	testBit(int n) Tests whether the bit at position n in this is set.
byte[]	toByteArray() Returns the two's complement representation of this BigInteger in a byte array.
String	toString() Returns a string representation of this BigInteger in decimal form.
String	toString(int radix) Returns a string containing a string representation of this BigInteger with base radix.
(package private) void	unCache()
(package private) void	validate(String caller, String param)
(package private) static void	validate1(String caller, BigInteger a)
(package private) static void	validate2(String caller, BigInteger a, BigInteger b)
(package private) static void	validate3(String caller, BigInteger a, BigInteger b, BigInteger c)
(package private) static void	validate4(String caller, BigInteger a, BigInteger b, BigInteger c, BigInteger d)
static BigInteger	valueOf(long val) Creates a new BigInteger whose value is equal to the specified long argument.
(package private) BigInteger	withNewRepresentation(String caller)
BigInteger	xor(BigInteger val) Returns a new BigInteger whose value is this ^ val.

Methods inherited from class java.lang.Number

byteValue, shortValue

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

bigInt

transient BigInt bigInt

digits

transient int[] digits

The magnitude of this in the little-endian representation.

numberLength

transient int numberLength

The length of this in measured in ints. Can be less than digits.length().

sign

transient int sign

The sign of this.

ZERO

public static final BigInteger ZERO

The BigInteger constant 0.

Since:

1.2

ONE

public static final BigInteger ONE

The BigInteger constatn 1.

Since:

1.2

TEN

public static final BigInteger TEN

The BigInteger constant 10.

Since:

1.5

MINUS_ONE

static final BigInteger MINUS_ONE

The BigInteger constant -1.

EQUALS

static final int EQUALS

The BigInteger constant 0 used for comparison.

See Also:

Constant Field Values

GREATER

static final int GREATER

The BigInteger constant 1 used for comparison.

See Also:

Constant Field Values

LESS

static final int LESS

The BigInteger constant -1 used for comparison.

See Also:

Constant Field Values

SMALL_VALUES

static final BigInteger[] SMALL_VALUES

All the BigInteger numbers in the range [0,10] are cached.

Constructor Detail

BigInteger

BigInteger(BigInt a)

BigInteger

BigInteger(int sign,
           long value)

BigInteger

BigInteger(int sign,
           int numberLength,
           int[] digits)

Constructs a number without to create new space. This construct should be used only if the three fields of representation are known.

Parameters:

sign - the sign of the number

numberLength - the length of the internal array

digits - a reference of some array created before

BigInteger

public BigInteger(int numBits,
                  Random rnd)

Constructs a random non-negative BigInteger instance in the range [0, 2^(numBits)-1].

Parameters:

numBits - maximum lenght of the new BigInteger in bits.

rnd - random generator used to generate the new BigInteger.

Throws:

IllegalArgumentException - if numBits < 0

BigInteger

public BigInteger(int bitLength,
                  int certainty,
                  Random rnd)

Constructs a random positive BigInteger instance in the range [0, 2^(bitLength)-1] which is probably prime. The probability that the returned BigInteger is prime is beyond (1-1/2^certainty).

Parameters:

bitLength - lenght of the new BigInteger in bits.

certainty - tolerated primality uncertainty.

rnd - random generator used to generate the new BigInteger.

Throws:

IllegalArgumentException - if bitLength < 2

BigInteger

public BigInteger(String val)

Constructs a new BigInteger instance from the string representation. The string representation consists of an optional minus sign followed by a non-empty sequence of decimal digits.

Parameters:

val - string representation of the new BigInteger.

Throws:

NullPointerException - if val == null.

NumberFormatException - if val is not a valid representation of a BigInteger.

BigInteger

public BigInteger(String val,
                  int radix)

Constructs a new BigInteger instance from the string representation. The string representation consists of an optional minus sign followed by a non-empty sequence of digits in the specified radix. For the conversion the method Character.digit(char, radix) is used.

Parameters:

val - string representation of the new BigInteger.

radix - the base to be used for the conversion.

Throws:

NullPointerException - if val == null

NumberFormatException - if val is not a valid representation of a BigInteger or if radix < Character.MIN_RADIX or radix > Character.MAX_RADIX.

BigInteger

public BigInteger(int signum,
                  byte[] magnitude)

Constructs a new BigInteger instance with the given sign and the given magnitude. The sign is given as an integer (-1 for negative, 0 for zero, 1 for positive). The magnitude is specified as a byte array. The most significant byte is the entry at index 0.

Parameters:

signum - sign of the new BigInteger (-1 for negative, 0 for zero, 1 for positive).

magnitude - magnitude of the new BigInteger with the most significant byte first.

Throws:

NullPointerException - if magnitude == null

NumberFormatException - if the sign is not one of -1, 0, 1 or if the sign is zero and the magnitute contains non-zero entries.

BigInteger

public BigInteger(byte[] val)

Constructs a new BigInteger from the given two's complement representation. The most significant byte is the entry at index 0. The most significant bit of this entry determines the sign of the new BigInteger instance. The given array must not be empty.

Parameters:

val - two's complement representation of the new BigInteger.

Throws:

NullPointerException - if val == null

NumberFormatException - if the lenght of val == 0.

Method Detail

establishOldRepresentation

void establishOldRepresentation(String caller)

withNewRepresentation

BigInteger withNewRepresentation(String caller)

validate

void validate(String caller,
              String param)

validate1

static void validate1(String caller,
                      BigInteger a)

validate2

static void validate2(String caller,
                      BigInteger a,
                      BigInteger b)

validate3

static void validate3(String caller,
                      BigInteger a,
                      BigInteger b,
                      BigInteger c)

validate4

static void validate4(String caller,
                      BigInteger a,
                      BigInteger b,
                      BigInteger c,
                      BigInteger d)

valueOf

public static BigInteger valueOf(long val)

Creates a new BigInteger whose value is equal to the specified long argument.

Parameters:

val - the value of the new BigInteger.

Returns:

BigInteger instance with the value val.

toByteArray

public byte[] toByteArray()

Returns the two's complement representation of this BigInteger in a byte array.

Returns:

two's complement representation of this.

abs

public BigInteger abs()

Returns a (new) BigInteger whose value is the absolute value of this.

Returns:

abs(this)

negate

public BigInteger negate()

Returns a new BigInteger whose value is the -this.

Returns:

-this.

add

public BigInteger add(BigInteger val)

Returns a new BigInteger whose value is this + val.

Parameters:

val - value to be added to this.

Returns:

this + val.

Throws:

NullPointerException - if val == null

subtract

public BigInteger subtract(BigInteger val)

Returns a new BigInteger whose value is this - val.

Parameters:

val - value to be subtracted from this.

Returns:

this - val.

Throws:

NullPointerException - if val == null

signum

public int signum()

Returns the sign of this BigInteger.

Returns:

-1 if this < 0, 0 if this == 0, 1 if this > 0.

shiftRight

public BigInteger shiftRight(int n)

Returns a new BigInteger whose value is this >> n. For negative arguments, the result is also negative. The shift distance may be negative which means that this is shifted left.

Parameters:

n - shift distance.

Returns:

this >> n if n >= 0; this << (-n) otherwise.

shiftLeft

public BigInteger shiftLeft(int n)

Returns a new BigInteger whose value is this << n. The result is equvalent to this * 2^n if n ≥ 0. The shift distance may be negative which means that this is shifted right. The result then corresponds to floor(this / 2^(-n)).

Parameters:

n - shift distance.

Returns:

this << n if n >= 0; this >> (-n) otherwise.

bitLength

public int bitLength()

Returns the number of bits of the binary representation of this without the sign bit. For positive values this is equivalent to the number of bits, and for negative values this is equivalent to the number of bits used to represent -value-1. mc: In other words: the number a can be coded in a.bitLength() + 1 bits two's complement. E.g. for a.bitLength() == 31, an int will hold a correctly and for a.bitLength() == 32 an int will NOT hold a correctly.

Returns:

number of bits of the binary representation of this without the sign bit.

testBit

public boolean testBit(int n)

Tests whether the bit at position n in this is set. The result is equivalent to this & (2^n) != 0.

Parameters:

n - position where the bit in this has to be inspected.

Returns:

this & (2^n) != 0.

Throws:

ArithmeticException - if n < 0

setBit

public BigInteger setBit(int n)

Returns a new BigInteger which has the same binary representation as this but with the bit at position n set. The result is equivalent to this | 2^n.

Parameters:

n - position where the bit in this has to be set.

Returns:

this | 2^n.

Throws:

ArithmeticException - if n < 0

clearBit

public BigInteger clearBit(int n)

Returns a new BigInteger which has the same binary representation as this but with the bit at position n cleared. The result is equivalent to this & ~(2^n).

Parameters:

n - position where the bit in this has to be cleared.

Returns:

this & ~(2^n).

Throws:

ArithmeticException - if n < 0

flipBit

public BigInteger flipBit(int n)

Returns a new BigInteger which has the same binary representation as this but with the bit at position n flipped. The result is equivalent to this ^ 2^n.

Parameters:

n - position where the bit in this has to be flipped.

Returns:

this ^ 2^n.

Throws:

ArithmeticException - if n < 0

getLowestSetBit

public int getLowestSetBit()

Returns the position of the lowest set bit in the two's complement representation of this BigInteger. If all bits are zero (this=0) then -1 is returned as result.

Returns:

position of lowest bit if this != 0, -1 otherwise.

bitCount

public int bitCount()

Returns the number of bits in the binary representation of this wich differ from the sign bit. If this is positive the result is equivalent to the number of bits set in the binary representation of this. If this is netative the result is equivalent to the number of bits set in the binary representation of -this-1.

Returns:

number of bits in the binary representation of this wich differ from the sign bit.

not

public BigInteger not()

Returns a new BigInteger whose value is ~this. The result of this operation is -this-1.

Returns:

~this.

and

public BigInteger and(BigInteger val)

Returns a new BigInteger whose value is this & val.

Parameters:

val - value to be and'ed with this.

Returns:

this & val.

Throws:

NullPointerException - if val == null

or

public BigInteger or(BigInteger val)

Returns a new BigInteger whose value is this | val.

Parameters:

val - value to be or'ed with this.

Returns:

this | val.

Throws:

NullPointerException - if val == null

xor

public BigInteger xor(BigInteger val)

Returns a new BigInteger whose value is this ^ val.

Parameters:

val - value to be xor'ed with this.

Returns:

this ^ val.

Throws:

NullPointerException - if val == null

andNot

public BigInteger andNot(BigInteger val)

Returns a new BigInteger whose value is this & ~val. Evaluating x.andNot(val) returns the same result as x.and(val.not()).

Parameters:

val - value to be not'ed and then and'ed with this.

Returns:

this & ~val.

Throws:

NullPointerException - if val == null

intValue

public int intValue()

Returns this BigInteger as an int value. If this is too big to be represented as an int, then this % 2^32 is returned.

Specified by:

intValue in class Number

Returns:

this BigInteger as an int value.

longValue

public long longValue()

Returns this BigInteger as an long value. If this is too big to be represented as an long, then this % 2^64 is returned.

Specified by:

longValue in class Number

Returns:

this BigInteger as a long value.

floatValue

public float floatValue()

Returns this BigInteger as an float value. If this is too big to be represented as an float, then Float.POSITIVE_INFINITY or Float.NEGATIVE_INFINITY is returned. Note, that not all integers x in the range [-Float.MAX_VALUE, Float.MAX_VALUE] can be represented as a float. The float representation has a mantissa of length 24. For example, 2^24+1 = 16777217 is returned as float 16777216.0.

Specified by:

floatValue in class Number

Returns:

this BigInteger as a float value.

doubleValue

public double doubleValue()

Returns this BigInteger as an double value. If this is too big to be represented as an double, then Double.POSITIVE_INFINITY or Double.NEGATIVE_INFINITY is returned. Note, that not all integers x in the range [-Dobule.MAX_VALUE, Dobule.MAX_VALUE] can be represented as a double. The double representation has a mantissa of length 53. For example, 2^53+1 = 9007199254740993 is returned as double 9007199254740992.0.

Specified by:

doubleValue in class Number

Returns:

this BigInteger as a double value.

compareTo

public int compareTo(BigInteger val)

Compares this BigInteger with val. Returns one of the three values 1, 0, or -1.

Specified by:

compareTo in interface Comparable<BigInteger>

Parameters:

val - value to be compared with this.

Returns:

1 if this > val, -1 if this < val, 0 if this == val.

Throws:

NullPointerException - if val == null

min

public BigInteger min(BigInteger val)

Returns the minimum of this BigInteger and val.

Parameters:

val - value to be used to compute the minimum with this.

Returns:

min(this, val.

Throws:

NullPointerException - if val == null

max

public BigInteger max(BigInteger val)

Returns the maximum of this BigInteger and val.

Parameters:

val - value to be used to compute the maximum with this.

Returns:

max(this, val.

Throws:

NullPointerException - if val == null

hashCode

public int hashCode()

Returns a hash code for this BigInteger.

Overrides:

hashCode in class Object

Returns:

hash code for this.

See Also:

Object.equals(java.lang.Object)

equals

public boolean equals(Object x)

Returns true if x is a BigInteger instance and if this instance is equal to this BigInteger.

Overrides:

equals in class Object

Parameters:

x - object to be compared with this.

Returns:

true if x is a BigInteger and this == x.

See Also:

Object.hashCode()

toString

public String toString()

Returns a string representation of this BigInteger in decimal form.

Overrides:

toString in class Object

Returns:

a string representation of this in decimal form.

toString

public String toString(int radix)

Returns a string containing a string representation of this BigInteger with base radix. If radix < Character.MIN_RADIX or radix > Character.MAX_RADIX then a decimal representation is returned. The characters of the string representation are generated with method Character.forDigit.

Parameters:

radix - base to be used for the string representation.

Returns:

a string representation of this with radix 10.

gcd

public BigInteger gcd(BigInteger val)

Returns a new BigInteger whose value is greatest common divisor of this and val. If this==0 and val==0 then zero is returned, otherwise the result is positive.

Parameters:

val - value with which the greatest common divisor is computed.

Returns:

gcd(this, val).

Throws:

NullPointerException - if val == null

multiply

public BigInteger multiply(BigInteger val)

Returns a new BigInteger whose value is this * val.

Parameters:

val - value to be multiplied with this.

Returns:

this * val.

Throws:

NullPointerException - if val == null

pow

public BigInteger pow(int exp)

Returns a new BigInteger whose value is this ^ exp.

Parameters:

exp - exponent to which this is raised.

Returns:

this ^ exp.

Throws:

ArithmeticException - if exp < 0

divideAndRemainder

public BigInteger[] divideAndRemainder(BigInteger divisor)

Returns a BigInteger array which contains this / divisor at index 0 and this % divisor at index 1.

Parameters:

divisor - value by which this is divided.

Returns:

[this / divisor, this % divisor].

Throws:

NullPointerException - if divisor == null

ArithmeticException - if divisor == 0

See Also:

divide(java.math.BigInteger), remainder(java.math.BigInteger)

divide

public BigInteger divide(BigInteger divisor)

Returns a new BigInteger whose value is this / divisor.

Parameters:

divisor - value by which this is divided.

Returns:

this / divisor.

Throws:

NullPointerException - if divisor == null

ArithmeticException - if divisor == 0

remainder

public BigInteger remainder(BigInteger divisor)

Returns a new BigInteger whose value is this % divisor. Regarding signs this methods has the same behavior as the % operator on int's, i.e. the sign of the remainder is the same as the sign of this.

Parameters:

divisor - value by which this is divided.

Returns:

this % divisor.

Throws:

NullPointerException - if divisor == null

ArithmeticException - if divisor == 0

modInverse

public BigInteger modInverse(BigInteger m)

Returns a new BigInteger whose value is 1/this mod m. The modulus m must be positive. The result is guaranteed to be in the interval [0, m) (0 inclusive, m exclusive). If this is not relatively prime to m, then an exception is thrown.

Parameters:

m - the modulus.

Returns:

this mod m.

Throws:

NullPointerException - if m == null

ArithmeticException - if m < 0 or if this is not relatively prime to m

modPow

public BigInteger modPow(BigInteger exponent,
                         BigInteger m)

Returns a new BigInteger whose value is this^exponent mod m. The modulus m must be positive. The result is guaranteed to be in the interval [0, m) (0 inclusive, m exclusive). If the exponent is negative, then this.modInverse(m)^(-exponent) mod m) is computed. The inverse of this only exists if this is relatively prime to m, otherwise an exception is thrown.

Parameters:

exponent - the exponent.

m - the modulus.

Returns:

this^exponent mod val.

Throws:

NullPointerException - if m == null or exponent == null

ArithmeticException - if m < 0 or if exponent<0 and this is not relatively prime to m

mod

public BigInteger mod(BigInteger m)

Returns a new BigInteger whose value is this mod m. The modulus m must be positive. The result is guaranteed to be in the interval [0, m) (0 inclusive, m exclusive). The behavior of this function is not equivalent to the behavior of the % operator defined for the built-in int's.

Parameters:

m - the modulus.

Returns:

this mod m.

Throws:

NullPointerException - if m == null

ArithmeticException - if m < 0

isProbablePrime

public boolean isProbablePrime(int certainty)

Tests whether this BigInteger is probably prime. If true is returned, then this is prime with a probability beyond (1-1/2^certainty). If false is returned, then this is definitely composite. If the argument certainty ≤ 0, then this method returns true.

Parameters:

certainty - tolerated primality uncertainty.

Returns:

ture, if this is probably prime, false otherwise.

nextProbablePrime

public BigInteger nextProbablePrime()

Returns the smallest integer x > this which is probably prime as a BigInteger instance. The probability that the returned BigInteger is prime is beyond (1-1/2^100).

Returns:

smallest integer > this pwhich is robably prime.

Throws:

ArithmeticException - if this < 0

probablePrime

public static BigInteger probablePrime(int bitLength,
                                       Random rnd)

Returns a random positive BigInteger instance in the range [0, 2^(bitLength)-1] which is probably prime. The probability that the returned BigInteger is prime is beyond (1-1/2^100).

Parameters:

bitLength - lenght of the new BigInteger in bits

rnd - random generator used to generate the new BigInteger.

Returns:

probably prime random BigInteger instance

Throws:

IllegalArgumentException - if bitLength < 2

multiplyByInt

static int multiplyByInt(int[] res,
                         int[] a,
                         int aSize,
                         int factor)

inplaceAdd

static int inplaceAdd(int[] a,
                      int aSize,
                      int addend)

cutOffLeadingZeroes

final void cutOffLeadingZeroes()

Decreases numberLength if there are zero high elements.

isOne

boolean isOne()

Tests if this.abs() is equals to ONE

getFirstNonzeroDigit

int getFirstNonzeroDigit()

copy

BigInteger copy()

unCache

void unCache()