java.math
Class MutableBigInteger

java.lang.Object
  extended byjava.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
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.

See Also:
Constant Field Values
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.