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

Incorrect BigInteger division because of MutableBigInteger.bitLength() overflow

    XMLWordPrintable

Details

    • Bug
    • Resolution: Fixed
    • P4
    • 8
    • 8
    • core-libs
    • b115
    • linux_ubuntu
    • Verified

    Description

      FULL PRODUCT VERSION :
      java version " 1.8.0-ea "
      Java(TM) SE Runtime Environment (build 1.8.0-ea-b102)
      Java HotSpot(TM) 64-Bit Server VM (build 25.0-b44, mixed mode)


      ADDITIONAL OS VERSION INFORMATION :
      Linux kisa 3.8.0-26-generic #38-Ubuntu SMP Mon Jun 17 21:43:33 UTC 2013 x86_64 x86_64 x86_64 GNU/Linux


      A DESCRIPTION OF THE PROBLEM :
      This is the bug in the implementation of BurnikelZiegler division algorithm.

      Both dividend and divisor are powers of two. So the expected remainder is zero, and expected quotent is another power of two.
      Divident is maximal power of two pow(2, Integer.MAX_VALUE - 1)) from the supported range
      [-pow(2,Integer.MAX_VALUE),pow(2,Integer.MAX_VALUE)-1].
      Divisor is the first value above BURNIKEL_ZIEGLER_THRESHOLD.
      When division algorithms normalizes the divisor, divident becomes out of the supported range
      and its " int MutableBigInteger.bitLength() " becomes negative.
      See Step 5 in MutableBigInteger.divideAndRemainderBurnikelZiegler .

      MutableBigInteger is not in public API so possible fix is to refactor to " long MutableBigInteger.bitLength() "

      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      Compile and run the attached test case

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      q.bitLenth=2147482079
      r.signum=0
      r.bitLength=0
      ACTUAL -
      q.bitLenth=1600
      r.signum=1
      r.bitLength=2147483646

      REPRODUCIBILITY :
      This bug can be reproduced always.

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

      public class DivideBug {
          
          public static void main(String[] args) {
              BigInteger a = BigInteger.ONE.shiftLeft(2147483646);
              BigInteger b = BigInteger.ONE.shiftLeft(1568);
              BigInteger[] qr = a.divideAndRemainder(b);
              BigInteger q = qr[0];
              BigInteger r = qr[1];
              System.out.println( " q.bitLenth= " + q.bitLength()); // expected 2147482079
              System.out.println( " r.signum= " + r.signum()); // expected 0
              System.out.println( " r.bitLength= " + r.bitLength()); // expected 0
          }
      }

      ---------- END SOURCE ----------

      CUSTOMER SUBMITTED WORKAROUND :
      Refactor MutableBigInteger.bitLength() to return " long " instead of " int " .
      It is possible because class MutableBigInteger is not in public API.

      Attachments

        Issue Links

          Activity

            People

              bpb Brian Burkhalter
              webbuggrp Webbug Group
              Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

                Created:
                Updated:
                Resolved: