/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation. Oracle designates this
* particular file as subject to the "Classpath" exception as provided
* by Oracle in the LICENSE file that accompanied this code.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*/
/**
* 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.
*
* @see BigInteger
* @author Michael McCloskey
* @since 1.3
*/
class MutableBigInteger {
/**
* 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.
*/
int[] value;
/**
* 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.
*/
int intLen;
/**
* The offset into the value array where the magnitude of this
* MutableBigInteger begins.
*/
// Constants
/**
* 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.
*/
// Constructors
/**
* The default constructor. An empty MutableBigInteger is created with
* a one word capacity.
*/
value = new int[1];
intLen = 0;
}
/**
* Construct a new MutableBigInteger with a magnitude specified by
* the int val.
*/
value = new int[1];
intLen = 1;
}
/**
* Construct a new MutableBigInteger with the specified value array
* up to the length of the array supplied.
*/
}
/**
* Construct a new MutableBigInteger with a magnitude equal to the
* specified BigInteger.
*/
}
/**
* Construct a new MutableBigInteger with a magnitude equal to the
* specified MutableBigInteger.
*/
}
/**
* Internal helper method to return the magnitude array. The caller is not
* supposed to modify the returned array.
*/
private int[] getMagnitudeArray() {
return value;
}
/**
* Convert this MutableBigInteger to a long value. The caller has to make
* sure this MutableBigInteger can be fit into long.
*/
private long toLong() {
if (intLen == 0)
return 0;
}
/**
* Convert this MutableBigInteger to a BigInteger object.
*/
return BigInteger.ZERO;
}
/**
* Convert this MutableBigInteger to BigDecimal object with the specified sign
* and scale.
*/
int[] mag = getMagnitudeArray();
int d = mag[0];
// If this MutableBigInteger can't be fit into long, we need to
// make a BigInteger object for the resultant BigDecimal object.
long v = (len == 2) ?
d & LONG_MASK;
}
/**
* Clear out a MutableBigInteger for reuse.
*/
void clear() {
}
/**
* Set a MutableBigInteger to zero, removing its offset.
*/
void reset() {
}
/**
* Compare the magnitude of two MutableBigIntegers. Returns -1, 0 or 1
* as this MutableBigInteger is numerically less than, equal to, or
* greater than <tt>b</tt>.
*/
return -1;
return 1;
// Add Integer.MIN_VALUE to make the comparison act as unsigned integer
// comparison.
return -1;
return 1;
}
return 0;
}
/**
* Compare this against half of a MutableBigInteger object (Needed for
* remainder tests).
* Assumes no leading unnecessary zeros, which holds for results
* from divide().
*/
if (len <= 0)
return 1;
return -1;
int bstart = 0;
int carry = 0;
// Only 2 cases left:len == blen or len == blen - 1
++bstart;
carry = 0x80000000;
} else
return -1;
}
// compare values with right-shifted values of b,
// carrying shifted-out bits across words
if (v != hb)
}
}
/**
* Return the index of the lowest set bit in this MutableBigInteger. If the
* magnitude of this MutableBigInteger is zero, -1 is returned.
*/
private final int getLowestSetBit() {
if (intLen == 0)
return -1;
int j, b;
;
if (b==0)
return -1;
}
/**
* 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.
*/
}
/**
* 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.
*/
}
/**
* 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.
*/
final void normalize() {
if (intLen == 0) {
offset = 0;
return;
}
return;
do {
index++;
}
/**
* If this MutableBigInteger cannot hold len words, increase the size
* of the value array to len words.
*/
offset = 0;
}
}
/**
* Convert this MutableBigInteger into an int array with no leading
* zeros, of a length that is equal to this MutableBigInteger's intLen.
*/
int[] toIntArray() {
for(int i=0; i<intLen; i++)
return result;
}
/**
* 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.
*/
}
/**
* Sets this MutableBigInteger's value array to the specified array.
* The intLen is set to the specified length.
*/
offset = 0;
}
/**
* Sets this MutableBigInteger's value array to a copy of the specified
* array. The intLen is set to the length of the new array.
*/
offset = 0;
}
/**
* Sets this MutableBigInteger's value array to a copy of the specified
* array. The intLen is set to the length of the specified array.
*/
offset = 0;
}
/**
* Returns true iff this MutableBigInteger has a value of one.
*/
boolean isOne() {
}
/**
* Returns true iff this MutableBigInteger has a value of zero.
*/
boolean isZero() {
return (intLen == 0);
}
/**
* Returns true iff this MutableBigInteger is even.
*/
boolean isEven() {
}
/**
* Returns true iff this MutableBigInteger is odd.
*/
boolean isOdd() {
}
/**
* 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.
*/
boolean isNormal() {
return false;
if (intLen ==0)
return true;
}
/**
* Returns a String representation of this MutableBigInteger in radix 10.
*/
return b.toString();
}
/**
* Right shift this MutableBigInteger n bits. The MutableBigInteger is left
* in normal form.
*/
void rightShift(int n) {
if (intLen == 0)
return;
int nInts = n >>> 5;
int nBits = n & 0x1F;
if (nBits == 0)
return;
if (nBits >= bitsInHighWord) {
this.intLen--;
} else {
}
}
/**
* Left shift this MutableBigInteger n bits.
*/
void leftShift(int n) {
/*
* If there is enough storage space in this MutableBigInteger already
* the available space will be used. Space to the right of the used
* ints in the value array is faster to utilize, so the extra space
* will be taken from the right if possible.
*/
if (intLen == 0)
return;
int nInts = n >>> 5;
int nBits = n&0x1F;
// If shift can be done without moving words, do so
if (n <= (32-bitsInHighWord)) {
return;
}
newLen--;
// The array must grow
for (int i=0; i<intLen; i++)
// Use space on right
} else {
// Must use space on left
for (int i=0; i<intLen; i++)
value[i] = 0;
offset = 0;
}
if (nBits == 0)
return;
else
}
/**
* 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.
*/
long carry = 0;
}
return (int)carry;
}
/**
* 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.
*/
long carry = 0;
q[offset--] = (int)difference;
+ (((difference & LONG_MASK) >
}
return (int)carry;
}
/**
* Right shift this MutableBigInteger n bits, where n is
* less than 32.
* Assumes that intLen > 0, n > 0 for speed
*/
private final void primitiveRightShift(int n) {
int n2 = 32 - n;
int b = c;
c = val[i-1];
}
}
/**
* Left shift this MutableBigInteger n bits, where n is
* less than 32.
* Assumes that intLen > 0, n > 0 for speed
*/
private final void primitiveLeftShift(int n) {
int n2 = 32 - n;
int b = c;
c = val[i+1];
}
}
/**
* Adds the contents of two MutableBigInteger objects.The result
* is placed within this MutableBigInteger.
* The contents of the addend are not changed.
*/
int x = intLen;
long sum;
long carry = 0;
// Add common parts of both numbers
while(x>0 && y>0) {
x--; y--;
}
// Add remainder of the longer number
while(x>0) {
x--;
return;
}
while(y>0) {
y--;
}
resultLen++;
// Result one word longer from carry-out; copy low-order
// bits into new result.
} else {
}
}
}
/**
* Subtracts the smaller of this and b from the larger and places the
* result into this MutableBigInteger.
*/
MutableBigInteger a = this;
if (sign == 0) {
reset();
return 0;
}
if (sign < 0) {
MutableBigInteger tmp = a;
a = b;
b = tmp;
}
long diff = 0;
int x = a.intLen;
int y = b.intLen;
// Subtract common parts of both numbers
while (y>0) {
x--; y--;
}
// Subtract remainder of longer number
while (x>0) {
x--;
}
normalize();
return sign;
}
/**
* 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.
*/
MutableBigInteger a = this;
if (sign ==0)
return 0;
if (sign < 0) {
MutableBigInteger tmp = a;
a = b;
b = tmp;
}
long diff = 0;
int x = a.intLen;
int y = b.intLen;
// Subtract common parts of both numbers
while (y>0) {
x--; y--;
}
// Subtract remainder of longer number
while (x>0) {
x--;
}
a.normalize();
return sign;
}
/**
* Multiply the contents of two MutableBigInteger objects. The result is
* placed into MutableBigInteger z. The contents of y are not changed.
*/
// Put z into an appropriate state to receive product
z.offset = 0;
// The first iteration is hoisted out of the loop to avoid extra add
long carry = 0;
}
// Perform the multiplication word by word
carry = 0;
}
}
// Remove leading zeros from product
z.normalize();
}
/**
* Multiply the contents of this MutableBigInteger by the word y. The
* result is placed into z.
*/
if (y == 1) {
z.copyValue(this);
return;
}
if (y == 0) {
z.clear();
return;
}
// Perform the multiplication word by word
: z.value);
long carry = 0;
}
if (carry == 0) {
z.offset = 1;
} else {
z.offset = 0;
}
}
/**
* 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.
*
* @return the remainder of the division is returned.
*
*/
// Special case of one word dividend
if (intLen == 1) {
int q = (int) (dividendValue / divisorLong);
int r = (int) (dividendValue - q * divisorLong);
return r;
}
// Normalize the divisor
if (remLong < divisorLong) {
} else {
}
int[] qWord = new int[2];
while (--xlen > 0) {
if (dividendEstimate >= 0) {
} else {
}
}
// Unnormalize
if (shift > 0)
else
return rem;
}
/**
* Calculates the quotient of this div b and places the quotient in the
* provided MutableBigInteger objects and the remainder object is returned.
*
* 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 content of b is not
* changed.
*
*/
if (b.intLen == 0)
throw new ArithmeticException("BigInteger divide by zero");
// Dividend is zero
if (intLen == 0) {
return new MutableBigInteger();
}
// Dividend less than divisor
if (cmp < 0) {
return new MutableBigInteger(this);
}
// Dividend equal to divisor
if (cmp == 0) {
return new MutableBigInteger();
}
// Special case one word divisor
if (b.intLen == 1) {
if (r == 0)
return new MutableBigInteger();
return new MutableBigInteger(r);
}
// Copy divisor value to protect divisor
}
/**
* Internally used to calculate the quotient of this div v and places the
* quotient in the provided MutableBigInteger object and the remainder is
* returned.
*
* @return the remainder of the division will be returned.
*/
if (v == 0)
throw new ArithmeticException("BigInteger divide by zero");
// Dividend is zero
if (intLen == 0) {
return 0;
}
if (v < 0)
v = -v;
int d = (int)(v >>> 32);
// Special case on word divisor
if (d == 0)
else {
}
}
/**
* Divide this MutableBigInteger by the divisor represented by its magnitude
* array. The quotient will be placed into the provided quotient object &
* the remainder object is returned.
*/
// Remainder starts as dividend with space for a leading zero
// Set the quotient size
}
// D1 normalize the divisor
if (shift > 0) {
// First shift will not grow array
// But this one might
}
// Must insert leading 0 in rem if its length did not change
}
int[] qWord = new int[2];
// D2 Initialize j
for(int j=0; j<limit; j++) {
// D3 Calculate qhat
// estimate qhat
int qhat = 0;
int qrem = 0;
boolean skipCorrection = false;
qhat = ~0;
} else {
if (nChunk >= 0) {
} else {
}
}
if (qhat == 0)
continue;
if (!skipCorrection) { // Correct qhat
qhat--;
qhat--;
}
}
}
// D4 Multiply and subtract
// D5 Test remainder
// D6 Add back
qhat--;
}
// Store the quotient digit
q[j] = qhat;
} // D7 loop on j
// D8 Unnormalize
if (shift > 0)
return rem;
}
/**
* Compare two longs as if they were unsigned.
* Returns true iff one is bigger than two.
*/
}
/**
* 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.
*/
if (dLong == 1) {
result[0] = (int)n;
return;
}
// Approximate the quotient and remainder
long r = n - q*dLong;
// Correct the approximation
while (r < 0) {
r += dLong;
q--;
}
while (r >= dLong) {
r -= dLong;
q++;
}
// n - q*dlong == r && 0 <= r <dLong, hence we're done.
result[0] = (int)q;
result[1] = (int)r;
}
/**
* Calculate GCD of this and b. This and b are changed by the computation.
*/
// Use Euclid's algorithm until the numbers are approximately the
// same length, then use the binary GCD algorithm to find the GCD.
MutableBigInteger a = this;
MutableBigInteger q = new MutableBigInteger();
while (b.intLen != 0) {
return a.binaryGCD(b);
MutableBigInteger r = a.divide(b, q);
a = b;
b = r;
}
return a;
}
/**
* Calculate GCD of this and v.
* Assumes that this and v are not zero.
*/
// Algorithm B from Knuth section 4.5.2
MutableBigInteger u = this;
MutableBigInteger r = new MutableBigInteger();
// step B1
int s1 = u.getLowestSetBit();
int s2 = v.getLowestSetBit();
if (k != 0) {
u.rightShift(k);
v.rightShift(k);
}
// step B2
MutableBigInteger t = uOdd ? v: u;
int lb;
// steps B3 and B4
t.rightShift(lb);
// step B5
if (tsign > 0)
u = t;
else
v = t;
// Special case one word numbers
x = binaryGcd(x, y);
r.value[0] = x;
r.intLen = 1;
r.offset = 0;
if (k > 0)
r.leftShift(k);
return r;
}
// step B6
break;
t = (tsign >= 0) ? u : v;
}
if (k > 0)
u.leftShift(k);
return u;
}
/**
* Calculate GCD of a and b interpreted as unsigned integers.
*/
static int binaryGcd(int a, int b) {
if (b==0)
return a;
if (a==0)
return b;
// Right shift a & b till their last bits equal to 1.
a >>>= aZeros;
b >>>= bZeros;
while (a != b) {
if ((a+0x80000000) > (b+0x80000000)) { // a > b as unsigned
a -= b;
a >>>= Integer.numberOfTrailingZeros(a);
} else {
b -= a;
b >>>= Integer.numberOfTrailingZeros(b);
}
}
return a<<t;
}
/**
* Returns the modInverse of this mod p. This and p are not affected by
* the operation.
*/
// Modulus is odd, use Schroeppel's algorithm
if (p.isOdd())
return modInverse(p);
// Base and modulus are even, throw exception
if (isEven())
throw new ArithmeticException("BigInteger not invertible.");
// Get even part of modulus expressed as a power of 2
int powersOf2 = p.getLowestSetBit();
// Construct odd part of modulus
return modInverseMP2(powersOf2);
// Calculate 1/a mod oddMod
// Calculate 1/a mod evenMod
// Combine the results using Chinese Remainder Theorem
}
/*
* Calculate the multiplicative inverse of this mod 2^k.
*/
if (isEven())
throw new ArithmeticException("Non-invertible. (GCD != 1)");
if (k > 64)
return euclidModInverse(k);
if (k < 33) {
t = (k == 32 ? t : t & ((1 << k) - 1));
return new MutableBigInteger(t);
}
if (intLen > 1)
return result;
}
/*
* Returns the multiplicative inverse of val mod 2^32. Assumes val is odd.
*/
// Newton's iteration!
int t = val;
t *= 2 - val*t;
t *= 2 - val*t;
t *= 2 - val*t;
t *= 2 - val*t;
return t;
}
/*
* Calculate the multiplicative inverse of 2^k mod mod, where mod is odd.
*/
// Copy the mod to protect original
}
/**
* 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."
*/
MutableBigInteger f = new MutableBigInteger(this);
MutableBigInteger g = new MutableBigInteger(p);
SignedMutableBigInteger d = new SignedMutableBigInteger();
int k = 0;
// Right shift f k times until odd, left shift d k times
if (f.isEven()) {
int trailingZeros = f.getLowestSetBit();
k = trailingZeros;
}
// The Almost Inverse Algorithm
while(!f.isOne()) {
// If gcd(f, g) != 1, number is not invertible modulo mod
if (f.isZero())
throw new ArithmeticException("BigInteger not invertible.");
// If f < g exchange f, g and c, d
if (f.compare(g) < 0) {
}
// If f == g (mod 4)
f.subtract(g);
c.signedSubtract(d);
} else { // If f != g (mod 4)
f.add(g);
c.signedAdd(d);
}
// Right shift f k times until odd, left shift d k times
int trailingZeros = f.getLowestSetBit();
k += trailingZeros;
}
while (c.sign < 0)
c.signedAdd(p);
return fixup(c, p, k);
}
/*
* The Fixup Algorithm
* Calculates X such that X = C * 2^(-k) (mod P)
* Assumes C<P and P is odd.
*/
int k) {
// Set r to the multiplicative inverse of p mod 2^32
// V = R * c (mod 2^j)
// c = c + (v * p)
// c = c / 2^j
c.intLen--;
}
int numBits = k & 0x1f;
if (numBits != 0) {
// V = R * c (mod 2^j)
// c = c + (v * p)
// c = c / 2^j
c.rightShift(numBits);
}
// In theory, c may be greater than p at this point (Very rare!)
while (c.compare(p) >= 0)
c.subtract(p);
return c;
}
/**
* 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.
*/
b.leftShift(k);
MutableBigInteger a = new MutableBigInteger(this);
MutableBigInteger q = new MutableBigInteger();
MutableBigInteger r = b.divide(a, q);
MutableBigInteger swapper = b;
// swap b & r
b = r;
r = swapper;
while (!b.isOne()) {
r = a.divide(b, q);
if (r.intLen == 0)
throw new ArithmeticException("BigInteger not invertible.");
swapper = r;
a = swapper;
if (q.intLen == 1)
else
swapper = q;
q = temp;
if (a.isOne())
return t0;
r = b.divide(a, q);
if (r.intLen == 0)
throw new ArithmeticException("BigInteger not invertible.");
swapper = b;
b = r;
if (q.intLen == 1)
else
}
return mod;
}
}