An asymptotically fast version of java.math.BigInteger
Java Other
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
gmp
src
LICENSE
README.md
makediff.sh

README.md

Efficient BigInteger Implementation

This is an improved version of java.math.BigInteger that uses fast algorithms for multiplying and dividing large numbers. It is based on Alan Eliasen's BigInteger patch which provides the Karatsuba and Toom-Cook implementations.

Depending on the input size, numbers are multiplied using Long Multiplication, Karatsuba, Toom-Cook, or Schönhage-Strassen. For division, Long Division, Burnikel-Ziegler Division, or Barrett Division is used.

This code has been merged into OpenJDK 8 except for the Schönhage-Strassen and Barrett algorithms which are planned for OpenJDK 9.

Benchmark results for multiplication of two n-digit numbers (Intel i3 @3.1 GHz, 64-bit mode):

nOpenJDK 7 BigIntegerOpenJDK 8 BigIntegerImproved BigIntegerSpeedup vs JDK8Algorithm
10.00006ms.00006ms.00006ms1.0Long
25.00008ms.00008ms.00008ms1.0Long
50.00016ms.00015ms.00015ms1.0Long
75.00022ms.00020ms.00020ms1.0Long
100.00037ms.00032ms.00033ms1.0Long
250.0016ms.00016ms.0016ms1.0Long
500.0063ms.00053ms.0055ms1.0Kara
750.014ms.012ms.012ms1.0Toom
1,000.024ms.018ms.018ms1.0Toom
2,500.15ms.080ms.082ms1.0Toom
5,000.57ms.23ms.23ms1.0Toom
7,5001.3ms.43ms.44ms1.0Toom
10,0002.3ms.64ms.66ms1.0Toom
25,00014ms2.5ms2.6ms1.0Toom
50,00057ms7.2ms7.0ms1.0Toom
75,000.13s13ms6.5ms2.0SS
100,000.23s20ms14ms1.4SS
250,0001.4s76ms30ms2.5SS
500,0005.7s.22s77ms2.9SS
750,00013s.38s.16s2.4SS
1,000,00023s.62s.16s3.9SS
2,500,000151s2.3s.44s5.2SS
5,000,000620s6.7s.89s7.5SS
7,500,0001395s12s2.3s5.2SS
10,000,0002488s18s2.3s7.8SS
25,000,00067s12s5.6SS
50,000,000181s25s7.2SS
75,000,000339s25s14SS
100,000,000454s61s7.4SS

Benchmark results for division of a 2n-digit number by a n-digit number (Intel i3 @3.1 GHz, 64-bit mode):

nOpenJDK 7 BigIntegerOpenJDK 8 BigIntegerImproved BigIntegerSpeedup vs JDK8Algorithm
10.00016ms.00016ms.000016ms1.0Long
25.00030ms.00031ms.00031ms1.0Long
50.00052ms.00054ms.00054ms1.0Long
75.00072ms.00074ms.00074ms1.0Long
100.0011ms.0011ms.0011ms1.0Long
250.0037ms.0036ms.0037ms1.0Long
500.013ms.012ms.012ms1.0Long
750.026ms.23ms.022ms1.0BZ
1,000.045ms.036ms.035ms1.0BZ
2,500.26ms.15ms.15ms1.0BZ
5,0001.0ms.45ms.44ms1.0BZ
7,5002.3ms.82ms.83ms1.0BZ
10,0004.0ms1.3ms1.3ms1.0BZ
25,00025ms5.5ms5.4ms1.0BZ
50,00099ms15ms15ms1.0BZ
75,000.22s29ms25ms1.2BZ
100,000.40s45ms42ms1.1BZ
250,0002.5s.17s.12s1.4Barr
500,0009.9s.48s.29s1.7Barr
750,00022s.88s.66s1.3BZ
1,000,00040s1.4s.64s2.2Barr
2,500,000250s5.2s1.6s3.2Barr
5,000,0001066s15s3.5s4.3Barr
7,500,0002346s26s8.3s3.1Barr
10,000,0004464s41s8.4s4.9Barr
25,000,000156s45s3.5Barr
50,000,000421s96s4.4Barr
75,000,000800s96s8.3Barr
100,000,0001151s247s4.7Barr