jdk-sandbox: comparison jdk/src/share/classes/java/math/MutableBigInteger.java

equal deleted inserted replaced

-:d9d491a5a169
+:dd6d609861f0
 * @see     BigInteger
 * @author  Michael McCloskey
 * @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.
 * The magnitude may start at an offset into the value array, and it may
 * end before the length of the value array.
 * The offset into the value array where the magnitude of this
 * MutableBigInteger begins.
 */
 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
-private final static long LONG_MASK = 0xffffffffL;
+* BigDecimal divideAndRound to increment the quotient. Use this constant
+* only when the method is not going to modify this object.
+*/
+static final MutableBigInteger ONE = new MutableBigInteger(1);
 // Constructors
 /**
 * The default constructor. An empty MutableBigInteger is created with
 value[0] = val;
 }
 /**
 * 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) {
 value = val;
 intLen = val.length;
 /**
 * Construct a new MutableBigInteger with a magnitude equal to the
 * specified BigInteger.
 */
 MutableBigInteger(BigInteger b) {
-value = b.mag.clone();
+intLen = b.mag.length;
-intLen = value.length;
+value = Arrays.copyOf(b.mag, intLen);
 }
 /**
 * Construct a new MutableBigInteger with a magnitude equal to the
 * specified MutableBigInteger.
 */
 MutableBigInteger(MutableBigInteger val) {
 intLen = val.intLen;
-value = new int[intLen];
+value = Arrays.copyOfRange(val.value, val.offset, val.offset + intLen);
+}
-for(int i=0; i<intLen; i++)
-value[i] = val.value[val.offset+i];
+/**
+* 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);
+}
+/**
+* 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.valueOf(0, 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 new BigDecimal(null, sign == -1 ? -v : v, scale, 0);
 }
 /**
 * Clear out a MutableBigInteger for reuse.
 */
 }
 /**
 * 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 <tt>b</tt>.
 */
 final int compare(MutableBigInteger b) {
-if (intLen < b.intLen)
+int blen = b.intLen;
+if (intLen < blen)
 return -1;
-if (intLen > b.intLen)
+if (intLen > blen)
 return 1;
-for (int i=0; i<intLen; i++) {
+// Add Integer.MIN_VALUE to make the comparison act as unsigned integer
-int b1 = value[offset+i]     + 0x80000000;
+// comparison.
-int b2 = b.value[b.offset+i] + 0x80000000;
+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;
+}
+/**
+* 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.
 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) + BigInteger.trailingZeroCnt(b);
+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
 /**
 * 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) {
+void copyValue(MutableBigInteger src) {
-int len = val.intLen;
+int len = src.intLen;
 if (value.length < len)
 value = new int[len];
+System.arraycopy(src.value, src.offset, value, 0, len);
-for(int i=0; i<len; i++)
-value[i] = val.value[val.offset+i];
 intLen = len;
 offset = 0;
 }
 /**
 */
 void copyValue(int[] val) {
 int len = val.length;
 if (value.length < len)
 value = new int[len];
-for(int i=0; i<len; i++)
+System.arraycopy(val, 0, value, 0, len);
-value[i] = val[i];
 intLen = len;
 offset = 0;
 }
 /**
 /**
 * Returns true iff this MutableBigInteger is odd.
 */
 boolean isOdd() {
-return ((value[offset + intLen - 1] & 1) == 1);
+return isZero() ? false : ((value[offset + intLen - 1] & 1) == 1);
 }
 /**
 * Returns true iff this MutableBigInteger is in normal form. A
 * MutableBigInteger is in normal form if it has no leading zeros
 /**
 * Returns a String representation of this MutableBigInteger in radix 10.
 */
 public String toString() {
-BigInteger b = new BigInteger(this, 1);
+BigInteger b = toBigInteger(1);
 return b.toString();
 }
 /**
 * Right shift this MutableBigInteger n bits. The MutableBigInteger is left
 int nInts = n >>> 5;
 int nBits = n & 0x1F;
 this.intLen -= nInts;
 if (nBits == 0)
 return;
-int bitsInHighWord = BigInteger.bitLen(value[offset]);
+int bitsInHighWord = BigInteger.bitLengthForInt(value[offset]);
 if (nBits >= bitsInHighWord) {
 this.primitiveLeftShift(32 - nBits);
 this.intLen--;
 } else {
 primitiveRightShift(nBits);
 */
 if (intLen == 0)
 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)) {
 primitiveLeftShift(nBits);
 return;
 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 = 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--)
+// Result one word longer from carry-out; copy low-order
-temp[i] = result[i-1];
+// bits into new result.
+System.arraycopy(result, 0, temp, 1, result.length);
 temp[0] = 1;
 result = temp;
 } else {
 result[rstart--] = 1;
 }
 zval[0] = (int)carry;
 }
 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
