n
-int number all of whose bits are ones.
* Used by Burnikel-Ziegler division.
* @param n number of ints in the value
array
* @return a number equal to ((1<<(32*n)))-1
*/
private void ones(int n) {
if (n > value.length)
value = new int[n];
Arrays.fill(value, -1);
offset = 0;
intLen = n;
}
/**
* Internal helper method to return the magnitude array. The caller is not
* supposed to modify the returned array.
*/
private int[] getMagnitudeArray() {
if (offset > 0 || value.length != intLen)
return Arrays.copyOfRange(value, offset, offset + intLen);
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() {
assert (intLen <= 2) : "this MutableBigInteger exceeds the range of long";
if (intLen == 0)
return 0;
long d = value[offset] & LONG_MASK;
return (intLen == 2) ? d << 32 | (value[offset + 1] & LONG_MASK) : d;
}
/**
* Convert this MutableBigInteger to a BigInteger object.
*/
BigInteger toBigInteger(int sign) {
if (intLen == 0 || sign == 0)
return BigInteger.ZERO;
return new BigInteger(getMagnitudeArray(), sign);
}
/**
* Converts this number to a nonnegative BigInteger
.
*/
BigInteger toBigInteger() {
normalize();
return toBigInteger(isZero() ? 0 : 1);
}
/**
* Convert this MutableBigInteger to BigDecimal object with the specified sign
* and scale.
*/
BigDecimal toBigDecimal(int sign, int scale) {
if (intLen == 0 || sign == 0)
return BigDecimal.zeroValueOf(scale);
int[] mag = getMagnitudeArray();
int len = mag.length;
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.
if (len > 2 || (d < 0 && len == 2))
return new BigDecimal(new BigInteger(mag, sign), INFLATED, scale, 0);
long v = (len == 2) ?
((mag[1] & LONG_MASK) | (d & LONG_MASK) << 32) :
d & LONG_MASK;
return BigDecimal.valueOf(sign == -1 ? -v : v, scale);
}
/**
* 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
*/
long toCompactValue(int sign) {
if (intLen == 0 || sign == 0)
return 0L;
int[] mag = getMagnitudeArray();
int len = mag.length;
int d = mag[0];
// If this MutableBigInteger can not be fitted into long, we need to
// make a BigInteger object for the resultant BigDecimal object.
if (len > 2 || (d < 0 && len == 2))
return INFLATED;
long v = (len == 2) ?
((mag[1] & LONG_MASK) | (d & LONG_MASK) << 32) :
d & LONG_MASK;
return sign == -1 ? -v : v;
}
/**
* Clear out a MutableBigInteger for reuse.
*/
void clear() {
offset = intLen = 0;
for (int index=0, n=value.length; index < n; index++)
value[index] = 0;
}
/**
* Set a MutableBigInteger to zero, removing its offset.
*/
void reset() {
offset = intLen = 0;
}
/**
* Compare the magnitude of two MutableBigIntegers. Returns -1, 0 or 1
* as this MutableBigInteger is numerically less than, equal to, or
* greater than b.
*/
final int compare(MutableBigInteger b) {
int blen = b.intLen;
if (intLen < blen)
return -1;
if (intLen > blen)
return 1;
// Add Integer.MIN_VALUE to make the comparison act as unsigned integer
// comparison.
int[] bval = b.value;
for (int i = offset, j = b.offset; i < intLen + offset; i++, j++) {
int b1 = value[i] + 0x80000000;
int b2 = bval[j] + 0x80000000;
if (b1 < b2)
return -1;
if (b1 > b2)
return 1;
}
return 0;
}
/**
* Returns a value equal to what b.leftShift(32*ints); return compare(b);
* would return, but doesn't change the value of b
.
*/
private int compareShifted(MutableBigInteger b, int ints) {
int blen = b.intLen;
int alen = intLen - ints;
if (alen < blen)
return -1;
if (alen > blen)
return 1;
// Add Integer.MIN_VALUE to make the comparison act as unsigned integer
// comparison.
int[] bval = b.value;
for (int i = offset, j = b.offset; i < alen + offset; i++, j++) {
int b1 = value[i] + 0x80000000;
int b2 = bval[j] + 0x80000000;
if (b1 < b2)
return -1;
if (b1 > b2)
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().
*/
final int compareHalf(MutableBigInteger b) {
int blen = b.intLen;
int len = intLen;
if (len <= 0)
return blen <=0 ? 0 : -1;
if (len > blen)
return 1;
if (len < blen - 1)
return -1;
int[] bval = b.value;
int bstart = 0;
int carry = 0;
// Only 2 cases left:len == blen or len == blen - 1
if (len != blen) { // len == blen - 1
if (bval[bstart] == 1) {
++bstart;
carry = 0x80000000;
} else
return -1;
}
// compare values with right-shifted values of b,
// carrying shifted-out bits across words
int[] val = value;
for (int i = offset, j = bstart; i < len + offset;) {
int bv = bval[j++];
long hb = ((bv >>> 1) + carry) & LONG_MASK;
long v = val[i++] & LONG_MASK;
if (v != hb)
return v < hb ? -1 : 1;
carry = (bv & 1) << 31; // carray will be either 0x80000000 or 0
}
return carry == 0? 0 : -1;
}
/**
* 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;
for (j=intLen-1; (j>0) && (value[j+offset]==0); j--)
;
b = value[j+offset];
if (b==0)
return -1;
return ((intLen-1-j)<<5) + Integer.numberOfTrailingZeros(b);
}
/**
* 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.
*/
private final int getInt(int index) {
return value[offset+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.
*/
private final long getLong(int index) {
return value[offset+index] & LONG_MASK;
}
/**
* 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;
}
int index = offset;
if (value[index] != 0)
return;
int indexBound = index+intLen;
do {
index++;
} while(index < indexBound && value[index]==0);
int numZeros = index - offset;
intLen -= numZeros;
offset = (intLen==0 ? 0 : offset+numZeros);
}
/**
* If this MutableBigInteger cannot hold len words, increase the size
* of the value array to len words.
*/
private final void ensureCapacity(int len) {
if (value.length < len) {
value = new int[len];
offset = 0;
intLen = len;
}
}
/**
* Convert this MutableBigInteger into an int array with no leading
* zeros, of a length that is equal to this MutableBigInteger's intLen.
*/
int[] toIntArray() {
int[] result = new int[intLen];
for(int i=0; in
can be grater than the length of the number.
*/
void safeRightShift(int n) {
if (n/32 >= intLen)
reset();
else
rightShift(n);
}
/**
* 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;
this.intLen -= nInts;
if (nBits == 0)
return;
int bitsInHighWord = BigInteger.bitLengthForInt(value[offset]);
if (nBits >= bitsInHighWord) {
this.primitiveLeftShift(32 - nBits);
this.intLen--;
} else {
primitiveRightShift(nBits);
}
}
/**
* Like {@link #leftShift(int)} but n
can be zero.
*/
void safeLeftShift(int n) {
if (n > 0)
leftShift(n);
}
/**
* 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;
int bitsInHighWord = BigInteger.bitLengthForInt(value[offset]);
// If shift can be done without moving words, do so
if (n <= (32-bitsInHighWord)) {
primitiveLeftShift(nBits);
return;
}
int newLen = intLen + nInts +1;
if (nBits <= (32-bitsInHighWord))
newLen--;
if (value.length < newLen) {
// The array must grow
int[] result = new int[newLen];
for (int i=0; iBigInteger
equal to the n
* low ints of this number.
*/
private BigInteger getLower(int n) {
if (isZero())
return BigInteger.ZERO;
else if (intLen < n)
return toBigInteger(1);
else {
// strip zeros
int len = n;
while (len>0 && value[offset+intLen-len]==0)
len--;
int sign = len>0 ? 1 : 0;
return new BigInteger(Arrays.copyOfRange(value, offset+intLen-len, offset+intLen), sign);
}
}
/**
* Discards all ints whose index is greater than n
.
*/
private void keepLower(int n) {
if (intLen >= n) {
offset += intLen - n;
intLen = n;
}
}
/**
* Adds the contents of two MutableBigInteger objects.The result
* is placed within this MutableBigInteger.
* The contents of the addend are not changed.
*/
void add(MutableBigInteger addend) {
int x = intLen;
int y = addend.intLen;
int resultLen = (intLen > addend.intLen ? intLen : addend.intLen);
int[] result = (value.length < resultLen ? new int[resultLen] : value);
int rstart = result.length-1;
long sum;
long carry = 0;
// Add common parts of both numbers
while(x>0 && y>0) {
x--; y--;
sum = (value[x+offset] & LONG_MASK) +
(addend.value[y+addend.offset] & LONG_MASK) + carry;
result[rstart--] = (int)sum;
carry = sum >>> 32;
}
// Add remainder of the longer number
while(x>0) {
x--;
if (carry == 0 && result == value && rstart == (x + offset))
return;
sum = (value[x+offset] & LONG_MASK) + carry;
result[rstart--] = (int)sum;
carry = sum >>> 32;
}
while(y>0) {
y--;
sum = (addend.value[y+addend.offset] & LONG_MASK) + carry;
result[rstart--] = (int)sum;
carry = sum >>> 32;
}
if (carry > 0) { // Result must grow in length
resultLen++;
if (result.length < resultLen) {
int temp[] = new int[resultLen];
// Result one word longer from carry-out; copy low-order
// bits into new result.
System.arraycopy(result, 0, temp, 1, result.length);
temp[0] = 1;
result = temp;
} else {
result[rstart--] = 1;
}
}
value = result;
intLen = resultLen;
offset = result.length - resultLen;
}
/**
* Adds the value of addend
shifted n
ints to the left.
* Has the same effect as addend.leftShift(32*ints); add(b);
* but doesn't change the value of b
.
*/
void addShifted(MutableBigInteger addend, int n) {
if (addend.isZero())
return;
int x = intLen;
int y = addend.intLen + n;
int resultLen = (intLen > y ? intLen : y);
int[] result = (value.length < resultLen ? new int[resultLen] : value);
int rstart = result.length-1;
long sum;
long carry = 0;
// Add common parts of both numbers
while(x>0 && y>0) {
x--; y--;
int bval = y+addend.offsetthis.intLen
must
* not be greater than n
. In other words, concatenates this
* and addend
.
*/
void addDisjoint(MutableBigInteger addend, int n) {
if (addend.isZero())
return;
int x = intLen;
int y = addend.intLen + n;
int resultLen = (intLen > y ? intLen : y);
int[] result;
if (value.length < resultLen)
result = new int[resultLen];
else {
result = value;
Arrays.fill(value, offset+intLen, value.length, 0);
}
int rstart = result.length-1;
// copy from this if needed
System.arraycopy(value, offset, result, rstart+1-x, x);
y -= x;
rstart -= x;
int len = Math.min(y, addend.value.length-addend.offset);
System.arraycopy(addend.value, addend.offset, result, rstart+1-y, len);
// zero the gap
for (int i=rstart+1-y+len; iaddend
.
*/
void addLower(MutableBigInteger addend, int n) {
MutableBigInteger a = new MutableBigInteger(addend);
if (a.offset + a.intLen >= n) {
a.offset = a.offset + a.intLen - n;
a.intLen = n;
}
a.normalize();
add(a);
}
/**
* Subtracts the smaller of this and b from the larger and places the
* result into this MutableBigInteger.
*/
int subtract(MutableBigInteger b) {
MutableBigInteger a = this;
int[] result = value;
int sign = a.compare(b);
if (sign == 0) {
reset();
return 0;
}
if (sign < 0) {
MutableBigInteger tmp = a;
a = b;
b = tmp;
}
int resultLen = a.intLen;
if (result.length < resultLen)
result = new int[resultLen];
long diff = 0;
int x = a.intLen;
int y = b.intLen;
int rstart = result.length - 1;
// Subtract common parts of both numbers
while (y>0) {
x--; y--;
diff = (a.value[x+a.offset] & LONG_MASK) -
(b.value[y+b.offset] & LONG_MASK) - ((int)-(diff>>32));
result[rstart--] = (int)diff;
}
// Subtract remainder of longer number
while (x>0) {
x--;
diff = (a.value[x+a.offset] & LONG_MASK) - ((int)-(diff>>32));
result[rstart--] = (int)diff;
}
value = result;
intLen = resultLen;
offset = value.length - resultLen;
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.
*/
private int difference(MutableBigInteger b) {
MutableBigInteger a = this;
int sign = a.compare(b);
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--;
diff = (a.value[a.offset+ x] & LONG_MASK) -
(b.value[b.offset+ y] & LONG_MASK) - ((int)-(diff>>32));
a.value[a.offset+x] = (int)diff;
}
// Subtract remainder of longer number
while (x>0) {
x--;
diff = (a.value[a.offset+ x] & LONG_MASK) - ((int)-(diff>>32));
a.value[a.offset+x] = (int)diff;
}
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.
*/
void multiply(MutableBigInteger y, MutableBigInteger z) {
int xLen = intLen;
int yLen = y.intLen;
int newLen = xLen + yLen;
// Put z into an appropriate state to receive product
if (z.value.length < newLen)
z.value = new int[newLen];
z.offset = 0;
z.intLen = newLen;
// The first iteration is hoisted out of the loop to avoid extra add
long carry = 0;
for (int j=yLen-1, k=yLen+xLen-1; j >= 0; j--, k--) {
long product = (y.value[j+y.offset] & LONG_MASK) *
(value[xLen-1+offset] & LONG_MASK) + carry;
z.value[k] = (int)product;
carry = product >>> 32;
}
z.value[xLen-1] = (int)carry;
// Perform the multiplication word by word
for (int i = xLen-2; i >= 0; i--) {
carry = 0;
for (int j=yLen-1, k=yLen+i; j >= 0; j--, k--) {
long product = (y.value[j+y.offset] & LONG_MASK) *
(value[i+offset] & LONG_MASK) +
(z.value[k] & LONG_MASK) + carry;
z.value[k] = (int)product;
carry = product >>> 32;
}
z.value[i] = (int)carry;
}
// Remove leading zeros from product
z.normalize();
}
/**
* Multiply the contents of this MutableBigInteger by the word y. The
* result is placed into z.
*/
void mul(int y, MutableBigInteger z) {
if (y == 1) {
z.copyValue(this);
return;
}
if (y == 0) {
z.clear();
return;
}
// Perform the multiplication word by word
long ylong = y & LONG_MASK;
int[] zval = (z.value.lengththis%b
using the
* Burnikel-Ziegler algorithm.
* 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.this
and b
must be nonnegative.
* @param b the divisor
* @param quotient output parameter for this/b
* @return the remainder
*/
MutableBigInteger divideAndRemainderBurnikelZiegler(MutableBigInteger b, MutableBigInteger quotient) {
int r = intLen;
int s = b.intLen;
if (r < s)
return this;
else {
// step 1: let m = min{2^k | (2^k)*BURNIKEL_ZIEGLER_THRESHOLD > s}
int m = 1 << (32-Integer.numberOfLeadingZeros(s/BigInteger.BURNIKEL_ZIEGLER_THRESHOLD));
int j = (s+m-1) / m; // step 2a: j = ceil(s/m)
int n = j * m; // step 2b: block length in 32-bit units
int n32 = 32 * n; // block length in bits
int sigma = Math.max(0, n32 - b.bitLength()); // step 3: sigma = max{T | (2^T)*B < beta^n}
MutableBigInteger bShifted = new MutableBigInteger(b);
bShifted.safeLeftShift(sigma); // step 4a: shift b so its length is a multiple of n
safeLeftShift(sigma); // step 4b: shift this by the same amount
// step 5: t is the number of blocks needed to accommodate this plus one additional bit
int t = (bitLength()+n32) / n32;
if (t < 2)
t = 2;
// step 6: conceptually split this into blocks a[t-1], ..., a[0]
MutableBigInteger a1 = getBlock(t-1, t, n); // the most significant block of this
// step 7: z[t-2] = [a[t-1], a[t-2]]
MutableBigInteger z = getBlock(t-2, t, n); // the second to most significant block
z.addDisjoint(a1, n); // z[t-2]
// do schoolbook division on blocks, dividing 2-block numbers by 1-block numbers
MutableBigInteger qi = new MutableBigInteger();
MutableBigInteger ri;
quotient.offset = quotient.intLen = 0;
for (int i=t-2; i>0; i--) {
// step 8a: compute (qi,ri) such that z=b*qi+ri
ri = z.divide2n1n(bShifted, qi);
// step 8b: z = [ri, a[i-1]]
z = getBlock(i-1, t, n); // a[i-1]
z.addDisjoint(ri, n);
quotient.addShifted(qi, i*n); // update q (part of step 9)
}
// final iteration of step 8: do the loop one more time for i=0 but leave z unchanged
ri = z.divide2n1n(bShifted, qi);
quotient.add(qi);
ri.rightShift(sigma); // step 9: this and b were shifted, so shift back
return ri;
}
}
/**
* This method implements algorithm 1 from pg. 4 of the Burnikel-Ziegler paper.
* It divides a 2n-digit number by a n-digit number.this
must be a nonnegative number such that this.bitLength() <= 2*b.bitLength()
* @param b a positive number such that b.bitLength()
is even
* @param quotient output parameter for this/b
* @return this%b
*/
private MutableBigInteger divide2n1n(MutableBigInteger b, MutableBigInteger quotient) {
int n = b.intLen;
// step 1: base case
if (n%2!=0 || nthis
must be a nonnegative number such that 2*this.bitLength() <= 3*b.bitLength()
* @param quotient output parameter for this/b
* @return this%b
*/
private MutableBigInteger divide3n2n(MutableBigInteger b, MutableBigInteger quotient) {
int n = b.intLen / 2; // half the length of b in ints
// step 1: view this as [a1,a2,a3] where each ai is n ints or less; let a12=[a1,a2]
MutableBigInteger a12 = new MutableBigInteger(this);
a12.safeRightShift(32*n);
// step 2: view b as [b1,b2] where each bi is n ints or less
MutableBigInteger b1 = new MutableBigInteger(b);
b1.safeRightShift(n * 32);
BigInteger b2 = b.getLower(n);
MutableBigInteger r;
MutableBigInteger d;
if (compareShifted(b, n) < 0) {
// step 3a: if a1MutableBigInteger
containing blockLength
ints from
* this
number, starting at index*blockLength
.this
number
* @param blockLength length of one block in units of 32 bits
* @return
*/
private MutableBigInteger getBlock(int index, int numBlocks, int blockLength) {
int blockStart = index * blockLength;
if (blockStart >= intLen)
return new MutableBigInteger();
int blockEnd;
if (index == numBlocks-1)
blockEnd = intLen;
else
blockEnd = (index+1) * blockLength;
if (blockEnd > intLen)
return new MutableBigInteger();
int[] newVal = Arrays.copyOfRange(value, offset+intLen-blockEnd, offset+intLen-blockStart);
return new MutableBigInteger(newVal);
}
/** @see BigInteger#bitLength() */
int bitLength() {
if (intLen == 0)
return 0;
return intLen*32 - Integer.numberOfLeadingZeros(value[offset]);
}
/**
* 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.
*/
long divide(long v, MutableBigInteger quotient) {
if (v == 0)
throw new ArithmeticException("BigInteger divide by zero");
// Dividend is zero
if (intLen == 0) {
quotient.intLen = quotient.offset = 0;
return 0;
}
if (v < 0)
v = -v;
int d = (int)(v >>> 32);
quotient.clear();
// Special case on word divisor
if (d == 0)
return divideOneWord((int)v, quotient) & LONG_MASK;
else {
return divideLongMagnitude(v, quotient).toLong();
}
}
private static void copyAndShift(int[] src, int srcFrom, int srcLen, int[] dst, int dstFrom, int shift) {
int n2 = 32 - shift;
int c=src[srcFrom];
for (int i=0; i < srcLen-1; i++) {
int b = c;
c = src[++srcFrom];
dst[dstFrom+i] = (b << shift) | (c >>> n2);
}
dst[dstFrom+srcLen-1] = c << shift;
}
/**
* Divide this MutableBigInteger by the divisor.
* The quotient will be placed into the provided quotient object &
* the remainder object is returned.
*/
private MutableBigInteger divideMagnitude(MutableBigInteger div,
MutableBigInteger quotient,
boolean needReminder ) {
// assert div.intLen > 1
// D1 normalize the divisor
int shift = Integer.numberOfLeadingZeros(div.value[div.offset]);
// Copy divisor value to protect divisor
final int dlen = div.intLen;
int[] divisor;
MutableBigInteger rem; // Remainder starts as dividend with space for a leading zero
if (shift > 0) {
divisor = new int[dlen];
copyAndShift(div.value,div.offset,dlen,divisor,0,shift);
if(Integer.numberOfLeadingZeros(value[offset])>=shift) {
int[] remarr = new int[intLen + 1];
rem = new MutableBigInteger(remarr);
rem.intLen = intLen;
rem.offset = 1;
copyAndShift(value,offset,intLen,remarr,1,shift);
} else {
int[] remarr = new int[intLen + 2];
rem = new MutableBigInteger(remarr);
rem.intLen = intLen+1;
rem.offset = 1;
int rFrom = offset;
int c=0;
int n2 = 32 - shift;
for (int i=1; i < intLen+1; i++,rFrom++) {
int b = c;
c = value[rFrom];
remarr[i] = (b << shift) | (c >>> n2);
}
remarr[intLen+1] = c << shift;
}
} else {
divisor = Arrays.copyOfRange(div.value, div.offset, div.offset + div.intLen);
rem = new MutableBigInteger(new int[intLen + 1]);
System.arraycopy(value, offset, rem.value, 1, intLen);
rem.intLen = intLen;
rem.offset = 1;
}
int nlen = rem.intLen;
// Set the quotient size
final int limit = nlen - dlen + 1;
if (quotient.value.length < limit) {
quotient.value = new int[limit];
quotient.offset = 0;
}
quotient.intLen = limit;
int[] q = quotient.value;
// Must insert leading 0 in rem if its length did not change
if (rem.intLen == nlen) {
rem.offset = 0;
rem.value[0] = 0;
rem.intLen++;
}
int dh = divisor[0];
long dhLong = dh & LONG_MASK;
int dl = divisor[1];
// D2 Initialize j
for(int j=0; j> 5; i