OpenJDK 27 · java.math.MutableBigInteger · APIdia, the JavaDoc alternative

Modifier and Type	Field and Description
pack-priv int	intLen The number of ints of the value array that are currently used to hold the magnitude of this MutableBigInteger.
pack-priv static final int	KNUTH_POW2_THRESH_LEN The minimum `intLen` for cancelling powers of two before dividing.
pack-priv static final int	KNUTH_POW2_THRESH_ZEROS The minimum number of trailing zero ints for cancelling powers of two before dividing.
pack-priv int	offset The offset into the value array where the magnitude of this MutableBigInteger begins.
pack-priv static final MutableBigInteger	ONE MutableBigInteger with one element value array with the value 1.
pack-priv int[]	value Holds the magnitude of this MutableBigInteger in big endian order.

Access	Constructor and Description
pack-priv	MutableBigInteger() The default constructor.
pack-priv	MutableBigInteger(int val) Construct a new MutableBigInteger with a magnitude specified by the int val.
pack-priv	MutableBigInteger(long val) Construct a new MutableBigInteger with a magnitude specified by the long val.
pack-priv	MutableBigInteger(int[] val) Construct a new MutableBigInteger with the specified value array up to the length of the array supplied.
pack-priv	MutableBigInteger(BigInteger b) Construct a new MutableBigInteger with a magnitude equal to the specified BigInteger.
pack-priv	MutableBigInteger(MutableBigInteger val) Construct a new MutableBigInteger with a magnitude equal to the specified MutableBigInteger.

Method Summary

