SignedMutableBigInteger

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.

@see BigInteger @author Michael McCloskey

class SignedMutableBigInteger : MutableBigInteger {

int sign;

this();

this(int val);

this(MutableBigInteger val);

void signedAdd(SignedMutableBigInteger addend);

void signedAdd(MutableBigInteger addend);

void signedSubtract(SignedMutableBigInteger addend);

void signedSubtract(MutableBigInteger addend);

string toString();

}

Constructors

this this(): The default constructor. An empty MutableBigInteger is created with a one word capacity.
this this(int val): Construct a new MutableBigInteger with a magnitude specified by the int val.
this this(MutableBigInteger val): Construct a new MutableBigInteger with a magnitude equal to the specified MutableBigInteger.

Members

Functions

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 string toString(): Print out the first intLen ints of this MutableBigInteger's value array starting at offset.

Variables

sign int sign;: The sign of this MutableBigInteger.

Inherited Members

From 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.
ONE 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.
KNUTH_POW2_THRESH_LEN enum int KNUTH_POW2_THRESH_LEN;: The minimum {@code intLen} for cancelling powers of two before dividing. If the number of ints is less than this threshold, {@code divideKnuth} does not eliminate common powers of two from the dividend and divisor.
KNUTH_POW2_THRESH_ZEROS enum 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, {@code divideKnuth} does not eliminate common powers of two from the dividend and divisor.
cloneValue int[] cloneValue(): Undocumented in source. Be warned that the author may not have intended to support it.
toBigInteger BigInteger toBigInteger(int sign): Convert this MutableBigInteger to a BigInteger object.
toBigInteger BigInteger toBigInteger(): Converts this number to a nonnegative {@code BigInteger}.
toCompactValue 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
clear void clear(): Clear out a MutableBigInteger for reuse.
reset void reset(): Set a MutableBigInteger to zero, removing its offset.
compare 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 {@code b}.
compareHalf 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().
normalize 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 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 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 bool isOne(): Returns true iff this MutableBigInteger has a value of one.
isZero bool isZero(): Returns true iff this MutableBigInteger has a value of zero.
isEven bool isEven(): Returns true iff this MutableBigInteger is even.
isOdd bool isOdd(): Returns true iff this MutableBigInteger is odd.
isNormal bool 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 <= cast(int)value.length.
toString string toString(): Returns a string representation of this MutableBigInteger in radix 10.
safeRightShift void safeRightShift(int n): Like {@link #rightShift(int)} but {@code n} can be greater than the length of the number.
rightShift void rightShift(int n): Right shift this MutableBigInteger n bits. The MutableBigInteger is left in normal form.
safeLeftShift void safeLeftShift(int n): Like {@link #leftShift(int)} but {@code n} can be zero.
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.
addShifted void addShifted(MutableBigInteger addend, int n): Adds the value of {@code addend} shifted {@code n} ints to the left. Has the same effect as {@code addend.leftShift(32*ints); add(addend);} but doesn't change the value of {@code addend}.
addDisjoint void addDisjoint(MutableBigInteger addend, int n): Like {@link #addShifted(MutableBigInteger, int)} but {@code this.intLen} must not be greater than {@code n}. In other words, concatenates {@code this} and {@code addend}.
addLower void addLower(MutableBigInteger addend, int n): Adds the low {@code n} ints of {@code addend}.
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 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.
divide 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 MutableBigInteger divide(MutableBigInteger b, MutableBigInteger quotient, bool needRemainder): Undocumented in source. Be warned that the author may not have intended to support it.
divideKnuth MutableBigInteger divideKnuth(MutableBigInteger b, MutableBigInteger quotient): @see #divideKnuth(MutableBigInteger, MutableBigInteger, bool)
divideKnuth MutableBigInteger divideKnuth(MutableBigInteger b, MutableBigInteger quotient, bool needRemainder): Calculates the quotient of this div b and places the quotient in the provided MutableBigInteger objects and the remainder object is returned.
divideAndRemainderBurnikelZiegler MutableBigInteger divideAndRemainderBurnikelZiegler(MutableBigInteger b, MutableBigInteger quotient): Computes {@code this/b} and {@code this%b} using the <a href="http://cr.yp.to/bib/1998/burnikel.ps"> Burnikel-Ziegler algorithm</a>. This method implements algorithm 3 from pg. 9 of the Burnikel-Ziegler paper. The parameter beta was chosen to b 232 so almost all shifts are multiples of 32 bits. {@code this} and {@code b} must be nonnegative. @param b the divisor @param quotient output parameter for {@code this/b} @return the remainder
bitLength long bitLength(): @see BigInteger#bitLength()
divide 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.
divWord long divWord(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. Returns long value where high 32 bits contain remainder value and low 32 bits contain quotient value.
sqrt MutableBigInteger sqrt(): Calculate the integer square root {@code floor(sqrt(this))} where {@code sqrt(.)} denotes the mathematical square root. The contents of {@code this} are not changed. The value of {@code this} is assumed to be non-negative.
hybridGCD MutableBigInteger hybridGCD(MutableBigInteger b): Calculate GCD of this and b. This and b are changed by the computation.
binaryGcd 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): Undocumented in source. Be warned that the author may not have intended to support it.
inverseMod32 int inverseMod32(int val): Returns the multiplicative inverse of val mod 2^32. Assumes val is odd.
inverseMod64 long inverseMod64(long val): Returns the multiplicative inverse of val mod 2^64. Assumes val is odd.
modInverseBP2 MutableBigInteger modInverseBP2(MutableBigInteger mod, int k): Calculate the multiplicative inverse of 2^k mod mod, where mod is odd.
fixup MutableBigInteger fixup(MutableBigInteger c, MutableBigInteger p, int k): The Fixup Algorithm Calculates X such that X = C * 2^(-k) (mod P) Assumes C<P and P is odd.
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.