java.math
Class MutableBigInteger

java.lang.Object
  |
  +--java.math.MutableBigInteger

Direct Known Subclasses:

SignedMutableBigInteger

class MutableBigInteger

extends Object

A class used to represent multiprecision integers that makes efficient use of allocated space by allowing a number to occupy only part of an array so that the arrays do not have to be reallocated as often. When performing an operation with many iterations the array used to hold a number is only reallocated when necessary and does not have to be the same size as the number it represents. A mutable number allows calculations to occur on the same number without having to create a new number for every step of the calculation as occurs with BigIntegers.

Since:

1.3

Version:

1.8, 06/11/02

Author:

Michael McCloskey

See Also:

BigInteger

Field Summary

(package private) int	intLen The number of ints of the value array that are currently used to hold the magnitude of this MutableBigInteger.
private static long	LONG_MASK This mask is used to obtain the value of an int as if it were unsigned.
(package private) int	offset The offset into the value array where the magnitude of this MutableBigInteger begins.
(package private) int[]	value Holds the magnitude of this MutableBigInteger in big endian order.

Constructor Summary

(package private)	MutableBigInteger() The default constructor.
(package private)	MutableBigInteger(BigInteger b) Construct a new MutableBigInteger with a magnitude equal to the specified BigInteger.
(package private)	MutableBigInteger(int val) Construct a new MutableBigInteger with a magnitude specified by the int val.
(package private)	MutableBigInteger(int[] val) Construct a new MutableBigInteger with the specified value array up to the length of the array supplied.
(package private)	MutableBigInteger(int[] val, int len) Construct a new MutableBigInteger with the specified value array up to the specified length.
(package private)	MutableBigInteger(MutableBigInteger val) Construct a new MutableBigInteger with a magnitude equal to the specified MutableBigInteger.

Method Summary