Modifier and Type	Method and Description
pack-priv void	add(MutableBigInteger addend) Adds the contents of two MutableBigInteger objects.The result is placed within this MutableBigInteger.
pack-priv void	addDisjoint(MutableBigInteger addend, int n) Like `addShifted(MutableBigInteger, int)` but `this.intLen` must not be greater than `n`.
pack-priv void	addLower(MutableBigInteger addend, int n) Adds the low `n` ints of `addend`.
pack-priv void	addShifted(MutableBigInteger addend, int n) Adds the value of `addend` shifted `n` ints to the left.
private MutableBigInteger	binaryGCD(MutableBigInteger v) Calculate GCD of this and v. Assumes that this and v are not zero.
pack-priv static int	binaryGcd(int a, int b) Calculate GCD of a and b interpreted as unsigned integers.
pack-priv long	bitLength()
pack-priv void	clear() Clear out a MutableBigInteger for reuse.
pack-priv final int	compare(MutableBigInteger b) Compare the magnitude of two MutableBigIntegers.
pack-priv final int	compareHalf(MutableBigInteger b) Compare this against half of a MutableBigInteger object (Needed for remainder tests).
private int	compareShifted(MutableBigInteger b, int ints) Returns a value equal to what `b.leftShift(32*ints); return compare(b);` would return, but doesn't change the value of `b`.
pack-priv void	copyValue(MutableBigInteger src) Sets this MutableBigInteger's value array to a copy of the specified array.
pack-priv void	copyValue(int[] val) Sets this MutableBigInteger's value array to a copy of the specified array.
private int	difference(MutableBigInteger b) Subtracts the smaller of a and b from the larger and places the result into the larger.
private int	divadd(int[] a, int[] result, int offset) A primitive used for division.
private int	divaddLong(int dh, int dl, int[] result, int offset) A primitive used for division by long.
pack-priv MutableBigInteger	divide(MutableBigInteger b, MutableBigInteger quotient) Calculates the quotient of this div b and places the quotient in the provided MutableBigInteger objects and the remainder object is returned.
pack-priv MutableBigInteger	divide(MutableBigInteger b, MutableBigInteger quotient, boolean needRemainder)
pack-priv long	Returns: the remainder of the division will be returned. divide(long v, MutableBigInteger quotient) Internally used to calculate the quotient of this div v and places the quotient in the provided MutableBigInteger object and the remainder is returned.
private MutableBigInteger	Returns: `this%b` divide2n1n(MutableBigInteger a positive number such that `b.bitLength()` is even b, MutableBigInteger output parameter for `this/b` quotient) This method implements algorithm 1 from pg.
private MutableBigInteger	Returns: `this%b` divide3n2n(MutableBigInteger b, MutableBigInteger output parameter for `this/b` quotient) This method implements algorithm 2 from pg.
pack-priv MutableBigInteger	Returns: the remainder divideAndRemainderBurnikelZiegler(MutableBigInteger the divisor b, MutableBigInteger output parameter for `this/b` quotient) Computes `this/b` and `this%b` using the Burnikel-Ziegler algorithm.
pack-priv MutableBigInteger	divideKnuth(MutableBigInteger b, MutableBigInteger quotient)
pack-priv MutableBigInteger	divideKnuth(MutableBigInteger b, MutableBigInteger quotient, boolean needRemainder) Calculates the quotient of this div b and places the quotient in the provided MutableBigInteger objects and the remainder object is returned.
private MutableBigInteger	divideLongMagnitude(long ldivisor, MutableBigInteger quotient) Divide this MutableBigInteger by the divisor represented by positive long value.
private MutableBigInteger	divideMagnitude(MutableBigInteger div, MutableBigInteger quotient, boolean needRemainder) Divide this MutableBigInteger by the divisor.
pack-priv int	Returns: the remainder of the division is returned. divideOneWord(int divisor, MutableBigInteger quotient) This method is used for division of an n word dividend by a one word divisor.
private final void	ensureCapacity(int len) If this MutableBigInteger cannot hold len words, increase the size of the value array to len words.
pack-priv MutableBigInteger	euclidModInverse(int k) Uses the extended Euclidean algorithm to compute the modInverse of base mod a modulus that is a power of 2.
pack-priv static MutableBigInteger	fixup(MutableBigInteger c, MutableBigInteger p, int k) The Fixup Algorithm Calculates X such that X = C * 2^(-k) (mod P) Assumes C
private MutableBigInteger	getBlock(int the block index index, int the total number of blocks in `this` number numBlocks, int length of one block in units of 32 bits blockLength) Returns a `MutableBigInteger` containing `blockLength` ints from `this` number, starting at `index*blockLength`.
private MutableBigInteger	Returns: a `MutableBigInteger` obtained by taking `blockLen` ints from `this` number, ending at `blockIndexblockLen` (exclusive). getBlockForSqrt(int the block index, starting from the lowest blockIndex, int the logical length of the input value in units of 32 bits len, int the length of the block in units of 32 bits blockLen) Returns a `MutableBigInteger` obtained by taking `blockLen` ints from `this` number, ending at `blockIndexblockLen` (exclusive).
private final int	getInt(int index) Return the int in use in this MutableBigInteger at the specified index.
private final long	getLong(int index) Return a long which is equal to the unsigned value of the int in use in this MutableBigInteger at the specified index.
private BigInteger	getLower(int n) Returns a `BigInteger` equal to the `n` low ints of this number.
private final int	getLowestSetBit() Return the index of the lowest set bit in this MutableBigInteger.
private int[]	getMagnitudeArray() Internal helper method to return the magnitude array.
pack-priv MutableBigInteger	hybridGCD(MutableBigInteger b) Calculate GCD of this and b.
private void	init(int val)
pack-priv static int	inverseMod32(int val) Returns the multiplicative inverse of val mod 2^32.
pack-priv static long	inverseMod64(long val) Returns the multiplicative inverse of val mod 2^64.
pack-priv boolean	isEven() Returns true iff this MutableBigInteger is even.
pack-priv boolean	isNormal() Returns true iff this MutableBigInteger is in normal form.
pack-priv boolean	isOdd() Returns true iff this MutableBigInteger is odd.
pack-priv boolean	isOne() Returns true iff this MutableBigInteger has a value of one.
pack-priv boolean	isZero() Returns true iff this MutableBigInteger has a value of zero.
private void	keepLower(int n) Discards all ints whose index is greater than `n`.
pack-priv void	leftShift(int n) Left shift this MutableBigInteger n bits.
private MutableBigInteger	modInverse(MutableBigInteger mod) Calculate the multiplicative inverse of this modulo mod, where the mod argument is odd.
pack-priv static MutableBigInteger	modInverseBP2(MutableBigInteger mod, int k) Calculate the multiplicative inverse of 2^k mod mod, where mod is odd.
pack-priv MutableBigInteger	modInverseMP2(int k)
pack-priv void	mul(int y, MutableBigInteger z) Multiply the contents of this MutableBigInteger by the word y.
private int	mulsub(int[] q, int[] a, int x, int len, int offset) This method is used for division.
private int	mulsubBorrow(int[] q, int[] a, int x, int len, int offset) The method is the same as mulsun, except the fact that q array is not updated, the only result of the method is borrow flag.
private int	mulsubLong(int[] q, int dh, int dl, int x, int offset) This method is used for division by long.
pack-priv void	multiply(MutableBigInteger y, MutableBigInteger z) Multiply the contents of two MutableBigInteger objects.
pack-priv MutableBigInteger	mutableModInverse(MutableBigInteger p) Returns the modInverse of this mod p.
private static void	newtonRecurrenceRootn(MutableBigInteger x, MutableBigInteger s, int n, BigInteger sToN1) Computes `((n-1)*s + x/sToN1)/n` and places the result in `s`.
pack-priv final void	normalize() Ensure that the MutableBigInteger is in normal form, specifically making sure that there are no leading zeros, and that if the magnitude is zero, then intLen is zero.
private void	ones(int number of ints in the `value` array n) Makes this number an `n`-int number all of whose bits are ones.
private void	primitiveLeftShift(int n) Left shift this MutableBigInteger n bits, where n is less than 32.
private void	primitiveLeftShift(int n, int[] result, int resFrom) Left shift this MutableBigInteger n bits, where n is less than 32, placing the result in the specified array.
private void	primitiveRightShift(int n) Right shift this MutableBigInteger n bits, where n is less than 32.
private void	primitiveRightShift(int n, int[] result, int resFrom) Right shift this MutableBigInteger n bits, where n is less than 32, placing the result in the specified array.
pack-priv void	reset() Set a MutableBigInteger to zero, removing its offset.
pack-priv void	rightShift(int n) Right shift this MutableBigInteger n bits.
private static double	rootnApprox(double x, int n)
pack-priv MutableBigInteger[]	Returns: the integer `n`th root of `this` and the remainder rootnRem(int the root degree n) Calculate the integer `n`th root `floor(nthRoot(this, n))` and the remainder, where `nthRoot(., n)` denotes the mathematical `n`th root.
pack-priv void	safeLeftShift(int n) Like `leftShift(int)` but `n` can be zero.
pack-priv void	safeRightShift(int n) Like `rightShift(int)` but `n` can be greater than the length of the number.
pack-priv void	setInt(int index, int val) Sets the int at index+offset in this MutableBigInteger to val.
pack-priv void	setValue(int[] val, int length) Sets this MutableBigInteger's value array to the specified array.
pack-priv void	shiftAdd(MutableBigInteger addend, int n) Shifts `this` of `n` ints to the left and adds `addend`.
pack-priv void	shiftAddDisjoint(MutableBigInteger addend, int n) Shifts `this` of `n` ints to the left and adds `addend`.
pack-priv MutableBigInteger[]	Returns: the integer square root of `this` and the remainder if needed sqrtRem(boolean needRemainder) Calculate the integer square root `floor(sqrt(this))` and the remainder if needed, where `sqrt(.)` denotes the mathematical square root.
private MutableBigInteger[]	sqrtRemKaratsuba(int len, boolean needRemainder) Assumes `2 <= len <= intLen && len % 2 == 0 && Integer.numberOfLeadingZeros(value[offset]) <= 1`
pack-priv int	subtract(MutableBigInteger b) Subtracts the smaller of this and b from the larger and places the result into this MutableBigInteger.
pack-priv BigDecimal	toBigDecimal(int sign, int scale) Convert this MutableBigInteger to BigDecimal object with the specified sign and scale.
pack-priv BigInteger	toBigInteger(int sign) Convert this MutableBigInteger to a BigInteger object.
pack-priv BigInteger	toBigInteger() Converts this number to a nonnegative `BigInteger`.
pack-priv long	toCompactValue(int sign) This is for internal use in converting from a MutableBigInteger object into a long value given a specified sign.
pack-priv int[]	toIntArray() Convert this MutableBigInteger into an int array with no leading zeros, of a length that is equal to this MutableBigInteger's intLen.
private long	toLong() Convert this MutableBigInteger to a long value.
public String	toString() Overrides java.lang.Object.toString. Returns a String representation of this MutableBigInteger in radix 10.
private boolean	unsignedLongCompare(long one, long two) Compare two longs as if they were unsigned.
private static long	unsignedLongSqrt(long x)

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll wait wait wait

