src/share/classes/java/math/BigInteger.java
Print this page
rev 7488 : 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>
*** 33,42 ****
--- 33,44 ----
import java.io.ObjectInputStream;
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
* BigIntegers were represented in two's-complement notation (like Java's
* primitive integer types). BigInteger provides analogues to all of Java's
*** 3450,3461 ****
* information about the precision of the BigInteger value.
*
* @return this BigInteger converted to a {@code float}.
*/
public float floatValue() {
! // Somewhat inefficient, but guaranteed to work.
! return Float.parseFloat(this.toString());
}
/**
* Converts this BigInteger to a {@code double}. This
* conversion is similar to the
--- 3452,3527 ----
* information about the precision of the BigInteger value.
*
* @return this BigInteger converted to a {@code float}.
*/
public float floatValue() {
! 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);
}
/**
* Converts this BigInteger to a {@code double}. This
* conversion is similar to the
*** 3470,3481 ****
* information about the precision of the BigInteger value.
*
* @return this BigInteger converted to a {@code double}.
*/
public double doubleValue() {
! // Somewhat inefficient, but guaranteed to work.
! return Double.parseDouble(this.toString());
}
/**
* Returns a copy of the input array stripped of any leading zero bytes.
*/
--- 3536,3619 ----
* information about the precision of the BigInteger value.
*
* @return this BigInteger converted to a {@code double}.
*/
public double doubleValue() {
! 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);
}
/**
* Returns a copy of the input array stripped of any leading zero bytes.
*/