(package private) void	add(MutableBigInteger addend) Adds the contents of two MutableBigInteger objects.The result is placed within this MutableBigInteger.
(package private) static int	binaryGcd(int a, int b) Calculate GCD of a and b interpreted as unsigned integers.
private MutableBigInteger	binaryGCD(MutableBigInteger v) Calculate GCD of this and v.
(package private) void	clear() Clear out a MutableBigInteger for reuse.
(package private) int	compare(MutableBigInteger b) Compare the magnitude of two MutableBigIntegers.
(package private) void	copyValue(int[] val) Sets this MutableBigInteger's value array to a copy of the specified array.
(package private) void	copyValue(MutableBigInteger 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.
(package private) void	divide(MutableBigInteger b, MutableBigInteger quotient, MutableBigInteger rem) Calculates the quotient and remainder of this div b and places them in the MutableBigInteger objects provided.
(package private) void	divideOneWord(int divisor, MutableBigInteger quotient) This method is used for division of an n word dividend by a one word divisor.
private void	divWord(int[] result, long n, int d) This method divides a long quantity by an int to estimate qhat for two multi precision numbers.
private void	ensureCapacity(int len) If this MutableBigInteger cannot hold len words, increase the size of the value array to len words.
(package private) MutableBigInteger	euclidModInverse(int k) Uses the extended Euclidean algorithm to compute the modInverse of base mod a modulus that is a power of 2.
(package private) static MutableBigInteger	fixup(MutableBigInteger c, MutableBigInteger p, int k)
private int	getInt(int index) Return the int in use in this MutableBigInteger at the specified index.
private 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 int	getLowestSetBit() Return the index of the lowest set bit in this MutableBigInteger.
(package private) MutableBigInteger	hybridGCD(MutableBigInteger b) Calculate GCD of this and b.
(package private) static int	inverseMod32(int val)
(package private) boolean	isEven() Returns true iff this MutableBigInteger is even.
(package private) boolean	isNormal() Returns true iff this MutableBigInteger is in normal form.
(package private) boolean	isOdd() Returns true iff this MutableBigInteger is odd.
(package private) boolean	isOne() Returns true iff this MutableBigInteger has a value of one.
(package private) boolean	isZero() Returns true iff this MutableBigInteger has a value of zero.
(package private) void	leftShift(int n) Left shift this MutableBigInteger n bits.
private MutableBigInteger	modInverse(MutableBigInteger mod) Calculate the multiplicative inverse of this mod mod, where mod is odd.
(package private) static MutableBigInteger	modInverseBP2(MutableBigInteger mod, int k)
(package private) MutableBigInteger	modInverseMP2(int k)
(package private) 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.
(package private) void	multiply(MutableBigInteger y, MutableBigInteger z) Multiply the contents of two MutableBigInteger objects.
(package private) MutableBigInteger	mutableModInverse(MutableBigInteger p) Returns the modInverse of this mod p.
(package private) 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	primitiveLeftShift(int n) Left shift this MutableBigInteger n bits, where n is less than 32.
private void	primitiveRightShift(int n) Right shift this MutableBigInteger n bits, where n is less than 32.
(package private) void	reset() Set a MutableBigInteger to zero, removing its offset.
(package private) void	rightShift(int n) Right shift this MutableBigInteger n bits.
(package private) void	setInt(int index, int val) Sets the int at index+offset in this MutableBigInteger to val.
(package private) void	setValue(int[] val, int length) Sets this MutableBigInteger's value array to the specified array.
(package private) int	subtract(MutableBigInteger b) Subtracts the smaller of this and b from the larger and places the result into this MutableBigInteger.
(package private) int[]	toIntArray() Convert this MutableBigInteger into an int array with no leading zeros, of a length that is equal to this MutableBigInteger's intLen.
String	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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

value

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.

intLen

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.

offset

int offset

The offset into the value array where the magnitude of this MutableBigInteger begins.

LONG_MASK

private static final long LONG_MASK

This mask is used to obtain the value of an int as if it were unsigned.

Constructor Detail

MutableBigInteger

MutableBigInteger()

The default constructor. An empty MutableBigInteger is created with a one word capacity.

MutableBigInteger

MutableBigInteger(int val)

Construct a new MutableBigInteger with a magnitude specified by the int val.

MutableBigInteger

MutableBigInteger(int[] val,
                  int len)

Construct a new MutableBigInteger with the specified value array up to the specified length.

MutableBigInteger

MutableBigInteger(int[] val)

Construct a new MutableBigInteger with the specified value array up to the length of the array supplied.

MutableBigInteger

MutableBigInteger(BigInteger b)

Construct a new MutableBigInteger with a magnitude equal to the specified BigInteger.

MutableBigInteger

MutableBigInteger(MutableBigInteger val)

Construct a new MutableBigInteger with a magnitude equal to the specified MutableBigInteger.

Method Detail

clear

void clear()

Clear out a MutableBigInteger for reuse.

reset

void reset()

Set a MutableBigInteger to zero, removing its offset.

compare

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.

getLowestSetBit

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.

getInt

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

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.

normalize

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.

ensureCapacity

private final void ensureCapacity(int len)

If this MutableBigInteger cannot hold len words, increase the size of the value array to len words.

toIntArray

int[] toIntArray()

Convert this MutableBigInteger into an int array with no leading zeros, of a length that is equal to this MutableBigInteger's intLen.

setInt

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

void setValue(int[] val,
              int length)

Sets this MutableBigInteger's value array to the specified array. The intLen is set to the specified length.

copyValue

void copyValue(MutableBigInteger val)

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

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.

isOne

boolean isOne()

Returns true iff this MutableBigInteger has a value of one.

isZero

boolean isZero()

Returns true iff this MutableBigInteger has a value of zero.

isEven

boolean isEven()

Returns true iff this MutableBigInteger is even.

isOdd

boolean isOdd()

Returns true iff this MutableBigInteger is odd.

isNormal

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.

toString

public String toString()

Returns a String representation of this MutableBigInteger in radix 10.

Overrides:

toString in class Object

Returns:

a string representation of the object.

rightShift

void rightShift(int n)

Right shift this MutableBigInteger n bits. The MutableBigInteger is left in normal form.

leftShift

void leftShift(int n)

Left shift this MutableBigInteger n bits.

divadd

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.

mulsub

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.

primitiveRightShift

private final void primitiveRightShift(int n)

Right shift this MutableBigInteger n bits, where n is less than 32. Assumes that intLen > 0, n > 0 for speed

primitiveLeftShift

private final void primitiveLeftShift(int n)

Left shift this MutableBigInteger n bits, where n is less than 32. Assumes that intLen > 0, n > 0 for speed

add

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.

subtract

int subtract(MutableBigInteger b)

Subtracts the smaller of this and b from the larger and places the result into this MutableBigInteger.

difference

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.

multiply

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.

mul

void mul(int y,
         MutableBigInteger z)

Multiply the contents of this MutableBigInteger by the word y. The result is placed into z.

divideOneWord

void 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. The value of this MutableBigInteger is the dividend at invocation but is replaced by the remainder. NOTE: The value of this MutableBigInteger is modified by this method.

divide

void divide(MutableBigInteger b,
            MutableBigInteger quotient,
            MutableBigInteger rem)

Calculates the quotient and remainder of this div b and places them in the MutableBigInteger objects provided. Uses Algorithm D in Knuth 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 contents of a and b are not changed.

unsignedLongCompare

private boolean unsignedLongCompare(long one,
                                    long two)

Compare two longs as if they were unsigned. Returns true iff one is bigger than two.

divWord

private void divWord(int[] result,
                     long n,
                     int d)

This method divides a long quantity by an int to estimate qhat for two multi precision numbers. It is used when the signed value of n is less than zero.

hybridGCD

MutableBigInteger hybridGCD(MutableBigInteger b)

Calculate GCD of this and b. This and b are changed by the computation.

binaryGCD

private MutableBigInteger binaryGCD(MutableBigInteger v)

Calculate GCD of this and v. Assumes that this and v are not zero.

binaryGcd

static int binaryGcd(int a,
                     int b)

Calculate GCD of a and b interpreted as unsigned integers.

mutableModInverse

MutableBigInteger mutableModInverse(MutableBigInteger p)

Returns the modInverse of this mod p. This and p are not affected by the operation.

modInverseMP2

MutableBigInteger modInverseMP2(int k)

inverseMod32

static int inverseMod32(int val)

modInverseBP2

static MutableBigInteger modInverseBP2(MutableBigInteger mod,
                                       int k)

modInverse

private MutableBigInteger modInverse(MutableBigInteger mod)

Calculate the multiplicative inverse of this mod mod, where mod 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."

fixup

static MutableBigInteger fixup(MutableBigInteger c,
                               MutableBigInteger p,
                               int k)

euclidModInverse

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.