intLen	back to summary
pack-priv int intLen The number of ints of the value array that are currently used to hold the magnitude of this MutableBigInteger. The magnitude starts at an offset and offset + intLen may be less than value.length.

KNUTH_POW2_THRESH_LEN	back to summary
pack-priv static final int KNUTH_POW2_THRESH_LEN The minimum `intLen` for cancelling powers of two before dividing. If the number of ints is less than this threshold, `divideKnuth` does not eliminate common powers of two from the dividend and divisor.

KNUTH_POW2_THRESH_ZEROS	back to summary
pack-priv static final int KNUTH_POW2_THRESH_ZEROS The minimum number of trailing zero ints for cancelling powers of two before dividing. If the dividend and divisor don't share at least this many zero ints at the end, `divideKnuth` does not eliminate common powers of two from the dividend and divisor.

offset	back to summary
pack-priv int offset The offset into the value array where the magnitude of this MutableBigInteger begins.

ONE	back to summary
pack-priv static final MutableBigInteger ONE MutableBigInteger with one element value array with the value 1. Used by BigDecimal divideAndRound to increment the quotient. Use this constant only when the method is not going to modify this object.

value	back to summary
pack-priv int[] value Holds the magnitude of this MutableBigInteger in big endian order. The magnitude may start at an offset into the value array, and it may end before the length of the value array.