+* specified by divisor.
-* dividend at invocation but is replaced by the remainder.
 *
-* NOTE: The value of this MutableBigInteger is modified by this method.
+* @return the remainder of the division is returned.
-*/
+*
-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;
+long dividendValue = value[offset] & LONG_MASK;
-quotient.value[0] = (int) (remValue / divLong);
+int q = (int) (dividendValue / divisorLong);
-quotient.intLen = (quotient.value[0] == 0) ? 0 : 1;
+int r = (int) (dividendValue - q * divisorLong);
+quotient.value[0] = q;
+quotient.intLen = (q == 0) ? 0 : 1;
 quotient.offset = 0;
+return r;
-value[0] = (int) (remValue - (quotient.value[0] * divLong));
-offset = 0;
-intLen = (value[0] == 0) ? 0 : 1;
-return;
 }
 if (quotient.value.length < intLen)
 quotient.value = new int[intLen];
 quotient.offset = 0;
 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);
+quotient.value[0] = (int)(remLong / divisorLong);
-rem = (int) (remLong - (quotient.value[0] * divLong));
+rem = (int) (remLong - (quotient.value[0] * divisorLong));
 remLong = rem & LONG_MASK;
 }
 int xlen = intLen;
 int[] qWord = new int[2];
 while (--xlen > 0) {
 long dividendEstimate = (remLong<<32) |
 (value[offset + intLen - xlen] & LONG_MASK);
 if (dividendEstimate >= 0) {
-qWord[0] = (int) (dividendEstimate/divLong);
+qWord[0] = (int) (dividendEstimate / divisorLong);
-qWord[1] = (int) (dividendEstimate - (qWord[0] * divLong));
+qWord[1] = (int) (dividendEstimate - qWord[0] * divisorLong);
 } else {
 divWord(qWord, dividendEstimate, divisor);
 }
 quotient.value[intLen - xlen] = qWord[0];
 rem = qWord[1];
 remLong = rem & LONG_MASK;
 }
+quotient.normalize();
 // Unnormalize
 if (shift > 0)
-value[0] = rem %= divisor;
+return rem % divisor;
 else
-value[0] = rem;
+return rem;
-intLen = (value[0] == 0) ? 0 : 1;
+}
-quotient.normalize();
+/**
-}
+* Calculates the quotient of this div b and places the quotient in the
+* provided MutableBigInteger objects and the remainder object is returned.
-/**
-* Calculates the quotient and remainder of this div b and places them
-* in the MutableBigInteger objects provided.
 *
 * 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.
+* It special cases one word divisors for speed. The content of b is not
-* The contents of a and b are not changed.
+* changed.
 *
 */
