--- a/jdk/src/share/classes/java/math/BigInteger.java Wed Jun 19 13:03:03 2013 +0100
+++ b/jdk/src/share/classes/java/math/BigInteger.java Wed Jun 19 08:59:39 2013 -0700
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1996, 2011, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1996, 2013, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -29,9 +29,12 @@
package java.math;
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.ObjectStreamField;
+import java.util.Arrays;
import java.util.Random;
-import java.io.*;
-import java.util.Arrays;
/**
* Immutable arbitrary-precision integers. All operations behave as if
@@ -94,6 +97,7 @@
* @see BigDecimal
* @author Josh Bloch
* @author Michael McCloskey
+ * @author Alan Eliasen
* @since JDK1.1
*/
@@ -174,6 +178,39 @@
*/
final static long LONG_MASK = 0xffffffffL;
+ /**
+ * The threshold value for using Karatsuba multiplication. If the number
+ * of ints in both mag arrays are greater than this number, then
+ * Karatsuba multiplication will be used. This value is found
+ * experimentally to work well.
+ */
+ private static final int KARATSUBA_THRESHOLD = 50;
+
+ /**
+ * The threshold value for using 3-way Toom-Cook multiplication.
+ * If the number of ints in each mag array is greater than the
+ * Karatsuba threshold, and the number of ints in at least one of
+ * the mag arrays is greater than this threshold, then Toom-Cook
+ * multiplication will be used.
+ */
+ private static final int TOOM_COOK_THRESHOLD = 75;
+
+ /**
+ * The threshold value for using Karatsuba squaring. If the number
+ * of ints in the number are larger than this value,
+ * Karatsuba squaring will be used. This value is found
+ * experimentally to work well.
+ */
+ private static final int KARATSUBA_SQUARE_THRESHOLD = 90;
+
+ /**
+ * The threshold value for using Toom-Cook squaring. If the number
+ * of ints in the number are larger than this value,
+ * Toom-Cook squaring will be used. This value is found
+ * experimentally to work well.
+ */
+ private static final int TOOM_COOK_SQUARE_THRESHOLD = 140;
+
//Constructors
/**
@@ -522,15 +559,16 @@
if (bitLength < 2)
throw new ArithmeticException("bitLength < 2");
- // The cutoff of 95 was chosen empirically for best performance
- prime = (bitLength < 95 ? smallPrime(bitLength, certainty, rnd)
+ prime = (bitLength < SMALL_PRIME_THRESHOLD
+ ? smallPrime(bitLength, certainty, rnd)
: largePrime(bitLength, certainty, rnd));
signum = 1;
mag = prime.mag;
}
// Minimum size in bits that the requested prime number has
- // before we use the large prime number generating algorithms
+ // before we use the large prime number generating algorithms.
+ // The cutoff of 95 was chosen empirically for best performance.
private static final int SMALL_PRIME_THRESHOLD = 95;
// Certainty required to meet the spec of probablePrime
@@ -553,7 +591,6 @@
if (bitLength < 2)
throw new ArithmeticException("bitLength < 2");
- // The cutoff of 95 was chosen empirically for best performance
return (bitLength < SMALL_PRIME_THRESHOLD ?
smallPrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd) :
largePrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd));
@@ -986,6 +1023,7 @@
private final static int MAX_CONSTANT = 16;
private static BigInteger posConst[] = new BigInteger[MAX_CONSTANT+1];
private static BigInteger negConst[] = new BigInteger[MAX_CONSTANT+1];
+
static {
for (int i = 1; i <= MAX_CONSTANT; i++) {
int[] magnitude = new int[1];
@@ -1015,6 +1053,11 @@
private static final BigInteger TWO = valueOf(2);
/**
+ * The BigInteger constant -1. (Not exported.)
+ */
+ private static final BigInteger NEGATIVE_ONE = valueOf(-1);
+
+ /**
* The BigInteger constant ten.
*
* @since 1.5
@@ -1290,17 +1333,29 @@
public BigInteger multiply(BigInteger val) {
if (val.signum == 0 || signum == 0)
return ZERO;
- int resultSign = signum == val.signum ? 1 : -1;
- if (val.mag.length == 1) {
- return multiplyByInt(mag,val.mag[0], resultSign);
+
+ int xlen = mag.length;
+ int ylen = val.mag.length;
+
+ if ((xlen < KARATSUBA_THRESHOLD) || (ylen < KARATSUBA_THRESHOLD))
+ {
+ int resultSign = signum == val.signum ? 1 : -1;
+ if (val.mag.length == 1) {
+ return multiplyByInt(mag,val.mag[0], resultSign);
+ }
+ if(mag.length == 1) {
+ return multiplyByInt(val.mag,mag[0], resultSign);
+ }
+ int[] result = multiplyToLen(mag, xlen,
+ val.mag, ylen, null);
+ result = trustedStripLeadingZeroInts(result);
+ return new BigInteger(result, resultSign);
}
- if(mag.length == 1) {
- return multiplyByInt(val.mag,mag[0], resultSign);
- }
- int[] result = multiplyToLen(mag, mag.length,
- val.mag, val.mag.length, null);
- result = trustedStripLeadingZeroInts(result);
- return new BigInteger(result, resultSign);
+ else
+ if ((xlen < TOOM_COOK_THRESHOLD) && (ylen < TOOM_COOK_THRESHOLD))
+ return multiplyKaratsuba(this, val);
+ else
+ return multiplyToomCook3(this, val);
}
private static BigInteger multiplyByInt(int[] x, int y, int sign) {
@@ -1402,6 +1457,272 @@
}
/**
+ * Multiplies two BigIntegers using the Karatsuba multiplication
+ * algorithm. This is a recursive divide-and-conquer algorithm which is
+ * more efficient for large numbers than what is commonly called the
+ * "grade-school" algorithm used in multiplyToLen. If the numbers to be
+ * multiplied have length n, the "grade-school" algorithm has an
+ * asymptotic complexity of O(n^2). In contrast, the Karatsuba algorithm
+ * has complexity of O(n^(log2(3))), or O(n^1.585). It achieves this
+ * increased performance by doing 3 multiplies instead of 4 when
+ * evaluating the product. As it has some overhead, should be used when
+ * both numbers are larger than a certain threshold (found
+ * experimentally).
+ *
+ * See: http://en.wikipedia.org/wiki/Karatsuba_algorithm
+ */
+ private static BigInteger multiplyKaratsuba(BigInteger x, BigInteger y)
+ {
+ int xlen = x.mag.length;
+ int ylen = y.mag.length;
+
+ // The number of ints in each half of the number.
+ int half = (Math.max(xlen, ylen)+1) / 2;
+
+ // xl and yl are the lower halves of x and y respectively,
+ // xh and yh are the upper halves.
+ BigInteger xl = x.getLower(half);
+ BigInteger xh = x.getUpper(half);
+ BigInteger yl = y.getLower(half);
+ BigInteger yh = y.getUpper(half);
+
+ BigInteger p1 = xh.multiply(yh); // p1 = xh*yh
+ BigInteger p2 = xl.multiply(yl); // p2 = xl*yl
+
+ // p3=(xh+xl)*(yh+yl)
+ BigInteger p3 = xh.add(xl).multiply(yh.add(yl));
+
+ // result = p1 * 2^(32*2*half) + (p3 - p1 - p2) * 2^(32*half) + p2
+ BigInteger result = p1.shiftLeft(32*half).add(p3.subtract(p1).subtract(p2)).shiftLeft(32*half).add(p2);
+
+ if (x.signum != y.signum)
+ return result.negate();
+ else
+ return result;
+ }
+
+ /**
+ * Multiplies two BigIntegers using a 3-way Toom-Cook multiplication
+ * algorithm. This is a recursive divide-and-conquer algorithm which is
+ * more efficient for large numbers than what is commonly called the
+ * "grade-school" algorithm used in multiplyToLen. If the numbers to be
+ * multiplied have length n, the "grade-school" algorithm has an
+ * asymptotic complexity of O(n^2). In contrast, 3-way Toom-Cook has a
+ * complexity of about O(n^1.465). It achieves this increased asymptotic
+ * performance by breaking each number into three parts and by doing 5
+ * multiplies instead of 9 when evaluating the product. Due to overhead
+ * (additions, shifts, and one division) in the Toom-Cook algorithm, it
+ * should only be used when both numbers are larger than a certain
+ * threshold (found experimentally). This threshold is generally larger
+ * than that for Karatsuba multiplication, so this algorithm is generally
+ * only used when numbers become significantly larger.
+ *
+ * The algorithm used is the "optimal" 3-way Toom-Cook algorithm outlined
+ * by Marco Bodrato.
+ *
+ * See: http://bodrato.it/toom-cook/
+ * http://bodrato.it/papers/#WAIFI2007
+ *
+ * "Towards Optimal Toom-Cook Multiplication for Univariate and
+ * Multivariate Polynomials in Characteristic 2 and 0." by Marco BODRATO;
+ * In C.Carlet and B.Sunar, Eds., "WAIFI'07 proceedings", p. 116-133,
+ * LNCS #4547. Springer, Madrid, Spain, June 21-22, 2007.
+ *
+ */
+ private static BigInteger multiplyToomCook3(BigInteger a, BigInteger b)
+ {
+ int alen = a.mag.length;
+ int blen = b.mag.length;
+
+ int largest = Math.max(alen, blen);
+
+ // k is the size (in ints) of the lower-order slices.
+ int k = (largest+2)/3; // Equal to ceil(largest/3)
+
+ // r is the size (in ints) of the highest-order slice.
+ int r = largest - 2*k;
+
+ // Obtain slices of the numbers. a2 and b2 are the most significant
+ // bits of the numbers a and b, and a0 and b0 the least significant.
+ BigInteger a0, a1, a2, b0, b1, b2;
+ a2 = a.getToomSlice(k, r, 0, largest);
+ a1 = a.getToomSlice(k, r, 1, largest);
+ a0 = a.getToomSlice(k, r, 2, largest);
+ b2 = b.getToomSlice(k, r, 0, largest);
+ b1 = b.getToomSlice(k, r, 1, largest);
+ b0 = b.getToomSlice(k, r, 2, largest);
+
+ BigInteger v0, v1, v2, vm1, vinf, t1, t2, tm1, da1, db1;
+
+ v0 = a0.multiply(b0);
+ da1 = a2.add(a0);
+ db1 = b2.add(b0);
+ vm1 = da1.subtract(a1).multiply(db1.subtract(b1));
+ da1 = da1.add(a1);
+ db1 = db1.add(b1);
+ v1 = da1.multiply(db1);
+ v2 = da1.add(a2).shiftLeft(1).subtract(a0).multiply(
+ db1.add(b2).shiftLeft(1).subtract(b0));
+ vinf = a2.multiply(b2);
+
+ /* The algorithm requires two divisions by 2 and one by 3.
+ All divisions are known to be exact, that is, they do not produce
+ remainders, and all results are positive. The divisions by 2 are
+ implemented as right shifts which are relatively efficient, leaving
+ only an exact division by 3, which is done by a specialized
+ linear-time algorithm. */
+ t2 = v2.subtract(vm1).exactDivideBy3();
+ tm1 = v1.subtract(vm1).shiftRight(1);
+ t1 = v1.subtract(v0);
+ t2 = t2.subtract(t1).shiftRight(1);
+ t1 = t1.subtract(tm1).subtract(vinf);
+ t2 = t2.subtract(vinf.shiftLeft(1));
+ tm1 = tm1.subtract(t2);
+
+ // Number of bits to shift left.
+ int ss = k*32;
+
+ BigInteger result = vinf.shiftLeft(ss).add(t2).shiftLeft(ss).add(t1).shiftLeft(ss).add(tm1).shiftLeft(ss).add(v0);
+
+ if (a.signum != b.signum)
+ return result.negate();
+ else
+ return result;
+ }
+
+
+ /**
+ * Returns a slice of a BigInteger for use in Toom-Cook multiplication.
+ *
+ * @param lowerSize The size of the lower-order bit slices.
+ * @param upperSize The size of the higher-order bit slices.
+ * @param slice The index of which slice is requested, which must be a
+ * number from 0 to size-1. Slice 0 is the highest-order bits, and slice
+ * size-1 are the lowest-order bits. Slice 0 may be of different size than
+ * the other slices.
+ * @param fullsize The size of the larger integer array, used to align
+ * slices to the appropriate position when multiplying different-sized
+ * numbers.
+ */
+ private BigInteger getToomSlice(int lowerSize, int upperSize, int slice,
+ int fullsize)
+ {
+ int start, end, sliceSize, len, offset;
+
+ len = mag.length;
+ offset = fullsize - len;
+
+ if (slice == 0)
+ {
+ start = 0 - offset;
+ end = upperSize - 1 - offset;
+ }
+ else
+ {
+ start = upperSize + (slice-1)*lowerSize - offset;
+ end = start + lowerSize - 1;
+ }
+
+ if (start < 0)
+ start = 0;
+ if (end < 0)
+ return ZERO;
+
+ sliceSize = (end-start) + 1;
+
+ if (sliceSize <= 0)
+ return ZERO;
+
+ // While performing Toom-Cook, all slices are positive and
+ // the sign is adjusted when the final number is composed.
+ if (start==0 && sliceSize >= len)
+ return this.abs();
+
+ int intSlice[] = new int[sliceSize];
+ System.arraycopy(mag, start, intSlice, 0, sliceSize);
+
+ return new BigInteger(trustedStripLeadingZeroInts(intSlice), 1);
+ }
+
+ /**
+ * Does an exact division (that is, the remainder is known to be zero)
+ * of the specified number by 3. This is used in Toom-Cook
+ * multiplication. This is an efficient algorithm that runs in linear
+ * time. If the argument is not exactly divisible by 3, results are
+ * undefined. Note that this is expected to be called with positive
+ * arguments only.
+ */
+ private BigInteger exactDivideBy3()
+ {
+ int len = mag.length;
+ int[] result = new int[len];
+ long x, w, q, borrow;
+ borrow = 0L;
+ for (int i=len-1; i>=0; i--)
+ {
+ x = (mag[i] & LONG_MASK);
+ w = x - borrow;
+ if (borrow > x) // Did we make the number go negative?
+ borrow = 1L;
+ else
+ borrow = 0L;
+
+ // 0xAAAAAAAB is the modular inverse of 3 (mod 2^32). Thus,
+ // the effect of this is to divide by 3 (mod 2^32).
+ // This is much faster than division on most architectures.
+ q = (w * 0xAAAAAAABL) & LONG_MASK;
+ result[i] = (int) q;
+
+ // Now check the borrow. The second check can of course be
+ // eliminated if the first fails.
+ if (q >= 0x55555556L)
+ {
+ borrow++;
+ if (q >= 0xAAAAAAABL)
+ borrow++;
+ }
+ }
+ result = trustedStripLeadingZeroInts(result);
+ return new BigInteger(result, signum);
+ }
+
+ /**
+ * Returns a new BigInteger representing n lower ints of the number.
+ * This is used by Karatsuba multiplication and Karatsuba squaring.
+ */
+ private BigInteger getLower(int n) {
+ int len = mag.length;
+
+ if (len <= n)
+ return this;
+
+ int lowerInts[] = new int[n];
+ System.arraycopy(mag, len-n, lowerInts, 0, n);
+
+ return new BigInteger(trustedStripLeadingZeroInts(lowerInts), 1);
+ }
+
+ /**
+ * Returns a new BigInteger representing mag.length-n upper
+ * ints of the number. This is used by Karatsuba multiplication and
+ * Karatsuba squaring.
+ */
+ private BigInteger getUpper(int n) {
+ int len = mag.length;
+
+ if (len <= n)
+ return ZERO;
+
+ int upperLen = len - n;
+ int upperInts[] = new int[upperLen];
+ System.arraycopy(mag, 0, upperInts, 0, upperLen);
+
+ return new BigInteger(trustedStripLeadingZeroInts(upperInts), 1);
+ }
+
+ // Squaring
+
+ /**
* Returns a BigInteger whose value is {@code (this<sup>2</sup>)}.
*
* @return {@code this<sup>2</sup>}
@@ -1409,8 +1730,18 @@
private BigInteger square() {
if (signum == 0)
return ZERO;
- int[] z = squareToLen(mag, mag.length, null);
- return new BigInteger(trustedStripLeadingZeroInts(z), 1);
+ int len = mag.length;
+
+ if (len < KARATSUBA_SQUARE_THRESHOLD)
+ {
+ int[] z = squareToLen(mag, len, null);
+ return new BigInteger(trustedStripLeadingZeroInts(z), 1);
+ }
+ else
+ if (len < TOOM_COOK_SQUARE_THRESHOLD)
+ return squareKaratsuba();
+ else
+ return squareToomCook3();
}
/**
@@ -1481,6 +1812,83 @@
}
/**
+ * Squares a BigInteger using the Karatsuba squaring algorithm. It should
+ * be used when both numbers are larger than a certain threshold (found
+ * experimentally). It is a recursive divide-and-conquer algorithm that
+ * has better asymptotic performance than the algorithm used in
+ * squareToLen.
+ */
+ private BigInteger squareKaratsuba()
+ {
+ int half = (mag.length+1) / 2;
+
+ BigInteger xl = getLower(half);
+ BigInteger xh = getUpper(half);
+
+ BigInteger xhs = xh.square(); // xhs = xh^2
+ BigInteger xls = xl.square(); // xls = xl^2
+
+ // xh^2 << 64 + (((xl+xh)^2 - (xh^2 + xl^2)) << 32) + xl^2
+ return xhs.shiftLeft(half*32).add(xl.add(xh).square().subtract(xhs.add(xls))).shiftLeft(half*32).add(xls);
+ }
+
+ /**
+ * Squares a BigInteger using the 3-way Toom-Cook squaring algorithm. It
+ * should be used when both numbers are larger than a certain threshold
+ * (found experimentally). It is a recursive divide-and-conquer algorithm
+ * that has better asymptotic performance than the algorithm used in
+ * squareToLen or squareKaratsuba.
+ */
+ private BigInteger squareToomCook3()
+ {
+ int len = mag.length;
+
+ // k is the size (in ints) of the lower-order slices.
+ int k = (len+2)/3; // Equal to ceil(largest/3)
+
+ // r is the size (in ints) of the highest-order slice.
+ int r = len - 2*k;
+
+ // Obtain slices of the numbers. a2 is the most significant
+ // bits of the number, and a0 the least significant.
+ BigInteger a0, a1, a2;
+ a2 = getToomSlice(k, r, 0, len);
+ a1 = getToomSlice(k, r, 1, len);
+ a0 = getToomSlice(k, r, 2, len);
+ BigInteger v0, v1, v2, vm1, vinf, t1, t2, tm1, da1;
+
+ v0 = a0.square();
+ da1 = a2.add(a0);
+ vm1 = da1.subtract(a1).square();
+ da1 = da1.add(a1);
+ v1 = da1.square();
+ vinf = a2.square();
+ v2 = da1.add(a2).shiftLeft(1).subtract(a0).square();
+
+ /* The algorithm requires two divisions by 2 and one by 3.
+ All divisions are known to be exact, that is, they do not produce
+ remainders, and all results are positive. The divisions by 2 are
+ implemented as right shifts which are relatively efficient, leaving
+ only a division by 3.
+ The division by 3 is done by an optimized algorithm for this case.
+ */
+ t2 = v2.subtract(vm1).exactDivideBy3();
+ tm1 = v1.subtract(vm1).shiftRight(1);
+ t1 = v1.subtract(v0);
+ t2 = t2.subtract(t1).shiftRight(1);
+ t1 = t1.subtract(tm1).subtract(vinf);
+ t2 = t2.subtract(vinf.shiftLeft(1));
+ tm1 = tm1.subtract(t2);
+
+ // Number of bits to shift left.
+ int ss = k*32;
+
+ return vinf.shiftLeft(ss).add(t2).shiftLeft(ss).add(t1).shiftLeft(ss).add(tm1).shiftLeft(ss).add(v0);
+ }
+
+ // Division
+
+ /**
* Returns a BigInteger whose value is {@code (this / val)}.
*
* @param val value by which this BigInteger is to be divided.
@@ -1549,23 +1957,100 @@
if (signum==0)
return (exponent==0 ? ONE : this);
- // Perform exponentiation using repeated squaring trick
- int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1);
- int[] baseToPow2 = this.mag;
- int[] result = {1};
-
- while (exponent != 0) {
- if ((exponent & 1)==1) {
- result = multiplyToLen(result, result.length,
- baseToPow2, baseToPow2.length, null);
- result = trustedStripLeadingZeroInts(result);
+ BigInteger partToSquare = this.abs();
+
+ // Factor out powers of two from the base, as the exponentiation of
+ // these can be done by left shifts only.
+ // The remaining part can then be exponentiated faster. The
+ // powers of two will be multiplied back at the end.
+ int powersOfTwo = partToSquare.getLowestSetBit();
+
+ int remainingBits;
+
+ // Factor the powers of two out quickly by shifting right, if needed.
+ if (powersOfTwo > 0)
+ {
+ partToSquare = partToSquare.shiftRight(powersOfTwo);
+ remainingBits = partToSquare.bitLength();
+ if (remainingBits == 1) // Nothing left but +/- 1?
+ if (signum<0 && (exponent&1)==1)
+ return NEGATIVE_ONE.shiftLeft(powersOfTwo*exponent);
+ else
+ return ONE.shiftLeft(powersOfTwo*exponent);
+ }
+ else
+ {
+ remainingBits = partToSquare.bitLength();
+ if (remainingBits == 1) // Nothing left but +/- 1?
+ if (signum<0 && (exponent&1)==1)
+ return NEGATIVE_ONE;
+ else
+ return ONE;
+ }
+
+ // This is a quick way to approximate the size of the result,
+ // similar to doing log2[n] * exponent. This will give an upper bound
+ // of how big the result can be, and which algorithm to use.
+ int scaleFactor = remainingBits * exponent;
+
+ // Use slightly different algorithms for small and large operands.
+ // See if the result will safely fit into a long. (Largest 2^63-1)
+ if (partToSquare.mag.length==1 && scaleFactor <= 62)
+ {
+ // Small number algorithm. Everything fits into a long.
+ int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1);
+ long result = 1;
+ long baseToPow2 = partToSquare.mag[0] & LONG_MASK;
+
+ int workingExponent = exponent;
+
+ // Perform exponentiation using repeated squaring trick
+ while (workingExponent != 0) {
+ if ((workingExponent & 1)==1)
+ result = result * baseToPow2;
+
+ if ((workingExponent >>>= 1) != 0)
+ baseToPow2 = baseToPow2 * baseToPow2;
}
- if ((exponent >>>= 1) != 0) {
- baseToPow2 = squareToLen(baseToPow2, baseToPow2.length, null);
- baseToPow2 = trustedStripLeadingZeroInts(baseToPow2);
+
+ // Multiply back the powers of two (quickly, by shifting left)
+ if (powersOfTwo > 0)
+ {
+ int bitsToShift = powersOfTwo*exponent;
+ if (bitsToShift + scaleFactor <= 62) // Fits in long?
+ return valueOf((result << bitsToShift) * newSign);
+ else
+ return valueOf(result*newSign).shiftLeft(bitsToShift);
}
+ else
+ return valueOf(result*newSign);
}
- return new BigInteger(result, newSign);
+ else
+ {
+ // Large number algorithm. This is basically identical to
+ // the algorithm above, but calls multiply() and square()
+ // which may use more efficient algorithms for large numbers.
+ BigInteger answer = ONE;
+
+ int workingExponent = exponent;
+ // Perform exponentiation using repeated squaring trick
+ while (workingExponent != 0) {
+ if ((workingExponent & 1)==1)
+ answer = answer.multiply(partToSquare);
+
+ if ((workingExponent >>>= 1) != 0)
+ partToSquare = partToSquare.square();
+ }
+ // Multiply back the (exponentiated) powers of two (quickly,
+ // by shifting left)
+ if (powersOfTwo > 0)
+ answer = answer.shiftLeft(powersOfTwo*exponent);
+
+ if (signum<0 && (exponent&1)==1)
+ return answer.negate();
+ else
+ return answer;
+ }
}
/**
@@ -2117,7 +2602,7 @@
* Perform exponentiation using repeated squaring trick, chopping off
* high order bits as indicated by modulus.
*/
- BigInteger result = valueOf(1);
+ BigInteger result = ONE;
BigInteger baseToPow2 = this.mod2(p);
int expOffset = 0;
@@ -2850,6 +3335,7 @@
return buf.toString();
}
+
/* zero[i] is a string of i consecutive zeros. */
private static String zeros[] = new String[64];
static {
@@ -3218,21 +3704,21 @@
* little-endian binary representation of the magnitude (int 0 is the
* least significant). If the magnitude is zero, return value is undefined.
*/
- private int firstNonzeroIntNum() {
- int fn = firstNonzeroIntNum - 2;
- if (fn == -2) { // firstNonzeroIntNum not initialized yet
- fn = 0;
-
- // Search for the first nonzero int
- int i;
- int mlen = mag.length;
- for (i = mlen - 1; i >= 0 && mag[i] == 0; i--)
- ;
- fn = mlen - i - 1;
- firstNonzeroIntNum = fn + 2; // offset by two to initialize
- }
- return fn;
- }
+ private int firstNonzeroIntNum() {
+ int fn = firstNonzeroIntNum - 2;
+ if (fn == -2) { // firstNonzeroIntNum not initialized yet
+ fn = 0;
+
+ // Search for the first nonzero int
+ int i;
+ int mlen = mag.length;
+ for (i = mlen - 1; i >= 0 && mag[i] == 0; i--)
+ ;
+ fn = mlen - i - 1;
+ firstNonzeroIntNum = fn + 2; // offset by two to initialize
+ }
+ return fn;
+ }
/** use serialVersionUID from JDK 1.1. for interoperability */
private static final long serialVersionUID = -8287574255936472291L;
--- a/jdk/test/java/math/BigInteger/BigIntegerTest.java Wed Jun 19 13:03:03 2013 +0100
+++ b/jdk/test/java/math/BigInteger/BigIntegerTest.java Wed Jun 19 08:59:39 2013 -0700
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1998, 2011, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1998, 2013, Oracle and/or its affiliates. All rights reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* This code is free software; you can redistribute it and/or modify it
@@ -23,15 +23,19 @@
/*
* @test
- * @bug 4181191 4161971 4227146 4194389 4823171 4624738 4812225
+ * @bug 4181191 4161971 4227146 4194389 4823171 4624738 4812225 4837946
* @summary tests methods in BigInteger
* @run main/timeout=400 BigIntegerTest
* @author madbot
*/
-import java.util.Random;
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.FileOutputStream;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
import java.math.BigInteger;
-import java.io.*;
+import java.util.Random;
/**
* This is a simple test class created to ensure that the results
@@ -48,21 +52,42 @@
*
*/
public class BigIntegerTest {
+ //
+ // Bit large number thresholds based on the int thresholds
+ // defined in BigInteger itself:
+ //
+ // KARATSUBA_THRESHOLD = 50 ints = 1600 bits
+ // TOOM_COOK_THRESHOLD = 75 ints = 2400 bits
+ // KARATSUBA_SQUARE_THRESHOLD = 90 ints = 2880 bits
+ // TOOM_COOK_SQUARE_THRESHOLD = 140 ints = 4480 bits
+ //
+ static final int BITS_KARATSUBA = 1600;
+ static final int BITS_TOOM_COOK = 2400;
+ static final int BITS_KARATSUBA_SQUARE = 2880;
+ static final int BITS_TOOM_COOK_SQUARE = 4480;
+
+ static final int ORDER_SMALL = 60;
+ static final int ORDER_MEDIUM = 100;
+ // #bits for testing Karatsuba and Burnikel-Ziegler
+ static final int ORDER_KARATSUBA = 1800;
+ // #bits for testing Toom-Cook
+ static final int ORDER_TOOM_COOK = 3000;
+ // #bits for testing Karatsuba squaring
+ static final int ORDER_KARATSUBA_SQUARE = 3200;
+ // #bits for testing Toom-Cook squaring
+ static final int ORDER_TOOM_COOK_SQUARE = 4600;
+
static Random rnd = new Random();
static int size = 1000; // numbers per batch
static boolean failure = false;
- // Some variables for sizing test numbers in bits
- private static int order1 = 100;
- private static int order2 = 60;
- private static int order3 = 30;
-
- public static void pow() {
+ public static void pow(int order) {
int failCount1 = 0;
for (int i=0; i<size; i++) {
- int power = rnd.nextInt(6) +2;
- BigInteger x = fetchNumber(order1);
+ // Test identity x^power == x*x*x ... *x
+ int power = rnd.nextInt(6) + 2;
+ BigInteger x = fetchNumber(order);
BigInteger y = x.pow(power);
BigInteger z = x;
@@ -72,22 +97,39 @@
if (!y.equals(z))
failCount1++;
}
- report("pow", failCount1);
+ report("pow for " + order + " bits", failCount1);
}
- public static void arithmetic() {
+ public static void square(int order) {
+ int failCount1 = 0;
+
+ for (int i=0; i<size; i++) {
+ // Test identity x^2 == x*x
+ BigInteger x = fetchNumber(order);
+ BigInteger xx = x.multiply(x);
+ BigInteger x2 = x.pow(2);
+
+ if (!x2.equals(xx))
+ failCount1++;
+ }
+ report("square for " + order + " bits", failCount1);
+ }
+
+ public static void arithmetic(int order) {
int failCount = 0;
for (int i=0; i<size; i++) {
- BigInteger x = fetchNumber(order1);
+ BigInteger x = fetchNumber(order);
while(x.compareTo(BigInteger.ZERO) != 1)
- x = fetchNumber(order1);
- BigInteger y = fetchNumber(order1/2);
+ x = fetchNumber(order);
+ BigInteger y = fetchNumber(order/2);
while(x.compareTo(y) == -1)
- y = fetchNumber(order1/2);
+ y = fetchNumber(order/2);
if (y.equals(BigInteger.ZERO))
y = y.add(BigInteger.ONE);
+ // Test identity ((x/y))*y + x%y - x == 0
+ // using separate divide() and remainder()
BigInteger baz = x.divide(y);
baz = baz.multiply(y);
baz = baz.add(x.remainder(y));
@@ -95,19 +137,21 @@
if (!baz.equals(BigInteger.ZERO))
failCount++;
}
- report("Arithmetic I", failCount);
+ report("Arithmetic I for " + order + " bits", failCount);
failCount = 0;
for (int i=0; i<100; i++) {
- BigInteger x = fetchNumber(order1);
+ BigInteger x = fetchNumber(order);
while(x.compareTo(BigInteger.ZERO) != 1)
- x = fetchNumber(order1);
- BigInteger y = fetchNumber(order1/2);
+ x = fetchNumber(order);
+ BigInteger y = fetchNumber(order/2);
while(x.compareTo(y) == -1)
- y = fetchNumber(order1/2);
+ y = fetchNumber(order/2);
if (y.equals(BigInteger.ZERO))
y = y.add(BigInteger.ONE);
+ // Test identity ((x/y))*y + x%y - x == 0
+ // using divideAndRemainder()
BigInteger baz[] = x.divideAndRemainder(y);
baz[0] = baz[0].multiply(y);
baz[0] = baz[0].add(baz[1]);
@@ -115,7 +159,118 @@
if (!baz[0].equals(BigInteger.ZERO))
failCount++;
}
- report("Arithmetic II", failCount);
+ report("Arithmetic II for " + order + " bits", failCount);
+ }
+
+ /**
+ * Sanity test for Karatsuba and 3-way Toom-Cook multiplication.
+ * For each of the Karatsuba and 3-way Toom-Cook multiplication thresholds,
+ * construct two factors each with a mag array one element shorter than the
+ * threshold, and with the most significant bit set and the rest of the bits
+ * random. Each of these numbers will therefore be below the threshold but
+ * if shifted left be above the threshold. Call the numbers 'u' and 'v' and
+ * define random shifts 'a' and 'b' in the range [1,32]. Then we have the
+ * identity
+ * <pre>
+ * (u << a)*(v << b) = (u*v) << (a + b)
+ * </pre>
+ * For Karatsuba multiplication, the right hand expression will be evaluated
+ * using the standard naive algorithm, and the left hand expression using
+ * the Karatsuba algorithm. For 3-way Toom-Cook multiplication, the right
+ * hand expression will be evaluated using Karatsuba multiplication, and the
+ * left hand expression using 3-way Toom-Cook multiplication.
+ */
+ public static void multiplyLarge() {
+ int failCount = 0;
+
+ BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA - 32 - 1);
+ for (int i=0; i<size; i++) {
+ BigInteger x = fetchNumber(BITS_KARATSUBA - 32 - 1);
+ BigInteger u = base.add(x);
+ int a = 1 + rnd.nextInt(31);
+ BigInteger w = u.shiftLeft(a);
+
+ BigInteger y = fetchNumber(BITS_KARATSUBA - 32 - 1);
+ BigInteger v = base.add(y);
+ int b = 1 + rnd.nextInt(32);
+ BigInteger z = v.shiftLeft(b);
+
+ BigInteger multiplyResult = u.multiply(v).shiftLeft(a + b);
+ BigInteger karatsubaMultiplyResult = w.multiply(z);
+
+ if (!multiplyResult.equals(karatsubaMultiplyResult)) {
+ failCount++;
+ }
+ }
+
+ report("multiplyLarge Karatsuba", failCount);
+
+ failCount = 0;
+ base = base.shiftLeft(BITS_TOOM_COOK - BITS_KARATSUBA);
+ for (int i=0; i<size; i++) {
+ BigInteger x = fetchNumber(BITS_TOOM_COOK - 32 - 1);
+ BigInteger u = base.add(x);
+ BigInteger u2 = u.shiftLeft(1);
+ BigInteger y = fetchNumber(BITS_TOOM_COOK - 32 - 1);
+ BigInteger v = base.add(y);
+ BigInteger v2 = v.shiftLeft(1);
+
+ BigInteger multiplyResult = u.multiply(v).shiftLeft(2);
+ BigInteger toomCookMultiplyResult = u2.multiply(v2);
+
+ if (!multiplyResult.equals(toomCookMultiplyResult)) {
+ failCount++;
+ }
+ }
+
+ report("multiplyLarge Toom-Cook", failCount);
+ }
+
+ /**
+ * Sanity test for Karatsuba and 3-way Toom-Cook squaring.
+ * This test is analogous to {@link AbstractMethodError#multiplyLarge}
+ * with both factors being equal. The squaring methods will not be tested
+ * unless the <code>bigInteger.multiply(bigInteger)</code> tests whether
+ * the parameter is the same instance on which the method is being invoked
+ * and calls <code>square()</code> accordingly.
+ */
+ public static void squareLarge() {
+ int failCount = 0;
+
+ BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA_SQUARE - 32 - 1);
+ for (int i=0; i<size; i++) {
+ BigInteger x = fetchNumber(BITS_KARATSUBA_SQUARE - 32 - 1);
+ BigInteger u = base.add(x);
+ int a = 1 + rnd.nextInt(31);
+ BigInteger w = u.shiftLeft(a);
+
+ BigInteger squareResult = u.multiply(u).shiftLeft(2*a);
+ BigInteger karatsubaSquareResult = w.multiply(w);
+
+ if (!squareResult.equals(karatsubaSquareResult)) {
+ failCount++;
+ }
+ }
+
+ report("squareLarge Karatsuba", failCount);
+
+ failCount = 0;
+ base = base.shiftLeft(BITS_TOOM_COOK_SQUARE - BITS_KARATSUBA_SQUARE);
+ for (int i=0; i<size; i++) {
+ BigInteger x = fetchNumber(BITS_TOOM_COOK_SQUARE - 32 - 1);
+ BigInteger u = base.add(x);
+ int a = 1 + rnd.nextInt(31);
+ BigInteger w = u.shiftLeft(a);
+
+ BigInteger squareResult = u.multiply(u).shiftLeft(2*a);
+ BigInteger toomCookSquareResult = w.multiply(w);
+
+ if (!squareResult.equals(toomCookSquareResult)) {
+ failCount++;
+ }
+ }
+
+ report("squareLarge Toom-Cook", failCount);
}
public static void bitCount() {
@@ -160,14 +315,14 @@
report("BitLength", failCount);
}
- public static void bitOps() {
+ public static void bitOps(int order) {
int failCount1 = 0, failCount2 = 0, failCount3 = 0;
for (int i=0; i<size*5; i++) {
- BigInteger x = fetchNumber(order1);
+ BigInteger x = fetchNumber(order);
BigInteger y;
- /* Test setBit and clearBit (and testBit) */
+ // Test setBit and clearBit (and testBit)
if (x.signum() < 0) {
y = BigInteger.valueOf(-1);
for (int j=0; j<x.bitLength(); j++)
@@ -182,7 +337,7 @@
if (!x.equals(y))
failCount1++;
- /* Test flipBit (and testBit) */
+ // Test flipBit (and testBit)
y = BigInteger.valueOf(x.signum()<0 ? -1 : 0);
for (int j=0; j<x.bitLength(); j++)
if (x.signum()<0 ^ x.testBit(j))
@@ -190,13 +345,13 @@
if (!x.equals(y))
failCount2++;
}
- report("clearBit/testBit", failCount1);
- report("flipBit/testBit", failCount2);
+ report("clearBit/testBit for " + order + " bits", failCount1);
+ report("flipBit/testBit for " + order + " bits", failCount2);
for (int i=0; i<size*5; i++) {
- BigInteger x = fetchNumber(order1);
+ BigInteger x = fetchNumber(order);
- /* Test getLowestSetBit() */
+ // Test getLowestSetBit()
int k = x.getLowestSetBit();
if (x.signum() == 0) {
if (k != -1)
@@ -210,43 +365,43 @@
failCount3++;
}
}
- report("getLowestSetBit", failCount3);
+ report("getLowestSetBit for " + order + " bits", failCount3);
}
- public static void bitwise() {
+ public static void bitwise(int order) {
- /* Test identity x^y == x|y &~ x&y */
+ // Test identity x^y == x|y &~ x&y
int failCount = 0;
for (int i=0; i<size; i++) {
- BigInteger x = fetchNumber(order1);
- BigInteger y = fetchNumber(order1);
+ BigInteger x = fetchNumber(order);
+ BigInteger y = fetchNumber(order);
BigInteger z = x.xor(y);
BigInteger w = x.or(y).andNot(x.and(y));
if (!z.equals(w))
failCount++;
}
- report("Logic (^ | & ~)", failCount);
+ report("Logic (^ | & ~) for " + order + " bits", failCount);
- /* Test identity x &~ y == ~(~x | y) */
+ // Test identity x &~ y == ~(~x | y)
failCount = 0;
for (int i=0; i<size; i++) {
- BigInteger x = fetchNumber(order1);
- BigInteger y = fetchNumber(order1);
+ BigInteger x = fetchNumber(order);
+ BigInteger y = fetchNumber(order);
BigInteger z = x.andNot(y);
BigInteger w = x.not().or(y).not();
if (!z.equals(w))
failCount++;
}
- report("Logic (&~ | ~)", failCount);
+ report("Logic (&~ | ~) for " + order + " bits", failCount);
}
- public static void shift() {
+ public static void shift(int order) {
int failCount1 = 0;
int failCount2 = 0;
int failCount3 = 0;
for (int i=0; i<100; i++) {
- BigInteger x = fetchNumber(order1);
+ BigInteger x = fetchNumber(order);
int n = Math.abs(rnd.nextInt()%200);
if (!x.shiftLeft(n).equals
@@ -274,18 +429,18 @@
if (!x.shiftLeft(n).shiftRight(n).equals(x))
failCount3++;
}
- report("baz shiftLeft", failCount1);
- report("baz shiftRight", failCount2);
- report("baz shiftLeft/Right", failCount3);
+ report("baz shiftLeft for " + order + " bits", failCount1);
+ report("baz shiftRight for " + order + " bits", failCount2);
+ report("baz shiftLeft/Right for " + order + " bits", failCount3);
}
- public static void divideAndRemainder() {
+ public static void divideAndRemainder(int order) {
int failCount1 = 0;
for (int i=0; i<size; i++) {
- BigInteger x = fetchNumber(order1).abs();
+ BigInteger x = fetchNumber(order).abs();
while(x.compareTo(BigInteger.valueOf(3L)) != 1)
- x = fetchNumber(order1).abs();
+ x = fetchNumber(order).abs();
BigInteger z = x.divide(BigInteger.valueOf(2L));
BigInteger y[] = x.divideAndRemainder(x);
if (!y[0].equals(BigInteger.ONE)) {
@@ -306,7 +461,7 @@
System.err.println(" y :"+y);
}
}
- report("divideAndRemainder I", failCount1);
+ report("divideAndRemainder for " + order + " bits", failCount1);
}
public static void stringConv() {
@@ -331,13 +486,13 @@
report("String Conversion", failCount);
}
- public static void byteArrayConv() {
+ public static void byteArrayConv(int order) {
int failCount = 0;
for (int i=0; i<size; i++) {
- BigInteger x = fetchNumber(order1);
+ BigInteger x = fetchNumber(order);
while (x.equals(BigInteger.ZERO))
- x = fetchNumber(order1);
+ x = fetchNumber(order);
BigInteger y = new BigInteger(x.toByteArray());
if (!x.equals(y)) {
failCount++;
@@ -345,19 +500,19 @@
System.err.println("new is "+y);
}
}
- report("Array Conversion", failCount);
+ report("Array Conversion for " + order + " bits", failCount);
}
- public static void modInv() {
+ public static void modInv(int order) {
int failCount = 0, successCount = 0, nonInvCount = 0;
for (int i=0; i<size; i++) {
- BigInteger x = fetchNumber(order1);
+ BigInteger x = fetchNumber(order);
while(x.equals(BigInteger.ZERO))
- x = fetchNumber(order1);
- BigInteger m = fetchNumber(order1).abs();
+ x = fetchNumber(order);
+ BigInteger m = fetchNumber(order).abs();
while(m.compareTo(BigInteger.ONE) != 1)
- m = fetchNumber(order1).abs();
+ m = fetchNumber(order).abs();
try {
BigInteger inv = x.modInverse(m);
@@ -374,10 +529,10 @@
nonInvCount++;
}
}
- report("Modular Inverse", failCount);
+ report("Modular Inverse for " + order + " bits", failCount);
}
- public static void modExp() {
+ public static void modExp(int order1, int order2) {
int failCount = 0;
for (int i=0; i<size/10; i++) {
@@ -398,13 +553,14 @@
failCount++;
}
}
- report("Exponentiation I", failCount);
+ report("Exponentiation I for " + order1 + " and " +
+ order2 + " bits", failCount);
}
// This test is based on Fermat's theorem
// which is not ideal because base must not be multiple of modulus
// and modulus must be a prime or pseudoprime (Carmichael number)
- public static void modExp2() {
+ public static void modExp2(int order) {
int failCount = 0;
for (int i=0; i<10; i++) {
@@ -412,11 +568,11 @@
while(m.compareTo(BigInteger.ONE) != 1)
m = new BigInteger(100, 5, rnd);
BigInteger exp = m.subtract(BigInteger.ONE);
- BigInteger base = fetchNumber(order1).abs();
+ BigInteger base = fetchNumber(order).abs();
while(base.compareTo(m) != -1)
- base = fetchNumber(order1).abs();
+ base = fetchNumber(order).abs();
while(base.equals(BigInteger.ZERO))
- base = fetchNumber(order1).abs();
+ base = fetchNumber(order).abs();
BigInteger one = base.modPow(exp, m);
if (!one.equals(BigInteger.ONE)) {
@@ -426,7 +582,7 @@
failCount++;
}
}
- report("Exponentiation II", failCount);
+ report("Exponentiation II for " + order + " bits", failCount);
}
private static final int[] mersenne_powers = {
@@ -704,36 +860,62 @@
*/
public static void main(String[] args) throws Exception {
+ // Some variables for sizing test numbers in bits
+ int order1 = ORDER_MEDIUM;
+ int order2 = ORDER_SMALL;
+ int order3 = ORDER_KARATSUBA;
+ int order4 = ORDER_TOOM_COOK;
+
if (args.length >0)
order1 = (int)((Integer.parseInt(args[0]))* 3.333);
if (args.length >1)
order2 = (int)((Integer.parseInt(args[1]))* 3.333);
if (args.length >2)
order3 = (int)((Integer.parseInt(args[2]))* 3.333);
+ if (args.length >3)
+ order4 = (int)((Integer.parseInt(args[3]))* 3.333);
prime();
nextProbablePrime();
- arithmetic();
- divideAndRemainder();
- pow();
+ arithmetic(order1); // small numbers
+ arithmetic(order3); // Karatsuba / Burnikel-Ziegler range
+ arithmetic(order4); // Toom-Cook range
+
+ divideAndRemainder(order1); // small numbers
+ divideAndRemainder(order3); // Karatsuba / Burnikel-Ziegler range
+ divideAndRemainder(order4); // Toom-Cook range
+
+ pow(order1);
+ pow(order3);
+ pow(order4);
+
+ square(ORDER_MEDIUM);
+ square(ORDER_KARATSUBA_SQUARE);
+ square(ORDER_TOOM_COOK_SQUARE);
bitCount();
bitLength();
- bitOps();
- bitwise();
+ bitOps(order1);
+ bitwise(order1);
- shift();
+ shift(order1);
+
+ byteArrayConv(order1);
- byteArrayConv();
+ modInv(order1); // small numbers
+ modInv(order3); // Karatsuba / Burnikel-Ziegler range
+ modInv(order4); // Toom-Cook range
- modInv();
- modExp();
- modExp2();
+ modExp(order1, order2);
+ modExp2(order1);
stringConv();
serialize();
+ multiplyLarge();
+ squareLarge();
+
if (failure)
throw new RuntimeException("Failure in BigIntegerTest.");
}
@@ -747,7 +929,7 @@
*/
private static BigInteger fetchNumber(int order) {
boolean negative = rnd.nextBoolean();
- int numType = rnd.nextInt(6);
+ int numType = rnd.nextInt(7);
BigInteger result = null;
if (order < 2) order = 2;
@@ -783,6 +965,19 @@
result = result.or(temp);
}
break;
+ case 5: // Runs of consecutive ones and zeros
+ result = ZERO;
+ int remaining = order;
+ int bit = rnd.nextInt(2);
+ while (remaining > 0) {
+ int runLength = Math.min(remaining, rnd.nextInt(order));
+ result = result.shiftLeft(runLength);
+ if (bit > 0)
+ result = result.add(ONE.shiftLeft(runLength).subtract(ONE));
+ remaining -= runLength;
+ bit = 1 - bit;
+ }
+ break;
default: // random bits
result = new BigInteger(order, rnd);