MutableBigInteger	back to summary
pack-priv MutableBigInteger() The default constructor. An empty MutableBigInteger is created with a one word capacity.

MutableBigInteger	back to summary
pack-priv MutableBigInteger(int val) Construct a new MutableBigInteger with a magnitude specified by the int val.

MutableBigInteger	back to summary
pack-priv MutableBigInteger(long val) Construct a new MutableBigInteger with a magnitude specified by the long val.

MutableBigInteger	back to summary
pack-priv MutableBigInteger(int[] val) Construct a new MutableBigInteger with the specified value array up to the length of the array supplied.

MutableBigInteger	back to summary
pack-priv MutableBigInteger(BigInteger b) Construct a new MutableBigInteger with a magnitude equal to the specified BigInteger.

MutableBigInteger	back to summary
pack-priv MutableBigInteger(MutableBigInteger val) Construct a new MutableBigInteger with a magnitude equal to the specified MutableBigInteger.

Method Detail

add	back to summary
pack-priv void add(MutableBigInteger addend) Adds the contents of two MutableBigInteger objects.The result is placed within this MutableBigInteger. The contents of the addend are not changed.

addDisjoint	back to summary
pack-priv void addDisjoint(MutableBigInteger addend, int n) Like `addShifted(MutableBigInteger, int)` but `this.intLen` must not be greater than `n`. In other words, concatenates `this` and `addend`.

addLower	back to summary
pack-priv void addLower(MutableBigInteger addend, int n) Adds the low `n` ints of `addend`.

addShifted	back to summary
pack-priv void addShifted(MutableBigInteger addend, int n) Adds the value of `addend` shifted `n` ints to the left. Has the same effect as `addend.leftShift(32*ints); add(addend);` but doesn't change the value of `addend`.

binaryGCD	back to summary
private MutableBigInteger binaryGCD(MutableBigInteger v) Calculate GCD of this and v. Assumes that this and v are not zero.

binaryGcd	back to summary
pack-priv static int binaryGcd(int a, int b) Calculate GCD of a and b interpreted as unsigned integers.

bitLength	back to summary
pack-priv long bitLength() See Also `BigInteger#bitLength()`

clear	back to summary
pack-priv void clear() Clear out a MutableBigInteger for reuse.

compare	back to summary
pack-priv final int compare(MutableBigInteger b) Compare the magnitude of two MutableBigIntegers. Returns -1, 0 or 1 as this MutableBigInteger is numerically less than, equal to, or greater than `b`. Assumes no leading unnecessary zeros.

compareHalf	back to summary
pack-priv final int compareHalf(MutableBigInteger b) Compare this against half of a MutableBigInteger object (Needed for remainder tests). Assumes no leading unnecessary zeros, which holds for results from divide().

compareShifted	back to summary
private int compareShifted(MutableBigInteger b, int ints) Returns a value equal to what `b.leftShift(32*ints); return compare(b);` would return, but doesn't change the value of `b`. Assumes no leading unnecessary zeros.

copyValue	back to summary
pack-priv void copyValue(MutableBigInteger src) Sets this MutableBigInteger's value array to a copy of the specified array. The intLen is set to the length of the new array.

copyValue	back to summary
pack-priv void copyValue(int[] val) Sets this MutableBigInteger's value array to a copy of the specified array. The intLen is set to the length of the specified array.

difference	back to summary
private int difference(MutableBigInteger b) Subtracts the smaller of a and b from the larger and places the result into the larger. Returns 1 if the answer is in a, -1 if in b, 0 if no operation was performed.

divadd	back to summary
private int divadd(int[] a, int[] result, int offset) A primitive used for division. This method adds in one multiple of the divisor a back to the dividend result at a specified offset. It is used when qhat was estimated too large, and must be adjusted.

divaddLong	back to summary
private int divaddLong(int dh, int dl, int[] result, int offset) A primitive used for division by long. Specialized version of the method divadd. dh is a high part of the divisor, dl is a low part

divide	back to summary
pack-priv MutableBigInteger divide(MutableBigInteger b, MutableBigInteger quotient) Calculates the quotient of this div b and places the quotient in the provided MutableBigInteger objects and the remainder object is returned.

divide	back to summary
pack-priv MutableBigInteger divide(MutableBigInteger b, MutableBigInteger quotient, boolean needRemainder)

divide	back to summary
pack-priv long divide(long v, MutableBigInteger quotient) Internally used to calculate the quotient of this div v and places the quotient in the provided MutableBigInteger object and the remainder is returned. Returns:long the remainder of the division will be returned.

divide

back to summary

pack-priv long divide(long v, MutableBigInteger quotient)

Internally used to calculate the quotient of this div v and places the quotient in the provided MutableBigInteger object and the remainder is returned.

Returns:long: the remainder of the division will be returned.

divide2n1n back to summary

divide2n1n	back to summary
private MutableBigInteger divide2n1n(MutableBigInteger b, MutableBigInteger quotient) This method implements algorithm 1 from pg. 4 of the Burnikel-Ziegler paper. It divides a 2n-digit number by a n-digit number. The parameter beta is 2³² so all shifts are multiples of 32 bits. `this` must be a nonnegative number such that `this.bitLength() <= 2*b.bitLength()` Parameters b:MutableBigInteger a positive number such that `b.bitLength()` is even quotient:MutableBigInteger output parameter for `this/b` Returns:MutableBigInteger `this%b`

private MutableBigInteger divide2n1n(MutableBigInteger b, MutableBigInteger quotient)

This method implements algorithm 1 from pg. 4 of the Burnikel-Ziegler paper. It divides a 2n-digit number by a n-digit number.
The parameter beta is 2³² so all shifts are multiples of 32 bits.
this must be a nonnegative number such that this.bitLength() <= 2*b.bitLength()

Parameters

b:MutableBigInteger: a positive number such that b.bitLength() is even
quotient:MutableBigInteger: output parameter for this/b

Returns:MutableBigInteger

this%b

divide3n2n back to summary

divide3n2n	back to summary
private MutableBigInteger divide3n2n(MutableBigInteger b, MutableBigInteger quotient) This method implements algorithm 2 from pg. 5 of the Burnikel-Ziegler paper. It divides a 3n-digit number by a 2n-digit number. The parameter beta is 2³² so all shifts are multiples of 32 bits. `this` must be a nonnegative number such that `2this.bitLength() <= 3b.bitLength()` Parameters quotient:MutableBigInteger output parameter for `this/b` Returns:MutableBigInteger `this%b`

private MutableBigInteger divide3n2n(MutableBigInteger b, MutableBigInteger quotient)

This method implements algorithm 2 from pg. 5 of the Burnikel-Ziegler paper. It divides a 3n-digit number by a 2n-digit number.
The parameter beta is 2³² so all shifts are multiples of 32 bits.

this must be a nonnegative number such that 2*this.bitLength() <= 3*b.bitLength()

Parameters

quotient:MutableBigInteger: output parameter for this/b

Returns:MutableBigInteger

this%b

divideAndRemainderBurnikelZiegler back to summary

divideAndRemainderBurnikelZiegler	back to summary
pack-priv MutableBigInteger divideAndRemainderBurnikelZiegler(MutableBigInteger b, MutableBigInteger quotient) Computes `this/b` and `this%b` using the Burnikel-Ziegler algorithm. This method implements algorithm 3 from pg. 9 of the Burnikel-Ziegler paper. The parameter beta was chosen to b 2³² so almost all shifts are multiples of 32 bits. `this` and `b` must be nonnegative. Parameters b:MutableBigInteger the divisor quotient:MutableBigInteger output parameter for `this/b` Returns:MutableBigInteger the remainder

pack-priv MutableBigInteger divideAndRemainderBurnikelZiegler(MutableBigInteger b, MutableBigInteger quotient)

Computes this/b and this%b using the Burnikel-Ziegler algorithm. This method implements algorithm 3 from pg. 9 of the Burnikel-Ziegler paper. The parameter beta was chosen to b 2³² so almost all shifts are multiples of 32 bits.
this and b must be nonnegative.

Parameters

b:MutableBigInteger: the divisor
quotient:MutableBigInteger: output parameter for this/b

Returns:MutableBigInteger

the remainder

divideKnuth	back to summary
pack-priv MutableBigInteger divideKnuth(MutableBigInteger b, MutableBigInteger quotient) See Also `divideKnuth(MutableBigInteger, MutableBigInteger, boolean)`

