diff -r d9d491a5a169 -r dd6d609861f0 jdk/src/share/classes/java/math/MutableBigInteger.java --- a/jdk/src/share/classes/java/math/MutableBigInteger.java Thu May 21 23:32:46 2009 -0700 +++ b/jdk/src/share/classes/java/math/MutableBigInteger.java Sun May 24 16:29:57 2009 -0700 @@ -41,6 +41,11 @@ * @since 1.3 */ +import java.util.Arrays; + +import static java.math.BigInteger.LONG_MASK; +import static java.math.BigDecimal.INFLATED; + class MutableBigInteger { /** * Holds the magnitude of this MutableBigInteger in big endian order. @@ -62,10 +67,13 @@ */ int offset = 0; + // Constants /** - * This mask is used to obtain the value of an int as if it were unsigned. + * 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. */ - private final static long LONG_MASK = 0xffffffffL; + static final MutableBigInteger ONE = new MutableBigInteger(1); // Constructors @@ -90,15 +98,6 @@ /** * Construct a new MutableBigInteger with the specified value array - * up to the specified length. - */ - MutableBigInteger(int[] val, int len) { - value = val; - intLen = len; - } - - /** - * Construct a new MutableBigInteger with the specified value array * up to the length of the array supplied. */ MutableBigInteger(int[] val) { @@ -111,8 +110,8 @@ * specified BigInteger. */ MutableBigInteger(BigInteger b) { - value = b.mag.clone(); - intLen = value.length; + intLen = b.mag.length; + value = Arrays.copyOf(b.mag, intLen); } /** @@ -121,10 +120,58 @@ */ MutableBigInteger(MutableBigInteger val) { intLen = val.intLen; - value = new int[intLen]; + value = Arrays.copyOfRange(val.value, val.offset, val.offset + intLen); + } + + /** + * 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; + } - for(int i=0; i 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 new BigDecimal(null, sign == -1 ? -v : v, scale, 0); } /** @@ -146,17 +193,21 @@ /** * Compare the magnitude of two MutableBigIntegers. Returns -1, 0 or 1 * as this MutableBigInteger is numerically less than, equal to, or - * greater than {@code b}. + * greater than b. */ final int compare(MutableBigInteger b) { - if (intLen < b.intLen) + int blen = b.intLen; + if (intLen < blen) return -1; - if (intLen > b.intLen) - return 1; + if (intLen > blen) + return 1; - for (int i=0; i b2) @@ -166,6 +217,46 @@ } /** + * 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. */ @@ -178,7 +269,7 @@ b = value[j+offset]; if (b==0) return -1; - return ((intLen-1-j)<<5) + BigInteger.trailingZeroCnt(b); + return ((intLen-1-j)<<5) + Integer.numberOfTrailingZeros(b); } /** @@ -270,13 +361,11 @@ * Sets this MutableBigInteger's value array to a copy of the specified * array. The intLen is set to the length of the new array. */ - void copyValue(MutableBigInteger val) { - int len = val.intLen; + void copyValue(MutableBigInteger src) { + int len = src.intLen; if (value.length < len) value = new int[len]; - - for(int i=0; i= bitsInHighWord) { this.primitiveLeftShift(32 - nBits); this.intLen--; @@ -379,7 +467,7 @@ return; int nInts = n >>> 5; int nBits = n&0x1F; - int bitsInHighWord = BigInteger.bitLen(value[offset]); + int bitsInHighWord = BigInteger.bitLengthForInt(value[offset]); // If shift can be done without moving words, do so if (n <= (32-bitsInHighWord)) { @@ -499,34 +587,41 @@ int[] result = (value.length < resultLen ? new int[resultLen] : value); int rstart = result.length-1; - long sum = 0; + 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) + (sum >>> 32); + (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--; - sum = (value[x+offset] & LONG_MASK) + (sum >>> 32); + 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) + (sum >>> 32); + sum = (addend.value[y+addend.offset] & LONG_MASK) + carry; result[rstart--] = (int)sum; + carry = sum >>> 32; } - if ((sum >>> 32) > 0) { // Result must grow in length + if (carry > 0) { // Result must grow in length resultLen++; if (result.length < resultLen) { int temp[] = new int[resultLen]; - for (int i=resultLen-1; i>0; i--) - temp[i] = result[i-1]; + // 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 { @@ -708,29 +803,26 @@ z.value = zval; } - /** + /** * 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. The value of this MutableBigInteger is the - * dividend at invocation but is replaced by the remainder. + * specified by divisor. + * + * @return the remainder of the division is returned. * - * NOTE: The value of this MutableBigInteger is modified by this method. */ - void divideOneWord(int divisor, MutableBigInteger quotient) { - long divLong = divisor & LONG_MASK; + int divideOneWord(int divisor, MutableBigInteger quotient) { + long divisorLong = divisor & LONG_MASK; // Special case of one word dividend if (intLen == 1) { - long remValue = value[offset] & LONG_MASK; - quotient.value[0] = (int) (remValue / divLong); - quotient.intLen = (quotient.value[0] == 0) ? 0 : 1; + long dividendValue = value[offset] & LONG_MASK; + int q = (int) (dividendValue / divisorLong); + int r = (int) (dividendValue - q * divisorLong); + quotient.value[0] = q; + quotient.intLen = (q == 0) ? 0 : 1; quotient.offset = 0; - - value[0] = (int) (remValue - (quotient.value[0] * divLong)); - offset = 0; - intLen = (value[0] == 0) ? 0 : 1; - - return; + return r; } if (quotient.value.length < intLen) @@ -739,15 +831,15 @@ quotient.intLen = intLen; // Normalize the divisor - int shift = 32 - BigInteger.bitLen(divisor); + int shift = Integer.numberOfLeadingZeros(divisor); int rem = value[offset]; long remLong = rem & LONG_MASK; - if (remLong < divLong) { + if (remLong < divisorLong) { quotient.value[0] = 0; } else { - quotient.value[0] = (int)(remLong/divLong); - rem = (int) (remLong - (quotient.value[0] * divLong)); + quotient.value[0] = (int)(remLong / divisorLong); + rem = (int) (remLong - (quotient.value[0] * divisorLong)); remLong = rem & LONG_MASK; } @@ -757,8 +849,8 @@ long dividendEstimate = (remLong<<32) | (value[offset + intLen - xlen] & LONG_MASK); if (dividendEstimate >= 0) { - qWord[0] = (int) (dividendEstimate/divLong); - qWord[1] = (int) (dividendEstimate - (qWord[0] * divLong)); + qWord[0] = (int) (dividendEstimate / divisorLong); + qWord[1] = (int) (dividendEstimate - qWord[0] * divisorLong); } else { divWord(qWord, dividendEstimate, divisor); } @@ -767,81 +859,110 @@ remLong = rem & LONG_MASK; } + quotient.normalize(); // Unnormalize if (shift > 0) - value[0] = rem %= divisor; + return rem % divisor; else - value[0] = rem; - intLen = (value[0] == 0) ? 0 : 1; - - quotient.normalize(); + return rem; } - /** - * Calculates the quotient and remainder of this div b and places them - * in the MutableBigInteger objects provided. + * 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 contents of a and b are not changed. + * It special cases one word divisors for speed. The content of b is not + * changed. * */ - void divide(MutableBigInteger b, - MutableBigInteger quotient, MutableBigInteger rem) { + MutableBigInteger divide(MutableBigInteger b, MutableBigInteger quotient) { if (b.intLen == 0) throw new ArithmeticException("BigInteger divide by zero"); // Dividend is zero if (intLen == 0) { - quotient.intLen = quotient.offset = rem.intLen = rem.offset = 0; - return; + quotient.intLen = quotient.offset; + return new MutableBigInteger(); } int cmp = compare(b); - // Dividend less than divisor if (cmp < 0) { quotient.intLen = quotient.offset = 0; - rem.copyValue(this); - return; + return new MutableBigInteger(this); } // Dividend equal to divisor if (cmp == 0) { quotient.value[0] = quotient.intLen = 1; - quotient.offset = rem.intLen = rem.offset = 0; - return; + quotient.offset = 0; + return new MutableBigInteger(); } quotient.clear(); - // Special case one word divisor if (b.intLen == 1) { - rem.copyValue(this); - rem.divideOneWord(b.value[b.offset], quotient); - return; + int r = divideOneWord(b.value[b.offset], quotient); + if (r == 0) + return new MutableBigInteger(); + return new MutableBigInteger(r); } // Copy divisor value to protect divisor - int[] d = new int[b.intLen]; - for(int i=0; i>> 32); + quotient.clear(); + // Special case on word divisor + if (d == 0) + return divideOneWord((int)v, quotient) & LONG_MASK; + else { + int[] div = new int[]{ d, (int)(v & LONG_MASK) }; + return divideMagnitude(div, quotient).toLong(); + } + } + + /** + * 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. + */ + private MutableBigInteger divideMagnitude(int[] divisor, + MutableBigInteger quotient) { // Remainder starts as dividend with space for a leading zero - if (rem.value.length < intLen +1) - rem.value = new int[intLen+1]; - - for (int i=0; i 0) { // First shift will not grow array - BigInteger.primitiveLeftShift(d, dlen, shift); + BigInteger.primitiveLeftShift(divisor, dlen, shift); // But this one might rem.leftShift(shift); } @@ -866,9 +987,9 @@ rem.intLen++; } - int dh = d[0]; + int dh = divisor[0]; long dhLong = dh & LONG_MASK; - int dl = d[1]; + int dl = divisor[1]; int[] qWord = new int[2]; // D2 Initialize j @@ -910,7 +1031,7 @@ qhat--; qrem = (int)((qrem & LONG_MASK) + dhLong); if ((qrem & LONG_MASK) >= dhLong) { - estProduct = (dl & LONG_MASK) * (qhat & LONG_MASK); + estProduct -= (dl & LONG_MASK); rs = ((qrem & LONG_MASK) << 32) | nl; if (unsignedLongCompare(estProduct, rs)) qhat--; @@ -920,12 +1041,12 @@ // D4 Multiply and subtract rem.value[j+rem.offset] = 0; - int borrow = mulsub(rem.value, d, qhat, dlen, j+rem.offset); + int borrow = mulsub(rem.value, divisor, qhat, dlen, j+rem.offset); // D5 Test remainder if (borrow + 0x80000000 > nh2) { // D6 Add back - divadd(d, rem.value, j+1+rem.offset); + divadd(divisor, rem.value, j+1+rem.offset); qhat--; } @@ -937,8 +1058,9 @@ if (shift > 0) rem.rightShift(shift); + quotient.normalize(); rem.normalize(); - quotient.normalize(); + return rem; } /** @@ -989,16 +1111,15 @@ // 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(), - r = new MutableBigInteger(); + MutableBigInteger q = new MutableBigInteger(); while (b.intLen != 0) { if (Math.abs(a.intLen - b.intLen) < 2) return a.binaryGCD(b); - a.divide(b, q, r); - MutableBigInteger swapper = a; - a = b; b = r; r = swapper; + MutableBigInteger r = a.divide(b, q); + a = b; + b = r; } return a; } @@ -1069,40 +1190,21 @@ if (a==0) return b; - int x; - int aZeros = 0; - while ((x = a & 0xff) == 0) { - a >>>= 8; - aZeros += 8; - } - int y = BigInteger.trailingZeroTable[x]; - aZeros += y; - a >>>= y; - - int bZeros = 0; - while ((x = b & 0xff) == 0) { - b >>>= 8; - bZeros += 8; - } - y = BigInteger.trailingZeroTable[x]; - bZeros += y; - b >>>= y; + // Right shift a & b till their last bits equal to 1. + int aZeros = Integer.numberOfTrailingZeros(a); + int bZeros = Integer.numberOfTrailingZeros(b); + a >>>= aZeros; + b >>>= bZeros; int t = (aZeros < bZeros ? aZeros : bZeros); while (a != b) { if ((a+0x80000000) > (b+0x80000000)) { // a > b as unsigned a -= b; - - while ((x = a & 0xff) == 0) - a >>>= 8; - a >>>= BigInteger.trailingZeroTable[x]; + a >>>= Integer.numberOfTrailingZeros(a); } else { b -= a; - - while ((x = b & 0xff) == 0) - b >>>= 8; - b >>>= BigInteger.trailingZeroTable[x]; + b >>>= Integer.numberOfTrailingZeros(b); } } return a<