java.math
Class SignedMutableBigInteger

java.lang.Object
  extended byjava.math.MutableBigInteger
      extended byjava.math.SignedMutableBigInteger

class SignedMutableBigInteger
extends MutableBigInteger

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 increased 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. Note that SignedMutableBigIntegers only support signed addition and subtraction. All other operations occur as with MutableBigIntegers.

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.
(package private)  int offset
          The offset into the value array where the magnitude of this MutableBigInteger begins.
(package private)  int sign
          The sign of this MutableBigInteger.
(package private)  int[] value
          Holds the magnitude of this MutableBigInteger in big endian order.
 
Constructor Summary
(package private) SignedMutableBigInteger()
          The default constructor.
(package private) SignedMutableBigInteger(int val)
          Construct a new MutableBigInteger with a magnitude specified by the int val.
(package private) SignedMutableBigInteger(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.
(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.
(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.
(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)
           
(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.
(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.
(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.
(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)  void signedAdd(MutableBigInteger addend)
          Signed addition built upon unsigned add and subtract.
(package private)  void signedAdd(SignedMutableBigInteger addend)
          Signed addition built upon unsigned add and subtract.
(package private)  void signedSubtract(MutableBigInteger addend)
          Signed subtraction built upon unsigned add and subtract.
(package private)  void signedSubtract(SignedMutableBigInteger addend)
          Signed subtraction built upon unsigned add and subtract.
(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()
          Print out the first intLen ints of this MutableBigInteger's value array starting at offset.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

sign

int sign
The sign of this MutableBigInteger.


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.

Constructor Detail

SignedMutableBigInteger

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


SignedMutableBigInteger

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


SignedMutableBigInteger

SignedMutableBigInteger(MutableBigInteger val)
Construct a new MutableBigInteger with a magnitude equal to the specified MutableBigInteger.

Method Detail

signedAdd

void signedAdd(SignedMutableBigInteger addend)
Signed addition built upon unsigned add and subtract.


signedAdd

void signedAdd(MutableBigInteger addend)
Signed addition built upon unsigned add and subtract.


signedSubtract

void signedSubtract(SignedMutableBigInteger addend)
Signed subtraction built upon unsigned add and subtract.


signedSubtract

void signedSubtract(MutableBigInteger addend)
Signed subtraction built upon unsigned add and subtract.


toString

public String toString()
Print out the first intLen ints of this MutableBigInteger's value array starting at offset.

Overrides:
toString in class MutableBigInteger

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.


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.


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.


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.


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.


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.


hybridGCD

MutableBigInteger hybridGCD(MutableBigInteger b)
Calculate GCD of this and b. This and b are changed by the computation.


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)

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.