java.math
Class SignedMutableBigInteger

java.lang.Object
  java.math.MutableBigInteger
      java.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.