test/java/math/BigInteger/BigIntegerTest.java

rev 10672 : 8058505: BigIntegerTest does not exercise Burnikel-Ziegler division
Modify divideLarge() method such that the w/z division exercises the B-Z branch.
Reviewed-by: TBD
Contributed-by: robbiexgibson@yahoo.com

*** 69,78 ****
--- 69,79 ----
      static final int BITS_TOOM_COOK = 7680;
      static final int BITS_KARATSUBA_SQUARE = 4096;
      static final int BITS_TOOM_COOK_SQUARE = 6912;
      static final int BITS_SCHOENHAGE_BASE = 640;
      static final int BITS_BURNIKEL_ZIEGLER = 2560;
+     static final int BITS_BURNIKEL_ZIEGLER_OFFSET = 1280;
  
      static final int ORDER_SMALL = 60;
      static final int ORDER_MEDIUM = 100;
      // #bits for testing Karatsuba
      static final int ORDER_KARATSUBA = 2760;
*** 286,308 ****
       * a specified number of ints in its representation.  This test is based on
       * the observation that if {@code w = u*pow(2,a)} and {@code z = v*pow(2,b)}
       * where {@code abs(u) > abs(v)} and {@code a > b && b > 0}, then if
       * {@code w/z = q1*z + r1} and {@code u/v = q2*v + r2}, then
       * {@code q1 = q2*pow(2,a-b)} and {@code r1 = r2*pow(2,b)}.  The test
!      * ensures that {@code v} is just under the B-Z threshold and that {@code w}
!      * and {@code z} are both over the threshold.  This implies that {@code u/v}
!      * uses the standard division algorithm and {@code w/z} uses the B-Z
!      * algorithm.  The results of the two algorithms are then compared using the
!      * observation described in the foregoing and if they are not equal a
!      * failure is logged.
       */
      public static void divideLarge() {
          int failCount = 0;
  
!         BigInteger base = BigInteger.ONE.shiftLeft(BITS_BURNIKEL_ZIEGLER - 33);
          for (int i=0; i<SIZE; i++) {
!             BigInteger addend = new BigInteger(BITS_BURNIKEL_ZIEGLER - 34, rnd);
              BigInteger v = base.add(addend);
  
              BigInteger u = v.multiply(BigInteger.valueOf(2 + rnd.nextInt(Short.MAX_VALUE - 1)));
  
              if(rnd.nextBoolean()) {
--- 287,309 ----
       * a specified number of ints in its representation.  This test is based on
       * the observation that if {@code w = u*pow(2,a)} and {@code z = v*pow(2,b)}
       * where {@code abs(u) > abs(v)} and {@code a > b && b > 0}, then if
       * {@code w/z = q1*z + r1} and {@code u/v = q2*v + r2}, then
       * {@code q1 = q2*pow(2,a-b)} and {@code r1 = r2*pow(2,b)}.  The test
!      * ensures that {@code v} is just under the B-Z threshold, that {@code z} is
!      * over the threshold and {@code w} is much larger than {@code z}. This
!      * implies that {@code u/v} uses the standard division algorithm and
!      * {@code w/z} uses the B-Z algorithm.  The results of the two algorithms
!      * are then compared using the observation described in the foregoing and
!      * if they are not equal a failure is logged.
       */
      public static void divideLarge() {
          int failCount = 0;
  
!         BigInteger base = BigInteger.ONE.shiftLeft(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 33);
          for (int i=0; i<SIZE; i++) {
!             BigInteger addend = new BigInteger(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 34, rnd);
              BigInteger v = base.add(addend);
  
              BigInteger u = v.multiply(BigInteger.valueOf(2 + rnd.nextInt(Short.MAX_VALUE - 1)));
  
              if(rnd.nextBoolean()) {
*** 310,327 ****
              }
              if(rnd.nextBoolean()) {
                  v = v.negate();
              }
  
!             int a = 17 + rnd.nextInt(16);
              int b = 1 + rnd.nextInt(16);
!             BigInteger w = u.multiply(BigInteger.valueOf(1L << a));
!             BigInteger z = v.multiply(BigInteger.valueOf(1L << b));
  
              BigInteger[] divideResult = u.divideAndRemainder(v);
!             divideResult[0] = divideResult[0].multiply(BigInteger.valueOf(1L << (a - b)));
!             divideResult[1] = divideResult[1].multiply(BigInteger.valueOf(1L << b));
              BigInteger[] bzResult = w.divideAndRemainder(z);
  
              if (divideResult[0].compareTo(bzResult[0]) != 0 ||
                      divideResult[1].compareTo(bzResult[1]) != 0) {
                  failCount++;
--- 311,328 ----
              }
              if(rnd.nextBoolean()) {
                  v = v.negate();
              }
  
!             int a = BITS_BURNIKEL_ZIEGLER_OFFSET + rnd.nextInt(16);
              int b = 1 + rnd.nextInt(16);
!             BigInteger w = u.multiply(BigInteger.ONE.shiftLeft(a));
!             BigInteger z = v.multiply(BigInteger.ONE.shiftLeft(b));
  
              BigInteger[] divideResult = u.divideAndRemainder(v);
!             divideResult[0] = divideResult[0].multiply(BigInteger.ONE.shiftLeft(a - b));
!             divideResult[1] = divideResult[1].multiply(BigInteger.ONE.shiftLeft(b));
              BigInteger[] bzResult = w.divideAndRemainder(z);
  
              if (divideResult[0].compareTo(bzResult[0]) != 0 ||
                      divideResult[1].compareTo(bzResult[1]) != 0) {
                  failCount++;