-void divide(MutableBigInteger b,
+MutableBigInteger divide(MutableBigInteger b, MutableBigInteger quotient) {
-MutableBigInteger quotient, MutableBigInteger rem) {
 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;
+quotient.intLen = quotient.offset;
-return;
+return new MutableBigInteger();
 }
 int cmp = compare(b);
 // Dividend less than divisor
 if (cmp < 0) {
 quotient.intLen = quotient.offset = 0;
-rem.copyValue(this);
+return new MutableBigInteger(this);
-return;
 }
 // Dividend equal to divisor
 if (cmp == 0) {
 quotient.value[0] = quotient.intLen = 1;
-quotient.offset = rem.intLen = rem.offset = 0;
+quotient.offset = 0;
-return;
+return new MutableBigInteger();
 }
 quotient.clear();
 // Special case one word divisor
 if (b.intLen == 1) {
-rem.copyValue(this);
+int r = divideOneWord(b.value[b.offset], quotient);
-rem.divideOneWord(b.value[b.offset], quotient);
+if (r == 0)
-return;
+return new MutableBigInteger();
+return new MutableBigInteger(r);
 }
 // Copy divisor value to protect divisor
-int[] d = new int[b.intLen];
+int[] div = Arrays.copyOfRange(b.value, b.offset, b.offset + b.intLen);
-for(int i=0; i<b.intLen; i++)
+return divideMagnitude(div, quotient);
-d[i] = b.value[b.offset+i];
+}
-int dlen = b.intLen;
+/**
+* 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 {
+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)
+MutableBigInteger rem = new MutableBigInteger(new int[intLen + 1]);
-rem.value = new int[intLen+1];
+System.arraycopy(value, offset, rem.value, 1, intLen);
-for (int i=0; i<intLen; i++)
-rem.value[i+1] = value[i+offset];
 rem.intLen = intLen;
 rem.offset = 1;
 int nlen = rem.intLen;
 // Set the quotient size
+int dlen = divisor.length;
 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;
 // D1 normalize the divisor
-int shift = 32 - BigInteger.bitLen(d[0]);
+int shift = Integer.numberOfLeadingZeros(divisor[0]);
 if (shift > 0) {
 // First shift will not grow array
-BigInteger.primitiveLeftShift(d, dlen, shift);
+BigInteger.primitiveLeftShift(divisor, dlen, shift);
 // But this one might
 rem.leftShift(shift);
 }
 // Must insert leading 0 in rem if its length did not change
 rem.offset = 0;
 rem.value[0] = 0;
 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
 for(int j=0; j<limit; j++) {
 // D3 Calculate qhat
 if (unsignedLongCompare(estProduct, rs)) {
 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--;
 }
 }
 }
 // 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--;
 }
 // Store the quotient digit
 q[j] = qhat;
 // D8 Unnormalize
 if (shift > 0)
 rem.rightShift(shift);
+quotient.normalize();
 rem.normalize();
-quotient.normalize();
+return rem;
 }
 /**
 * Compare two longs as if they were unsigned.
 * Returns true iff one is bigger than two.
 */
 MutableBigInteger hybridGCD(MutableBigInteger b) {
 // 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(),
+MutableBigInteger q = new MutableBigInteger();
-r = new MutableBigInteger();
 while (b.intLen != 0) {
 if (Math.abs(a.intLen - b.intLen) < 2)
 return a.binaryGCD(b);
-a.divide(b, q, r);
+MutableBigInteger r = a.divide(b, q);
-MutableBigInteger swapper = a;
+a = b;
-a = b; b = r; r = swapper;
+b = r;
 }
 return a;
 }
 /**
 if (b==0)
 return a;
 if (a==0)
 return b;
-int x;
+// Right shift a & b till their last bits equal to 1.
-int aZeros = 0;
+int aZeros = Integer.numberOfTrailingZeros(a);
-while ((x = a & 0xff) == 0) {
+int bZeros = Integer.numberOfTrailingZeros(b);
-a >>>= 8;
+a >>>= aZeros;
-aZeros += 8;
+b >>>= bZeros;
-}
-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;
 int t = (aZeros < bZeros ? aZeros : bZeros);
 while (a != b) {
 if ((a+0x80000000) > (b+0x80000000)) {  // a > b as unsigned
 a -= b;
+a >>>= Integer.numberOfTrailingZeros(a);
-while ((x = a & 0xff) == 0)
-a >>>= 8;
-a >>>= BigInteger.trailingZeroTable[x];
 } else {
 b -= a;
+b >>>= Integer.numberOfTrailingZeros(b);
-while ((x = b & 0xff) == 0)
-b >>>= 8;
-b >>>= BigInteger.trailingZeroTable[x];
 }
 }
 return a<<t;
 }
 evenPart.multiply(oddMod, temp1);
 temp1.multiply(y2, temp2);
 result.add(temp2);
-result.divide(p, temp1, temp2);
+return result.divide(p, temp1);
-return temp2;
 }
 /*
 * Calculate the multiplicative inverse of this mod 2^k.
 */
 b.leftShift(k);
 MutableBigInteger mod = new MutableBigInteger(b);
 MutableBigInteger a = new MutableBigInteger(this);
 MutableBigInteger q = new MutableBigInteger();
-MutableBigInteger r = new MutableBigInteger();
+MutableBigInteger r = b.divide(a, q);
-b.divide(a, q, r);
+MutableBigInteger swapper = b;
-MutableBigInteger swapper = b; b = r; r = swapper;
+// swap b & r
+b = r;
+r = swapper;
 MutableBigInteger t1 = new MutableBigInteger(q);
 MutableBigInteger t0 = new MutableBigInteger(1);
 MutableBigInteger temp = new MutableBigInteger();
 while (!b.isOne()) {
-a.divide(b, q, r);
+r = a.divide(b, q);
 if (r.intLen == 0)
 throw new ArithmeticException("BigInteger not invertible.");
-swapper = r; r = a; a = swapper;
+swapper = r;
+a = swapper;
 if (q.intLen == 1)
 t1.mul(q.value[q.offset], temp);
 else
 q.multiply(t1, temp);
-swapper = q; q = temp; temp = swapper;
+swapper = q;
+q = temp;
+temp = swapper;
 t0.add(q);
 if (a.isOne())
 return t0;
-b.divide(a, q, r);
+r = b.divide(a, q);
 if (r.intLen == 0)
 throw new ArithmeticException("BigInteger not invertible.");
-swapper = b; b = r; r = swapper;
+swapper = b;
+b =  r;
 if (q.intLen == 1)
 t0.mul(q.value[q.offset], temp);
 else
 q.multiply(t0, temp);

changeset 2922	dd6d609861f0
parent 2	90ce3da70b43
child 5506	202f599c92aa