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

Faster string conversion of large integers

    XMLWordPrintable

    Details

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

      Description

      Name: gm110360 Date: 02/22/2002


      FULL PRODUCT VERSION :
      java version "1.3.1"
      Java(TM) 2 Runtime Environment, Standard Edition (build 1.3.1-b24)
      Java HotSpot(TM) Client VM (build 1.3.1-b24, mixed mode)

      FULL OPERATING SYSTEM VERSION :
      Microsoft Windows 2000 [Version 5.00.2195]

      ADDITIONAL OPERATING SYSTEMS :
      All


      A DESCRIPTION OF THE PROBLEM :
      The algorithm for radix conversion in BigInteger.toString()
      is very inefficient for large numbers, making it unusable
      for serious mathematical work.

      For example, calculating the value of the largest
      currently-known Mersenne prime, 2^13466917 - 1, takes about
      .16 seconds on an 800 MHz Pentium III. (This is if you work
      around the similar critical slowness in pow(), see bug
      4449911 ) No big problem in the exponentiation (but there
      would be if it was a base that wasn't a power of 2.)

      But if you want to see the results, toString() takes over 14
      *hours*. Other tools, such as Mathematica, return the value
      in a few seconds.

      The algorithm used is inefficient; much more efficient
      algorithms exist. See the recursive decomposition
      algorithms attributed to Knuth and Schoenhage in Donald
      Knuth, The Art of Computer Programming, Vol. 2:
      Seminumerical Algorithms, in the section "Answers to
      Exercises, Section 4.4" Section 4.4 of the text (which
      resembles the algorithms used in BigInteger) are orders of
      magnitude slower than the algorithms outlined in the
      "Answers to Exercises."

      All algorithms will also benefit from improving the
      quadratic behavior of the multiply, divide, and
      exponentiation functions as implemented.

      For a Java implementation of more efficient algorithms, see
      http://www.cis.ksu.edu/~howell/calculator/comparison.html.

      This implementation, using a base 10 radix (the radix is
      configurable) can calculate and print the value in about 6
      minutes, making it a minimum of 140 times faster. Almost
      all of this time is in the exponentiation (which is of
      course harder to do in base 10, but still much faster than
      the JDK 1.3.1 implementation of pow())

      Again, this is critical if BigInteger is to be used for
      serious mathematical work.

      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      Compile and run the code below:

      javac BigIntTest.java
      java BigIntTest

      (wait 14 hours...)



      This bug can be reproduced always.

      ---------- BEGIN SOURCE ----------
      import java.math.BigInteger;

      public class BigIntTest
      {
         /** This calculates the largest-known Mersenne Prime, 2^13466917 - 1 */
         public static void main(String[] args)
         {
            System.out.println("Starting");
            BigInteger b = new BigInteger("2");

            // The shiftLeft below is a kludge to get around how slow pow() is in 1.3)
            // Internally, pow() should be implemented so that it does this
            // shiftLeft optimization for bases that are powers of 2.
            BigInteger p = b.shiftLeft(13466917 - 1);
            System.out.println("Exponentiation complete");
            p = p.subtract(new BigInteger("1"));
            System.out.println("Subtraction complete");

            // Now wait about a day for the toString() to work.
            System.out.println(p.toString());
         }
      }
      ---------- END SOURCE ----------

      CUSTOMER WORKAROUND :
      Use Mathematica or the LargeInteger class mentioned above.
      (Review ID: 143124)
      ======================================================================
      ###@###.### 2004-11-11 22:25:31 GMT

        Attachments

          Issue Links

            Activity

              People

              Assignee:
              bpb Brian Burkhalter
              Reporter:
              gmanwanisunw Girish Manwani (Inactive)
              Votes:
              0 Vote for this issue
              Watchers:
              3 Start watching this issue

                Dates

                Created:
                Updated:
                Resolved:
                Imported:
                Indexed: