test/java/math/BigInteger/BigIntegerTest.java

rev 7474 : 4641897: Faster string conversion of large integers
Summary: Accelerate conversion to string by means of Schoenhage recursive base conversion.
Reviewed-by: bpb
Contributed-by: Alan Eliasen <eliasen@mindspring.com>

*** 59,72 ****
--- 59,75 ----
      // KARATSUBA_THRESHOLD        = 50  ints = 1600 bits
      // TOOM_COOK_THRESHOLD        = 75  ints = 2400 bits
      // KARATSUBA_SQUARE_THRESHOLD = 90  ints = 2880 bits
      // TOOM_COOK_SQUARE_THRESHOLD = 140 ints = 4480 bits
      //
+     // SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 8 ints = 256 bits
+     //
      static final int BITS_KARATSUBA = 1600;
      static final int BITS_TOOM_COOK = 2400;
      static final int BITS_KARATSUBA_SQUARE = 2880;
      static final int BITS_TOOM_COOK_SQUARE = 4480;
+     static final int BITS_SCHOENHAGE_BASE = 256;
  
      static final int ORDER_SMALL = 60;
      static final int ORDER_MEDIUM = 100;
      // #bits for testing Karatsuba and Burnikel-Ziegler
      static final int ORDER_KARATSUBA = 1800;
*** 465,490 ****
      }
  
      public static void stringConv() {
          int failCount = 0;
  
          for (int i=0; i<100; i++) {
              byte xBytes[] = new byte[Math.abs(rnd.nextInt())%100+1];
              rnd.nextBytes(xBytes);
              BigInteger x = new BigInteger(xBytes);
  
!             for (int radix=2; radix < 37; radix++) {
                  String result = x.toString(radix);
                  BigInteger test = new BigInteger(result, radix);
                  if (!test.equals(x)) {
                      failCount++;
                      System.err.println("BigInteger toString: "+x);
                      System.err.println("Test: "+test);
                      System.err.println(radix);
                  }
              }
          }
          report("String Conversion", failCount);
      }
  
      public static void byteArrayConv(int order) {
          int failCount = 0;
--- 468,522 ----
      }
  
      public static void stringConv() {
          int failCount = 0;
  
+         // Generic string conversion.
          for (int i=0; i<100; i++) {
              byte xBytes[] = new byte[Math.abs(rnd.nextInt())%100+1];
              rnd.nextBytes(xBytes);
              BigInteger x = new BigInteger(xBytes);
  
!             for (int radix=Character.MIN_RADIX; radix < Character.MAX_RADIX; radix++) {
                  String result = x.toString(radix);
                  BigInteger test = new BigInteger(result, radix);
                  if (!test.equals(x)) {
                      failCount++;
                      System.err.println("BigInteger toString: "+x);
                      System.err.println("Test: "+test);
                      System.err.println(radix);
                  }
              }
          }
+ 
+         // String conversion straddling the Schoenhage algorithm crossover
+         // threshold, and at twice and four times the threshold.
+         for (int k = 0; k <= 2; k++) {
+             int factor = 1 << k;
+             int upper = factor * BITS_SCHOENHAGE_BASE + 33;
+             int lower = upper - 35;
+ 
+             for (int bits = upper; bits >= lower; bits--) {
+                 for (int i = 0; i < 50; i++) {
+                     BigInteger x = BigInteger.ONE.shiftLeft(bits - 1);
+                     BigInteger y = new BigInteger(bits - 2, rnd);
+                     x = x.or(y);
+ 
+                     for (int radix = Character.MIN_RADIX; radix < Character.MAX_RADIX; radix++) {
+                         String result = x.toString(radix);
+                         BigInteger test = new BigInteger(result, radix);
+                         if (!test.equals(x)) {
+                             failCount++;
+                             System.err.println("BigInteger toString: " + x);
+                             System.err.println("Test: " + test);
+                             System.err.println(radix);
+                         }
+                     }
+                 }
+             }
+         }
+ 
          report("String Conversion", failCount);
      }
  
      public static void byteArrayConv(int order) {
          int failCount = 0;