src/share/classes/java/math/MutableBigInteger.java
Print this page
rev 7663 : 8014319: Faster division of large integers
Summary: Implement Burnickel-Ziegler division algorithm in BigInteger
Reviewed-by: bpb
Contributed-by: Tim Buktu <tbuktu@hotmail.com>
rev 7664 : 8020641: Clean up some code style in recent BigInteger contributions
Summary: Some minor cleanup to adhere better to Java coding conventions.
Reviewed-by: darcy
Contributed-by: Brian Burkhalter <brian.burkhalter@oracle.com>
*** 311,321 ****
*/
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;
--- 311,321 ----
*/
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;
*** 338,362 ****
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);
}
/**
--- 338,362 ----
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);
}
/**
*** 393,407 ****
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.
--- 393,407 ----
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.
*** 418,428 ****
* 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; i<intLen; i++)
result[i] = value[offset+i];
return result;
}
/**
--- 418,428 ----
* 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; i < intLen; i++)
result[i] = value[offset+i];
return result;
}
/**
*** 504,514 ****
* after the offset, and intLen + offset <= value.length.
*/
boolean isNormal() {
if (intLen + offset > value.length)
return false;
! if (intLen ==0)
return true;
return (value[offset] != 0);
}
/**
--- 504,514 ----
* after the offset, and intLen + offset <= value.length.
*/
boolean isNormal() {
if (intLen + offset > value.length)
return false;
! if (intLen == 0)
return true;
return (value[offset] != 0);
}
/**
*** 521,535 ****
/**
* Like {@link #rightShift(int)} but {@code n} can be greater 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.
*/
--- 521,536 ----
/**
* Like {@link #rightShift(int)} but {@code n} can be greater 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.
*/
*** 552,564 ****
/**
* Like {@link #leftShift(int)} but {@code n} can be zero.
*/
void safeLeftShift(int n) {
! if (n > 0)
leftShift(n);
}
/**
* Left shift this MutableBigInteger n bits.
*/
void leftShift(int n) {
--- 553,566 ----
/**
* Like {@link #leftShift(int)} but {@code n} can be zero.
*/
void safeLeftShift(int n) {
! if (n > 0) {
leftShift(n);
}
+ }
/**
* Left shift this MutableBigInteger n bits.
*/
void leftShift(int n) {
*** 584,605 ****
if (nBits <= (32-bitsInHighWord))
newLen--;
if (value.length < newLen) {
// The array must grow
int[] result = new int[newLen];
! for (int i=0; i<intLen; i++)
result[i] = value[offset+i];
setValue(result, newLen);
} else if (value.length - offset >= newLen) {
// Use space on right
! for(int i=0; i<newLen - intLen; i++)
value[offset+intLen+i] = 0;
} else {
// Must use space on left
! for (int i=0; i<intLen; i++)
value[i] = value[offset+i];
! for (int i=intLen; i<newLen; i++)
value[i] = 0;
offset = 0;
}
intLen = newLen;
if (nBits == 0)
--- 586,607 ----
if (nBits <= (32-bitsInHighWord))
newLen--;
if (value.length < newLen) {
// The array must grow
int[] result = new int[newLen];
! for (int i=0; i < intLen; i++)
result[i] = value[offset+i];
setValue(result, newLen);
} else if (value.length - offset >= newLen) {
// Use space on right
! for(int i=0; i < newLen - intLen; i++)
value[offset+intLen+i] = 0;
} else {
// Must use space on left
! for (int i=0; i < intLen; i++)
value[i] = value[offset+i];
! for (int i=intLen; i < newLen; i++)
value[i] = 0;
offset = 0;
}
intLen = newLen;
if (nBits == 0)
*** 672,682 ****
* Assumes that intLen > 0, n > 0 for speed
*/
private final void primitiveRightShift(int n) {
int[] val = value;
int n2 = 32 - n;
! for (int i=offset+intLen-1, c=val[i]; i>offset; i--) {
int b = c;
c = val[i-1];
val[i] = (c << n2) | (b >>> n);
}
val[offset] >>>= n;
--- 674,684 ----
* Assumes that intLen > 0, n > 0 for speed
*/
private final void primitiveRightShift(int n) {
int[] val = value;
int n2 = 32 - n;
! for (int i=offset+intLen-1, c=val[i]; i > offset; i--) {
int b = c;
c = val[i-1];
val[i] = (c << n2) | (b >>> n);
}
val[offset] >>>= n;
*** 688,698 ****
* Assumes that intLen > 0, n > 0 for speed
*/
private final void primitiveLeftShift(int n) {
int[] val = value;
int n2 = 32 - n;
! for (int i=offset, c=val[i], m=i+intLen-1; i<m; i++) {
int b = c;
c = val[i+1];
val[i] = (b << n) | (c >>> n2);
}
val[offset+intLen-1] <<= n;
--- 690,700 ----
* Assumes that intLen > 0, n > 0 for speed
*/
private final void primitiveLeftShift(int n) {
int[] val = value;
int n2 = 32 - n;
! for (int i=offset, c=val[i], m=i+intLen-1; i < m; i++) {
int b = c;
c = val[i+1];
val[i] = (b << n) | (c >>> n2);
}
val[offset+intLen-1] <<= n;
*** 701,720 ****
/**
* Returns a {@code BigInteger} equal to the {@code 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);
}
}
/**
--- 703,722 ----
/**
* Returns a {@code BigInteger} equal to the {@code 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);
}
}
/**
*** 741,768 ****
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;
}
--- 743,770 ----
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;
}
*** 786,801 ****
offset = result.length - resultLen;
}
/**
* Adds the value of {@code addend} shifted {@code n} ints to the left.
! * Has the same effect as {@code addend.leftShift(32*ints); add(b);}
! * but doesn't change the value of {@code 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);
--- 788,804 ----
offset = result.length - resultLen;
}
/**
* 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}.
*/
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);
*** 803,833 ****
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.offset<addend.value.length ? addend.value[y+addend.offset] : 0;
sum = (value[x+offset] & LONG_MASK) +
(bval & 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--;
! int bval = y+addend.offset<addend.value.length ? addend.value[y+addend.offset] : 0;
sum = (bval & LONG_MASK) + carry;
result[rstart--] = (int)sum;
carry = sum >>> 32;
}
--- 806,837 ----
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.offset < addend.value.length ? addend.value[y+addend.offset] : 0;
sum = (value[x+offset] & LONG_MASK) +
(bval & 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--;
! int bval = y+addend.offset < addend.value.length ? addend.value[y+addend.offset] : 0;
sum = (bval & LONG_MASK) + carry;
result[rstart--] = (int)sum;
carry = sum >>> 32;
}
*** 879,889 ****
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; i<rstart+1; i++)
result[i] = 0;
value = result;
intLen = resultLen;
offset = result.length - resultLen;
--- 883,893 ----
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; i < rstart+1; i++)
result[i] = 0;
value = result;
intLen = resultLen;
offset = result.length - resultLen;
*** 930,948 ****
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;
}
--- 934,952 ----
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;
}
*** 959,969 ****
* 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;
--- 963,973 ----
* 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;
*** 972,989 ****
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;
}
--- 976,993 ----
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;
}
*** 1048,1058 ****
return;
}
// Perform the multiplication word by word
long ylong = y & LONG_MASK;
! int[] zval = (z.value.length<intLen+1 ? new int[intLen + 1]
: z.value);
long carry = 0;
for (int i = intLen-1; i >= 0; i--) {
long product = ylong * (value[i+offset] & LONG_MASK) + carry;
zval[i+1] = (int)product;
--- 1052,1062 ----
return;
}
// Perform the multiplication word by word
long ylong = y & LONG_MASK;
! int[] zval = (z.value.length < intLen+1 ? new int[intLen + 1]
: z.value);
long carry = 0;
for (int i = intLen-1; i >= 0; i--) {
long product = ylong * (value[i+offset] & LONG_MASK) + carry;
zval[i+1] = (int)product;
*** 1142,1156 ****
MutableBigInteger divide(MutableBigInteger b, MutableBigInteger quotient) {
return divide(b,quotient,true);
}
MutableBigInteger divide(MutableBigInteger b, MutableBigInteger quotient, boolean needRemainder) {
! if (intLen<BigInteger.BURNIKEL_ZIEGLER_THRESHOLD || b.intLen<BigInteger.BURNIKEL_ZIEGLER_THRESHOLD)
return divideKnuth(b, quotient, needRemainder);
! else
return divideAndRemainderBurnikelZiegler(b, quotient);
}
/**
* @see #divideKnuth(MutableBigInteger, MutableBigInteger, boolean)
*/
MutableBigInteger divideKnuth(MutableBigInteger b, MutableBigInteger quotient) {
--- 1146,1162 ----
MutableBigInteger divide(MutableBigInteger b, MutableBigInteger quotient) {
return divide(b,quotient,true);
}
MutableBigInteger divide(MutableBigInteger b, MutableBigInteger quotient, boolean needRemainder) {
! if (intLen < BigInteger.BURNIKEL_ZIEGLER_THRESHOLD ||
! b.intLen < BigInteger.BURNIKEL_ZIEGLER_THRESHOLD) {
return divideKnuth(b, quotient, needRemainder);
! } else {
return divideAndRemainderBurnikelZiegler(b, quotient);
}
+ }
/**
* @see #divideKnuth(MutableBigInteger, MutableBigInteger, boolean)
*/
MutableBigInteger divideKnuth(MutableBigInteger b, MutableBigInteger quotient) {
*** 1234,1246 ****
*/
MutableBigInteger divideAndRemainderBurnikelZiegler(MutableBigInteger b, MutableBigInteger quotient) {
int r = intLen;
int s = b.intLen;
! if (r < s)
return this;
! else {
// Unlike Knuth division, we don't check for common powers of two here because
// BZ already runs faster if both numbers contain powers of two and cancelling them has no
// additional benefit.
// step 1: let m = min{2^k | (2^k)*BURNIKEL_ZIEGLER_THRESHOLD > s}
--- 1240,1252 ----
*/
MutableBigInteger divideAndRemainderBurnikelZiegler(MutableBigInteger b, MutableBigInteger quotient) {
int r = intLen;
int s = b.intLen;
! if (r < s) {
return this;
! } else {
// Unlike Knuth division, we don't check for common powers of two here because
// BZ already runs faster if both numbers contain powers of two and cancelling them has no
// additional benefit.
// step 1: let m = min{2^k | (2^k)*BURNIKEL_ZIEGLER_THRESHOLD > s}
*** 1254,1265 ****
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]]
--- 1260,1272 ----
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]]
*** 1268,1278 ****
// 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]
--- 1275,1285 ----
// 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]
*** 1300,1311 ****
*/
private MutableBigInteger divide2n1n(MutableBigInteger b, MutableBigInteger quotient) {
int n = b.intLen;
// step 1: base case
! if (n%2!=0 || n<BigInteger.BURNIKEL_ZIEGLER_THRESHOLD)
return divideKnuth(b, quotient);
// step 2: view this as [a1,a2,a3,a4] where each ai is n/2 ints or less
MutableBigInteger aUpper = new MutableBigInteger(this);
aUpper.safeRightShift(32*(n/2)); // aUpper = [a1,a2,a3]
keepLower(n/2); // this = a4
--- 1307,1319 ----
*/
private MutableBigInteger divide2n1n(MutableBigInteger b, MutableBigInteger quotient) {
int n = b.intLen;
// step 1: base case
! if (n%2 != 0 || n < BigInteger.BURNIKEL_ZIEGLER_THRESHOLD) {
return divideKnuth(b, quotient);
+ }
// step 2: view this as [a1,a2,a3,a4] where each ai is n/2 ints or less
MutableBigInteger aUpper = new MutableBigInteger(this);
aUpper.safeRightShift(32*(n/2)); // aUpper = [a1,a2,a3]
keepLower(n/2); // this = a4
*** 1350,1361 ****
// step 3a: if a1<b1, let quotient=a12/b1 and r=a12%b1
r = a12.divide2n1n(b1, quotient);
// step 4: d=quotient*b2
d = new MutableBigInteger(quotient.toBigInteger().multiply(b2));
! }
! else {
// step 3b: if a1>=b1, let quotient=beta^n-1 and r=a12-b1*2^n+b1
quotient.ones(n);
a12.add(b1);
b1.leftShift(32*n);
a12.subtract(b1);
--- 1358,1368 ----
// step 3a: if a1<b1, let quotient=a12/b1 and r=a12%b1
r = a12.divide2n1n(b1, quotient);
// step 4: d=quotient*b2
d = new MutableBigInteger(quotient.toBigInteger().multiply(b2));
! } else {
// step 3b: if a1>=b1, let quotient=beta^n-1 and r=a12-b1*2^n+b1
quotient.ones(n);
a12.add(b1);
b1.leftShift(32*n);
a12.subtract(b1);
*** 1391,1410 ****
* @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);
}
--- 1398,1420 ----
* @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);
}
*** 1471,1481 ****
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);
--- 1481,1491 ----
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);
*** 1524,1534 ****
int dh = divisor[0];
long dhLong = dh & LONG_MASK;
int dl = divisor[1];
// D2 Initialize j
! for(int j=0; j<limit-1; j++) {
// D3 Calculate qhat
// estimate qhat
int qhat = 0;
int qrem = 0;
boolean skipCorrection = false;
--- 1534,1544 ----
int dh = divisor[0];
long dhLong = dh & LONG_MASK;
int dl = divisor[1];
// D2 Initialize j
! for (int j=0; j < limit-1; j++) {
// D3 Calculate qhat
// estimate qhat
int qhat = 0;
int qrem = 0;
boolean skipCorrection = false;
*** 1648,1658 ****
// Store the quotient digit
q[(limit - 1)] = qhat;
}
! if(needRemainder) {
// D8 Unnormalize
if (shift > 0)
rem.rightShift(shift);
rem.normalize();
}
--- 1658,1668 ----
// Store the quotient digit
q[(limit - 1)] = qhat;
}
! if (needRemainder) {
// D8 Unnormalize
if (shift > 0)
rem.rightShift(shift);
rem.normalize();
}
*** 1890,1900 ****
u.rightShift(k);
v.rightShift(k);
}
// step B2
! boolean uOdd = (k==s1);
MutableBigInteger t = uOdd ? v: u;
int tsign = uOdd ? -1 : 1;
int lb;
while ((lb = t.getLowestSetBit()) >= 0) {
--- 1900,1910 ----
u.rightShift(k);
v.rightShift(k);
}
// step B2
! boolean uOdd = (k == s1);
MutableBigInteger t = uOdd ? v: u;
int tsign = uOdd ? -1 : 1;
int lb;
while ((lb = t.getLowestSetBit()) >= 0) {
*** 1932,1944 ****
/**
* 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.
int aZeros = Integer.numberOfTrailingZeros(a);
int bZeros = Integer.numberOfTrailingZeros(b);
--- 1942,1954 ----
/**
* 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.
int aZeros = Integer.numberOfTrailingZeros(a);
int bZeros = Integer.numberOfTrailingZeros(b);
*** 2085,2095 ****
d.leftShift(trailingZeros);
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
--- 2095,2105 ----
d.leftShift(trailingZeros);
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
*** 2130,2140 ****
int k) {
MutableBigInteger temp = new MutableBigInteger();
// Set r to the multiplicative inverse of p mod 2^32
int r = -inverseMod32(p.value[p.offset+p.intLen-1]);
! for(int i=0, numWords = k >> 5; i<numWords; i++) {
// V = R * c (mod 2^j)
int v = r * c.value[c.offset + c.intLen-1];
// c = c + (v * p)
p.mul(v, temp);
c.add(temp);
--- 2140,2150 ----
int k) {
MutableBigInteger temp = new MutableBigInteger();
// Set r to the multiplicative inverse of p mod 2^32
int r = -inverseMod32(p.value[p.offset+p.intLen-1]);
! for (int i=0, numWords = k >> 5; i < numWords; i++) {
// V = R * c (mod 2^j)
int v = r * c.value[c.offset + c.intLen-1];
// c = c + (v * p)
p.mul(v, temp);
c.add(temp);