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);