divideKnuth	back to summary
pack-priv MutableBigInteger divideKnuth(MutableBigInteger b, MutableBigInteger quotient, boolean needRemainder) Calculates the quotient of this div b and places the quotient in the provided MutableBigInteger objects and the remainder object is returned. Uses Algorithm D from Knuth TAOCP Vol. 2, 3rd edition, section 4.3.1. Many optimizations to that algorithm have been adapted from the Colin Plumb C library. It special cases one word divisors for speed. The content of b is not changed.

divideKnuth

back to summary

pack-priv MutableBigInteger divideKnuth(MutableBigInteger b, MutableBigInteger quotient, boolean needRemainder)

Calculates the quotient of this div b and places the quotient in the provided MutableBigInteger objects and the remainder object is returned. Uses Algorithm D from Knuth TAOCP Vol. 2, 3rd edition, section 4.3.1. Many optimizations to that algorithm have been adapted from the Colin Plumb C library. It special cases one word divisors for speed. The content of b is not changed.

divideLongMagnitude	back to summary
private MutableBigInteger divideLongMagnitude(long ldivisor, MutableBigInteger quotient) Divide this MutableBigInteger by the divisor represented by positive long value. The quotient will be placed into the provided quotient object & the remainder object is returned.

divideMagnitude	back to summary
private MutableBigInteger divideMagnitude(MutableBigInteger div, MutableBigInteger quotient, boolean needRemainder) Divide this MutableBigInteger by the divisor. The quotient will be placed into the provided quotient object & the remainder object is returned.

divideOneWord	back to summary
pack-priv int divideOneWord(int divisor, MutableBigInteger quotient) This method is used for division of an n word dividend by a one word divisor. The quotient is placed into quotient. The one word divisor is specified by divisor. Returns:int the remainder of the division is returned.

divideOneWord

back to summary

pack-priv int divideOneWord(int divisor, MutableBigInteger quotient)

This method is used for division of an n word dividend by a one word divisor. The quotient is placed into quotient. The one word divisor is specified by divisor.

Returns:int: the remainder of the division is returned.

ensureCapacity	back to summary
private final void ensureCapacity(int len) If this MutableBigInteger cannot hold len words, increase the size of the value array to len words.

euclidModInverse	back to summary
pack-priv MutableBigInteger euclidModInverse(int k) Uses the extended Euclidean algorithm to compute the modInverse of base mod a modulus that is a power of 2. The modulus is 2^k.

fixup back to summary

pack-priv static MutableBigInteger fixup(MutableBigInteger c, MutableBigInteger p, int k)

The Fixup Algorithm Calculates X such that X = C * 2^(-k) (mod P) Assumes C

getBlock back to summary

private MutableBigInteger getBlock(int index, int numBlocks, int blockLength)

Returns a MutableBigInteger containing blockLength ints from this number, starting at index*blockLength.
Used by Burnikel-Ziegler division.

Parameters

index:int: the block index
numBlocks:int: the total number of blocks in this number
blockLength:int: length of one block in units of 32 bits

getBlockForSqrt back to summary

private MutableBigInteger getBlockForSqrt(int blockIndex, int len, int blockLen)

Returns a MutableBigInteger obtained by taking blockLen ints from this number, ending at blockIndex*blockLen (exclusive).
Used in Karatsuba square root.

Parameters

blockIndex:int: the block index, starting from the lowest
len:int: the logical length of the input value in units of 32 bits
blockLen:int: the length of the block in units of 32 bits

Returns:MutableBigInteger

a MutableBigInteger obtained by taking blockLen ints from this number, ending at blockIndex*blockLen (exclusive).

getInt	back to summary
private final int getInt(int index) Return the int in use in this MutableBigInteger at the specified index. This method is not used because it is not inlined on all platforms.

getLong	back to summary
private final long getLong(int index) Return a long which is equal to the unsigned value of the int in use in this MutableBigInteger at the specified index. This method is not used because it is not inlined on all platforms.

getLower	back to summary
private BigInteger getLower(int n) Returns a `BigInteger` equal to the `n` low ints of this number.

getLowestSetBit	back to summary
private final int getLowestSetBit() Return the index of the lowest set bit in this MutableBigInteger. If the magnitude of this MutableBigInteger is zero, -1 is returned.

getMagnitudeArray	back to summary
private int[] getMagnitudeArray() Internal helper method to return the magnitude array. The caller is not supposed to modify the returned array.

hybridGCD	back to summary
pack-priv MutableBigInteger hybridGCD(MutableBigInteger b) Calculate GCD of this and b. This and b are changed by the computation.

init	back to summary
private void init(int val)

