7131192: BigInteger.doubleValue() is depressingly slow

Summary: In doubleValue() and floatValue() replace converting to String and parsing to Double or Float with direct conversion into IEEE 754 bits.
Reviewed-by: bpb, drchase, martin
Contributed-by: Louis Wasserman <lowasser@google.com>

1 files changed, 142 insertions, 4 deletions

diff --git a/src/share/classes/java/math/BigInteger.java b/src/share/classes/java/math/BigInteger.java
index 4c8b7816d0..8972ac76ef 100644
--- a/src/share/classes/java/math/BigInteger.java
+++ b/src/share/classes/java/math/BigInteger.java
@@ -35,6 +35,8 @@ import java.io.ObjectOutputStream;
 import java.io.ObjectStreamField;
 import java.util.Arrays;
 import java.util.Random;
+import sun.misc.DoubleConsts;
+import sun.misc.FloatConsts;
 
 /**
  * Immutable arbitrary-precision integers.  All operations behave as if
@@ -3452,8 +3454,72 @@ public class BigInteger extends Number implements Comparable<BigInteger> {
      * @return this BigInteger converted to a {@code float}.
      */
     public float floatValue() {
-        // Somewhat inefficient, but guaranteed to work.
-        return Float.parseFloat(this.toString());
+        if (signum == 0) {
+            return 0.0f;
+        }
+
+        int exponent = ((mag.length - 1) << 5) + bitLengthForInt(mag[0]) - 1;
+
+        // exponent == floor(log2(abs(this)))
+        if (exponent < Long.SIZE - 1) {
+            return longValue();
+        } else if (exponent > Float.MAX_EXPONENT) {
+            return signum > 0 ? Float.POSITIVE_INFINITY : Float.NEGATIVE_INFINITY;
+        }
+
+        /*
+         * We need the top SIGNIFICAND_WIDTH bits, including the "implicit"
+         * one bit. To make rounding easier, we pick out the top
+         * SIGNIFICAND_WIDTH + 1 bits, so we have one to help us round up or
+         * down. twiceSignifFloor will contain the top SIGNIFICAND_WIDTH + 1
+         * bits, and signifFloor the top SIGNIFICAND_WIDTH.
+         *
+         * It helps to consider the real number signif = abs(this) *
+         * 2^(SIGNIFICAND_WIDTH - 1 - exponent).
+         */
+        int shift = exponent - FloatConsts.SIGNIFICAND_WIDTH;
+
+        int twiceSignifFloor;
+        // twiceSignifFloor will be == abs().shiftRight(shift).intValue()
+        // We do the shift into an int directly to improve performance.
+
+        int nBits = shift & 0x1f;
+        int nBits2 = 32 - nBits;
+
+        if (nBits == 0) {
+            twiceSignifFloor = mag[0];
+        } else {
+            twiceSignifFloor = mag[0] >>> nBits;
+            if (twiceSignifFloor == 0) {
+                twiceSignifFloor = (mag[0] << nBits2) | (mag[1] >>> nBits);
+            }
+        }
+
+        int signifFloor = twiceSignifFloor >> 1;
+        signifFloor &= FloatConsts.SIGNIF_BIT_MASK; // remove the implied bit
+
+        /*
+         * We round up if either the fractional part of signif is strictly
+         * greater than 0.5 (which is true if the 0.5 bit is set and any lower
+         * bit is set), or if the fractional part of signif is >= 0.5 and
+         * signifFloor is odd (which is true if both the 0.5 bit and the 1 bit
+         * are set). This is equivalent to the desired HALF_EVEN rounding.
+         */
+        boolean increment = (twiceSignifFloor & 1) != 0
+                && ((signifFloor & 1) != 0 || abs().getLowestSetBit() < shift);
+        int signifRounded = increment ? signifFloor + 1 : signifFloor;
+        int bits = ((exponent + FloatConsts.EXP_BIAS))
+                << (FloatConsts.SIGNIFICAND_WIDTH - 1);
+        bits += signifRounded;
+        /*
+         * If signifRounded == 2^24, we'd need to set all of the significand
+         * bits to zero and add 1 to the exponent. This is exactly the behavior
+         * we get from just adding signifRounded to bits directly. If the
+         * exponent is Float.MAX_EXPONENT, we round up (correctly) to
+         * Float.POSITIVE_INFINITY.
+         */
+        bits |= signum & FloatConsts.SIGN_BIT_MASK;
+        return Float.intBitsToFloat(bits);
     }
 
     /**
@@ -3472,8 +3538,80 @@ public class BigInteger extends Number implements Comparable<BigInteger> {
      * @return this BigInteger converted to a {@code double}.
      */
     public double doubleValue() {
-        // Somewhat inefficient, but guaranteed to work.
-        return Double.parseDouble(this.toString());
+        if (signum == 0) {
+            return 0.0;
+        }
+
+        int exponent = ((mag.length - 1) << 5) + bitLengthForInt(mag[0]) - 1;
+
+        // exponent == floor(log2(abs(this))Double)
+        if (exponent < Long.SIZE - 1) {
+            return longValue();
+        } else if (exponent > Double.MAX_EXPONENT) {
+            return signum > 0 ? Double.POSITIVE_INFINITY : Double.NEGATIVE_INFINITY;
+        }
+
+        /*
+         * We need the top SIGNIFICAND_WIDTH bits, including the "implicit"
+         * one bit. To make rounding easier, we pick out the top
+         * SIGNIFICAND_WIDTH + 1 bits, so we have one to help us round up or
+         * down. twiceSignifFloor will contain the top SIGNIFICAND_WIDTH + 1
+         * bits, and signifFloor the top SIGNIFICAND_WIDTH.
+         *
+         * It helps to consider the real number signif = abs(this) *
+         * 2^(SIGNIFICAND_WIDTH - 1 - exponent).
+         */
+        int shift = exponent - DoubleConsts.SIGNIFICAND_WIDTH;
+
+        long twiceSignifFloor;
+        // twiceSignifFloor will be == abs().shiftRight(shift).longValue()
+        // We do the shift into a long directly to improve performance.
+
+        int nBits = shift & 0x1f;
+        int nBits2 = 32 - nBits;
+
+        int highBits;
+        int lowBits;
+        if (nBits == 0) {
+            highBits = mag[0];
+            lowBits = mag[1];
+        } else {
+            highBits = mag[0] >>> nBits;
+            lowBits = (mag[0] << nBits2) | (mag[1] >>> nBits);
+            if (highBits == 0) {
+                highBits = lowBits;
+                lowBits = (mag[1] << nBits2) | (mag[2] >>> nBits);
+            }
+        }
+
+        twiceSignifFloor = ((highBits & LONG_MASK) << 32)
+                | (lowBits & LONG_MASK);
+
+        long signifFloor = twiceSignifFloor >> 1;
+        signifFloor &= DoubleConsts.SIGNIF_BIT_MASK; // remove the implied bit
+
+        /*
+         * We round up if either the fractional part of signif is strictly
+         * greater than 0.5 (which is true if the 0.5 bit is set and any lower
+         * bit is set), or if the fractional part of signif is >= 0.5 and
+         * signifFloor is odd (which is true if both the 0.5 bit and the 1 bit
+         * are set). This is equivalent to the desired HALF_EVEN rounding.
+         */
+        boolean increment = (twiceSignifFloor & 1) != 0
+                && ((signifFloor & 1) != 0 || abs().getLowestSetBit() < shift);
+        long signifRounded = increment ? signifFloor + 1 : signifFloor;
+        long bits = (long) ((exponent + DoubleConsts.EXP_BIAS))
+                << (DoubleConsts.SIGNIFICAND_WIDTH - 1);
+        bits += signifRounded;
+        /*
+         * If signifRounded == 2^53, we'd need to set all of the significand
+         * bits to zero and add 1 to the exponent. This is exactly the behavior
+         * we get from just adding signifRounded to bits directly. If the
+         * exponent is Double.MAX_EXPONENT, we round up (correctly) to
+         * Double.POSITIVE_INFINITY.
+         */
+        bits |= signum & DoubleConsts.SIGN_BIT_MASK;
+        return Double.longBitsToDouble(bits);
     }
 
     /**