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,11 +311,11 @@
*/
final int compareHalf(MutableBigInteger b) {
int blen = b.intLen;
int len = intLen;
if (len <= 0)
- return blen <=0 ? 0 : -1;
+ return blen <= 0 ? 0 : -1;
if (len > blen)
return 1;
if (len < blen - 1)
return -1;
int[] bval = b.value;
@@ -338,25 +338,25 @@
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 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--)
+ for (j=intLen-1; (j > 0) && (value[j+offset] == 0); j--)
;
b = value[j+offset];
- if (b==0)
+ if (b == 0)
return -1;
return ((intLen-1-j)<<5) + Integer.numberOfTrailingZeros(b);
}
/**
@@ -393,15 +393,15 @@
return;
int indexBound = index+intLen;
do {
index++;
- } while(index < indexBound && value[index]==0);
+ } while(index < indexBound && value[index] == 0);
int numZeros = index - offset;
intLen -= numZeros;
- offset = (intLen==0 ? 0 : offset+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,11 +418,11 @@
* 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++)
+ for(int i=0; i < intLen; i++)
result[i] = value[offset+i];
return result;
}
/**
@@ -504,11 +504,11 @@
* after the offset, and intLen + offset <= value.length.
*/
boolean isNormal() {
if (intLen + offset > value.length)
return false;
- if (intLen ==0)
+ if (intLen == 0)
return true;
return (value[offset] != 0);
}
/**
@@ -521,15 +521,16 @@
/**
* Like {@link #rightShift(int)} but {@code n} can be greater than the length of the number.
*/
void safeRightShift(int n) {
- if (n/32 >= intLen)
+ if (n/32 >= intLen) {
reset();
- else
+ } else {
rightShift(n);
}
+ }
/**
* Right shift this MutableBigInteger n bits. The MutableBigInteger is left
* in normal form.
*/
@@ -552,13 +553,14 @@
/**
* Like {@link #leftShift(int)} but {@code n} can be zero.
*/
void safeLeftShift(int n) {
- if (n > 0)
+ if (n > 0) {
leftShift(n);
}
+ }
/**
* Left shift this MutableBigInteger n bits.
*/
void leftShift(int n) {
@@ -584,22 +586,22 @@
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++)
+ 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++)
+ 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++)
+ for (int i=0; i < intLen; i++)
value[i] = value[offset+i];
- for (int i=intLen; i<newLen; i++)
+ for (int i=intLen; i < newLen; i++)
value[i] = 0;
offset = 0;
}
intLen = newLen;
if (nBits == 0)
@@ -672,11 +674,11 @@
* 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--) {
+ 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,11 +690,11 @@
* 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++) {
+ 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,20 +703,20 @@
/**
* Returns a {@code BigInteger} equal to the {@code n}
* low ints of this number.
*/
private BigInteger getLower(int n) {
- if (isZero())
+ if (isZero()) {
return BigInteger.ZERO;
- else if (intLen < n)
+ } else if (intLen < n) {
return toBigInteger(1);
- else {
+ } else {
// strip zeros
int len = n;
- while (len>0 && value[offset+intLen-len]==0)
+ while (len > 0 && value[offset+intLen-len] == 0)
len--;
- int sign = len>0 ? 1 : 0;
+ int sign = len > 0 ? 1 : 0;
return new BigInteger(Arrays.copyOfRange(value, offset+intLen-len, offset+intLen), sign);
}
}
/**
@@ -741,28 +743,28 @@
int rstart = result.length-1;
long sum;
long carry = 0;
// Add common parts of both numbers
- while(x>0 && y>0) {
+ 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) {
+ 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) {
+ while(y > 0) {
y--;
sum = (addend.value[y+addend.offset] & LONG_MASK) + carry;
result[rstart--] = (int)sum;
carry = sum >>> 32;
}
@@ -786,16 +788,17 @@
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}.
+ * 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())
+ 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,31 +806,32 @@
int rstart = result.length-1;
long sum;
long carry = 0;
// Add common parts of both numbers
- while(x>0 && y>0) {
+ while (x > 0 && y > 0) {
x--; y--;
- int bval = y+addend.offset<addend.value.length ? addend.value[y+addend.offset] : 0;
+ 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) {
+ while (x > 0) {
x--;
- if (carry == 0 && result == value && rstart == (x + offset))
+ 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) {
+ while (y > 0) {
y--;
- int bval = y+addend.offset<addend.value.length ? addend.value[y+addend.offset] : 0;
+ 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,11 +883,11 @@
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++)
+ for (int i=rstart+1-y+len; i < rstart+1; i++)
result[i] = 0;
value = result;
intLen = resultLen;
offset = result.length - resultLen;
@@ -930,19 +934,19 @@
int x = a.intLen;
int y = b.intLen;
int rstart = result.length - 1;
// Subtract common parts of both numbers
- while (y>0) {
+ 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) {
+ while (x > 0) {
x--;
diff = (a.value[x+a.offset] & LONG_MASK) - ((int)-(diff>>32));
result[rstart--] = (int)diff;
}
@@ -959,11 +963,11 @@
* operation was performed.
*/
private int difference(MutableBigInteger b) {
MutableBigInteger a = this;
int sign = a.compare(b);
- if (sign ==0)
+ if (sign == 0)
return 0;
if (sign < 0) {
MutableBigInteger tmp = a;
a = b;
b = tmp;
@@ -972,18 +976,18 @@
long diff = 0;
int x = a.intLen;
int y = b.intLen;
// Subtract common parts of both numbers
- while (y>0) {
+ 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) {
+ while (x > 0) {
x--;
diff = (a.value[a.offset+ x] & LONG_MASK) - ((int)-(diff>>32));
a.value[a.offset+x] = (int)diff;
}
@@ -1048,11 +1052,11 @@
return;
}
// Perform the multiplication word by word
long ylong = y & LONG_MASK;
- int[] zval = (z.value.length<intLen+1 ? new int[intLen + 1]
+ 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,15 +1146,17 @@
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)
+ if (intLen < BigInteger.BURNIKEL_ZIEGLER_THRESHOLD ||
+ b.intLen < BigInteger.BURNIKEL_ZIEGLER_THRESHOLD) {
return divideKnuth(b, quotient, needRemainder);
- else
+ } else {
return divideAndRemainderBurnikelZiegler(b, quotient);
}
+ }
/**
* @see #divideKnuth(MutableBigInteger, MutableBigInteger, boolean)
*/
MutableBigInteger divideKnuth(MutableBigInteger b, MutableBigInteger quotient) {
@@ -1234,13 +1240,13 @@
*/
MutableBigInteger divideAndRemainderBurnikelZiegler(MutableBigInteger b, MutableBigInteger quotient) {
int r = intLen;
int s = b.intLen;
- if (r < s)
+ if (r < s) {
return this;
- else {
+ } 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,12 +1260,13 @@
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)
+ 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,11 +1275,11 @@
// 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--) {
+ 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,12 +1307,13 @@
*/
private MutableBigInteger divide2n1n(MutableBigInteger b, MutableBigInteger quotient) {
int n = b.intLen;
// step 1: base case
- if (n%2!=0 || n<BigInteger.BURNIKEL_ZIEGLER_THRESHOLD)
+ 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,12 +1358,11 @@
// 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 {
+ } 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,20 +1398,23 @@
* @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)
+ if (blockStart >= intLen) {
return new MutableBigInteger();
+ }
int blockEnd;
- if (index == numBlocks-1)
+ if (index == numBlocks-1) {
blockEnd = intLen;
- else
+ } else {
blockEnd = (index+1) * blockLength;
- if (blockEnd > intLen)
+ }
+ if (blockEnd > intLen) {
return new MutableBigInteger();
+ }
int[] newVal = Arrays.copyOfRange(value, offset+intLen-blockEnd, offset+intLen-blockStart);
return new MutableBigInteger(newVal);
}
@@ -1471,11 +1481,11 @@
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) {
+ 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,11 +1534,11 @@
int dh = divisor[0];
long dhLong = dh & LONG_MASK;
int dl = divisor[1];
// D2 Initialize j
- for(int j=0; j<limit-1; j++) {
+ for (int j=0; j < limit-1; j++) {
// D3 Calculate qhat
// estimate qhat
int qhat = 0;
int qrem = 0;
boolean skipCorrection = false;
@@ -1648,11 +1658,11 @@
// Store the quotient digit
q[(limit - 1)] = qhat;
}
- if(needRemainder) {
+ if (needRemainder) {
// D8 Unnormalize
if (shift > 0)
rem.rightShift(shift);
rem.normalize();
}
@@ -1890,11 +1900,11 @@
u.rightShift(k);
v.rightShift(k);
}
// step B2
- boolean uOdd = (k==s1);
+ boolean uOdd = (k == s1);
MutableBigInteger t = uOdd ? v: u;
int tsign = uOdd ? -1 : 1;
int lb;
while ((lb = t.getLowestSetBit()) >= 0) {
@@ -1932,13 +1942,13 @@
/**
* Calculate GCD of a and b interpreted as unsigned integers.
*/
static int binaryGcd(int a, int b) {
- if (b==0)
+ if (b == 0)
return a;
- if (a==0)
+ 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,11 +2095,11 @@
d.leftShift(trailingZeros);
k = trailingZeros;
}
// The Almost Inverse Algorithm
- while(!f.isOne()) {
+ 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,11 +2140,11 @@
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++) {
+ 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);