inverseMod32	back to summary
pack-priv static int inverseMod32(int val) Returns the multiplicative inverse of val mod 2^32. Assumes val is odd.

inverseMod64	back to summary
pack-priv static long inverseMod64(long val) Returns the multiplicative inverse of val mod 2^64. Assumes val is odd.

isEven	back to summary
pack-priv boolean isEven() Returns true iff this MutableBigInteger is even.

isNormal	back to summary
pack-priv boolean isNormal() Returns true iff this MutableBigInteger is in normal form. A MutableBigInteger is in normal form if it has no leading zeros after the offset, and intLen + offset <= value.length.

isOdd	back to summary
pack-priv boolean isOdd() Returns true iff this MutableBigInteger is odd.

isOne	back to summary
pack-priv boolean isOne() Returns true iff this MutableBigInteger has a value of one.

isZero	back to summary
pack-priv boolean isZero() Returns true iff this MutableBigInteger has a value of zero.

keepLower	back to summary
private void keepLower(int n) Discards all ints whose index is greater than `n`.

leftShift	back to summary
pack-priv void leftShift(int n) Left shift this MutableBigInteger n bits.

modInverse

back to summary

private MutableBigInteger modInverse(MutableBigInteger mod)

Calculate the multiplicative inverse of this modulo mod, where the mod argument is odd. This and mod are not changed by the calculation. This method implements an algorithm due to Richard Schroeppel, that uses the same intermediate representation as Montgomery Reduction ("Montgomery Form"). The algorithm is described in an unpublished manuscript entitled "Fast Modular Reciprocals."

modInverseBP2	back to summary
pack-priv static MutableBigInteger modInverseBP2(MutableBigInteger mod, int k) Calculate the multiplicative inverse of 2^k mod mod, where mod is odd.

modInverseMP2	back to summary
pack-priv MutableBigInteger modInverseMP2(int k)

mul	back to summary
pack-priv void mul(int y, MutableBigInteger z) Multiply the contents of this MutableBigInteger by the word y. The result is placed into z.

mulsub	back to summary
private int mulsub(int[] q, int[] a, int x, int len, int offset) This method is used for division. It multiplies an n word input a by one word input x, and subtracts the n word product from q. This is needed when subtracting qhat*divisor from dividend.

mulsubBorrow	back to summary
private int mulsubBorrow(int[] q, int[] a, int x, int len, int offset) The method is the same as mulsun, except the fact that q array is not updated, the only result of the method is borrow flag.

mulsubLong	back to summary
private int mulsubLong(int[] q, int dh, int dl, int x, int offset) This method is used for division by long. Specialized version of the method sulsub. dh is a high part of the divisor, dl is a low part

multiply	back to summary
pack-priv void multiply(MutableBigInteger y, MutableBigInteger z) Multiply the contents of two MutableBigInteger objects. The result is placed into MutableBigInteger z. The contents of y are not changed. Assume `intLen > 0`

mutableModInverse	back to summary
pack-priv MutableBigInteger mutableModInverse(MutableBigInteger p) Returns the modInverse of this mod p. This and p are not affected by the operation.

newtonRecurrenceRootn	back to summary
private static void newtonRecurrenceRootn(MutableBigInteger x, MutableBigInteger s, int n, BigInteger sToN1) Computes `((n-1)*s + x/sToN1)/n` and places the result in `s`.

normalize	back to summary
pack-priv final void normalize() Ensure that the MutableBigInteger is in normal form, specifically making sure that there are no leading zeros, and that if the magnitude is zero, then intLen is zero.

ones back to summary

private void ones(int n)

Makes this number an n-int number all of whose bits are ones. Used by Burnikel-Ziegler division.

Parameters

n:int: number of ints in the value array

primitiveLeftShift	back to summary
private void primitiveLeftShift(int n) Left shift this MutableBigInteger n bits, where n is less than 32. Assumes that intLen > 0, n > 0 for speed

primitiveLeftShift back to summary

private void primitiveLeftShift(int n, int[] result, int resFrom)

Left shift this MutableBigInteger n bits, where n is less than 32, placing the result in the specified array. Assumes that intLen > 0, n > 0 for speed. The result can be the value array of this MutableBigInteger, but for speed the copy is not performed safely, so, in that case the caller has to make sure that (resFrom <= offset || resFrom >= offset + intLen).

primitiveRightShift	back to summary
private void primitiveRightShift(int n) Right shift this MutableBigInteger n bits, where n is less than 32. Assumes that intLen > 0, n > 0 for speed

primitiveRightShift back to summary

private void primitiveRightShift(int n, int[] result, int resFrom)

Right shift this MutableBigInteger n bits, where n is less than 32, placing the result in the specified array. Assumes that intLen > 0, n > 0 for speed. The result can be the value array of this MutableBigInteger, but for speed the copy is not performed safely, so, in that case the caller has to make sure that (resFrom <= offset || resFrom >= offset + intLen).

reset	back to summary
pack-priv void reset() Set a MutableBigInteger to zero, removing its offset.

rightShift	back to summary
pack-priv void rightShift(int n) Right shift this MutableBigInteger n bits. The MutableBigInteger is left in normal form. Assumes `Math.ceilDiv(n, 32) <= intLen \|\| intLen == 0`

rootnApprox	back to summary
private static double rootnApprox(double x, int n)

rootnRem back to summary

pack-priv MutableBigInteger[] rootnRem(int n)

Calculate the integer nth root floor(nthRoot(this, n)) and the remainder, where nthRoot(., n) denotes the mathematical nth root. The contents of this are not changed. The value of this is assumed to be non-negative and the root degree n >= 3. Assumes bitLength() <= Integer.MAX_VALUE.

Implementation Note

The implementation is based on the material in Richard P. Brent and Paul Zimmermann, Modern Computer Arithmetic, p. 27-28.

Parameters

n:int: the root degree

Returns:MutableBigInteger[]

the integer nth root of this and the remainder

safeLeftShift	back to summary
pack-priv void safeLeftShift(int n) Like `leftShift(int)` but `n` can be zero.

safeRightShift	back to summary
pack-priv void safeRightShift(int n) Like `rightShift(int)` but `n` can be greater than the length of the number.

setInt	back to summary
pack-priv void setInt(int index, int val) Sets the int at index+offset in this MutableBigInteger to val. This does not get inlined on all platforms so it is not used as often as originally intended.

setValue	back to summary
pack-priv void setValue(int[] val, int length) Sets this MutableBigInteger's value array to the specified array. The intLen is set to the specified length.

shiftAdd	back to summary
pack-priv void shiftAdd(MutableBigInteger addend, int n) Shifts `this` of `n` ints to the left and adds `addend`. Assumes `n > 0` for speed.

shiftAddDisjoint	back to summary
pack-priv void shiftAddDisjoint(MutableBigInteger addend, int n) Shifts `this` of `n` ints to the left and adds `addend`. Assumes `addend.intLen <= n`.

sqrtRem back to summary

pack-priv MutableBigInteger[] sqrtRem(boolean needRemainder)

Calculate the integer square root floor(sqrt(this)) and the remainder if needed, where sqrt(.) denotes the mathematical square root. The contents of this are not changed. The value of this is assumed to be non-negative.

Returns:MutableBigInteger[]: the integer square root of this and the remainder if needed

sqrtRemKaratsuba	back to summary
private MutableBigInteger[] sqrtRemKaratsuba(int len, boolean needRemainder) Assumes `2 <= len <= intLen && len % 2 == 0 && Integer.numberOfLeadingZeros(value[offset]) <= 1` Implementation Note The implementation is based on Zimmermann's works available here and here

subtract	back to summary
pack-priv int subtract(MutableBigInteger b) Subtracts the smaller of this and b from the larger and places the result into this MutableBigInteger.

toBigDecimal	back to summary
pack-priv BigDecimal toBigDecimal(int sign, int scale) Convert this MutableBigInteger to BigDecimal object with the specified sign and scale.

toBigInteger	back to summary
pack-priv BigInteger toBigInteger(int sign) Convert this MutableBigInteger to a BigInteger object.

toBigInteger	back to summary
pack-priv BigInteger toBigInteger() Converts this number to a nonnegative `BigInteger`.

toCompactValue	back to summary
pack-priv long toCompactValue(int sign) This is for internal use in converting from a MutableBigInteger object into a long value given a specified sign. returns INFLATED if value is not fit into long

toIntArray	back to summary
pack-priv int[] toIntArray() Convert this MutableBigInteger into an int array with no leading zeros, of a length that is equal to this MutableBigInteger's intLen.

toLong	back to summary
private long toLong() Convert this MutableBigInteger to a long value. The caller has to make sure this MutableBigInteger can be fit into long.

toString

back to summary

public String toString()

Overrides java.lang.Object.toString.

Returns a String representation of this MutableBigInteger in radix 10.

unsignedLongCompare	back to summary
private boolean unsignedLongCompare(long one, long two) Compare two longs as if they were unsigned. Returns true iff one is bigger than two.

unsignedLongSqrt	back to summary
private static long unsignedLongSqrt(long x)

pack-priv Class MutableBigInteger

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail