4891331: BigInteger a.multiply(a) should use squaring code
Summary: Change multiply(BigInteger a) to return square() if a == this and the number of ints in the magnitude is over a threshold.
Reviewed-by: darcy, shade
--- a/jdk/src/share/classes/java/math/BigInteger.java Fri Dec 13 15:24:38 2013 -0800
+++ b/jdk/src/share/classes/java/math/BigInteger.java Fri Dec 13 16:15:58 2013 -0800
@@ -268,7 +268,15 @@
*/
private static final int SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 20;
- //Constructors
+ /**
+ * The threshold value for using squaring code to perform multiplication
+ * of a {@code BigInteger} instance by itself. If the number of ints in
+ * the number are larger than this value, {@code multiply(this)} will
+ * return {@code square()}.
+ */
+ private static final int MULTIPLY_SQUARE_THRESHOLD = 20;
+
+ // Constructors
/**
* Translates a byte array containing the two's-complement binary
@@ -1458,6 +1466,9 @@
/**
* Returns a BigInteger whose value is {@code (this * val)}.
*
+ * @implNote An implementation may offer better algorithmic
+ * performance when {@code val == this}.
+ *
* @param val value to be multiplied by this BigInteger.
* @return {@code this * val}
*/
@@ -1466,6 +1477,11 @@
return ZERO;
int xlen = mag.length;
+
+ if (val == this && xlen > MULTIPLY_SQUARE_THRESHOLD) {
+ return square();
+ }
+
int ylen = val.mag.length;
if ((xlen < KARATSUBA_THRESHOLD) || (ylen < KARATSUBA_THRESHOLD)) {