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

Faster multiplication and exponentiation of large integers

    XMLWordPrintable

    Details

    • Type: Enhancement
    • Status: Closed
    • Priority: P3
    • Resolution: Fixed
    • Affects Version/s: 5.0
    • Fix Version/s: 8
    • Component/s: core-libs
    • Labels:
    • Subcomponent:
    • Resolved In Build:
      b96
    • CPU:
      generic
    • OS:
      generic
    • Verification:
      Verified

      Description

      Implement Karatsuba and 3-way Toom-Cook multiplication of large integers, and improve exponentiation algorithm used in pow().

      Karatsuba is a recursive algorithm for multiplying multi precision integers. It has a running time of O(n ^ 1.58) compared to O(n ^ 2) [or O(n * m)] for the "simple" multiplication algorithm. It is discussed in Knuth volume 2 and http://cr.yp.to/papers/m3.pdf as well as other literature.

      Anecdotal evidence indicates that Karatsuba is the best multiplication algorithm for numbers of around 500 to a few 1000 bits as are commonly used in cryptographic and other common applications. Therefore, we should consider implementing it in BigInteger.

      Toom-Cook 3-way multiplication is also a recursive algorithm for multiplying multi-precision integers that becomes more effective than Karatsuba for integers beyond a larger threshold of number of bits. More information may be obtained here: http://bodrato.it/toom-cook/ http://bodrato.it/papers/#WAIFI2007.

      Exponentiation may be improved by factoring out powers of two for left-shifting, and using Karatsuba and Toom-Cook squaring for large numbers.

      ###@###.### 2003-03-26

        Attachments

          Issue Links

            Activity

              People

              Assignee:
              bpb Brian Burkhalter
              Reporter:
              andreas Andreas Sterbenz
              Votes:
              0 Vote for this issue
              Watchers:
              3 Start watching this issue

                Dates

                Created:
                Updated:
                Resolved:
                Imported:
                Indexed: