Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-7131192

BigInteger.doubleValue() is depressingly slow

    Details

    • Type: Enhancement
    • Status: Closed
    • Priority: P4
    • Resolution: Fixed
    • Affects Version/s: 7
    • Fix Version/s: 8
    • Component/s: core-libs
    • Labels:
    • Subcomponent:
    • Resolved In Build:
      b98
    • CPU:
      x86
    • OS:
      linux_ubuntu
    • Verification:
      Verified

      Description

      A DESCRIPTION OF THE REQUEST :
      BigInteger.doubleValue() is implemented using the terrible workaround of converting it to a string and then parsing the double, instead of using Double.longBitsToDouble to do the work in at most linear (and usually faster) time.

      JUSTIFICATION :
      BigInteger is intended to be used for relatively high-performance arbitrary-precision arithmetic. Being able to convert efficiently into a double can be extremely useful, especially for constructing initial approximations to BigInteger results.

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      BigInteger.doubleValue() and floatValue() should be implemented in terms of Double.longBitsToDouble and Float.intBitsToFloat, and should run in at most linear time in the length of the BigInteger.
      ACTUAL -
      BigInteger.doubleValue() is implemented as the sequence of two already-expensive operations: BigInteger.toString() and Double.parseDouble.

      CUSTOMER SUBMITTED WORKAROUND :
      I have used the following algorithm for converting BigIntegers to doubles, even without being able to access the BigInteger internals.

        static final int SIGNIFICAND_BITS = 52;
        static final int EXPONENT_BIAS = 1023;
        static final long SIGNIFICAND_MASK = 0x000fffffffffffffL;
        static final long SIGN_MASK = 0x8000000000000000L;
        
        static double bigToDouble(BigInteger x) {
          BigInteger absX = x.abs();
          int exponent = absX.bitLength() - 1;
          // exponent == floor(log2(abs(x)))
          if (exponent < Long.SIZE - 1) {
            return x.longValue();
          } else if (exponent > Double.MAX_EXPONENT) {
            return x.signum() * Double.POSITIVE_INFINITY;
          }

          /*
           * We need the top SIGNIFICAND_BITS + 1 bits, including the "implicit" one bit. To make
           * rounding easier, we pick out the top SIGNIFICAND_BITS + 2 bits, so we have one to help us
           * round up or down. twiceSignifFloor will contain the top SIGNIFICAND_BITS + 2 bits, and
           * signifFloor the top SIGNIFICAND_BITS + 1.
           *
           * It helps to consider the real number signif = absX * 2^(SIGNIFICAND_BITS - exponent).
           */
          int shift = exponent - SIGNIFICAND_BITS - 1;
          long twiceSignifFloor = absX.shiftRight(shift).longValue();
          long signifFloor = twiceSignifFloor >> 1;
          signifFloor &= SIGNIFICAND_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 behavior.
           */
          boolean increment = (twiceSignifFloor & 1) != 0
              && ((signifFloor & 1) != 0 || absX.getLowestSetBit() < shift);
          long signifRounded = increment ? signifFloor + 1 : signifFloor;
          long bits = (long) ((exponent + EXPONENT_BIAS)) << SIGNIFICAND_BITS;
          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 MAX_DOUBLE_EXPONENT, we round up (correctly) to
           * Double.POSITIVE_INFINITY.
           */
          bits |= x.signum() & SIGN_MASK;
          return Double.longBitsToDouble(bits);
        }

      I have tested this on an extremely large set of test cases intended to break it. In fact, my testing of this method actually led to my independent discovery of Sun bug 6358355.

      Of course, this method could be made even faster with access to the internals of BigInteger, but benchmarks already suggest massive superiority. I tested it using the open-source microbenchmarking tool Caliper, generating inputs according to the following code:

          Random gen = new Random();
          for (int i = 0; i < SAMPLE_SIZE; i++) {
            BIGINTS[i] = new BigInteger(gen.nextInt(1024), gen);
          }

      which seems reasonable enough. The benchmark, as you might expect, wasn't even close, suggesting over two orders of magnitude of improvement.
      Comments copied from http://bugs.openjdk.java.net/show_bug.cgi?id=100222

      Description From Louis Wasserman 2012-01-20 12:13:25 PDT

      Created an attachment (id=254) [details]
      Patch including both the performance improvement and the test.

      sunbug=7131192

      This patch improves the performance of BigInteger.floatValue() and
      BigInteger.doubleValue() by over two orders of magnitude, based on a
      microbenchmark run with the open-source Java microbenchmarking tool Caliper.

      http://microbenchmarks.appspot.com/run/###@###.###/DoubleBenchmark

      This patch is based on code I contributed to Google Guava:
      http://code.google.com/p/guava-libraries/source/browse/guava/src/com/google/common/math/DoubleUtils.java#136

      However, with access to the BigInteger internals, this patch can be even
      faster. In particular, shifting directly into a long, rather than performing a
      shiftRight into a BigInteger that fits into a long, significantly improves
      performance.

      Comment #1 From Tim Bell 2012-07-11 14:51:46 PDT

      Closing. SUNBUG=7131192

      Comment #2 From Louis Wasserman 2012-07-11 14:58:13 PDT

      I'm not sure I follow why this was closed. The instructions linked to by the
      Sun website say that bug fixes should be submitted and discussed with this
      tracker.

      Comment #3 From Tim Bell 2012-07-11 15:06:54 PDT

      (In reply to comment #2)
      > I'm not sure I follow why this was closed. The instructions linked to by the
      > Sun website say that bug fixes should be submitted and discussed with this
      > tracker.

      We are preparing to roll out a new Jira instance for tracking all OpenJDK bugs.
       As part of the conversion I am going through all old bugs.openjdk.java.net
      reports and closing them out.

      In this case, since there is already an existing internal SUNBUG (7131192), I
      will copy the information from this report (100222) to 7131192. In other cases
      I will be creating a new SUNBUG before copying to it. Our automated conversion
      tools will migrate these to Jira along with all our other reports.

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                bpb Brian Burkhalter
                Reporter:
                webbuggrp Webbug Group
              • Votes:
                0 Vote for this issue
                Watchers:
                1 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved:
                  Imported:
                  Indexed: