GitHub - tbuktu/bigint at floatfft (original) (raw)
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):
| n | OpenJDK 7 BigInteger | OpenJDK 8 BigInteger | Improved BigInteger | Speedup vs JDK8 | Algorithm |
|---|---|---|---|---|---|
| 10 | .00006ms | .00006ms | .00006ms | 1.0 | Long |
| 25 | .00008ms | .00008ms | .00008ms | 1.0 | Long |
| 50 | .00016ms | .00015ms | .00015ms | 1.0 | Long |
| 75 | .00022ms | .00020ms | .00020ms | 1.0 | Long |
| 100 | .00037ms | .00032ms | .00033ms | 1.0 | Long |
| 250 | .0016ms | .00016ms | .0016ms | 1.0 | Long |
| 500 | .0063ms | .00053ms | .0055ms | 1.0 | Kara |
| 750 | .014ms | .012ms | .012ms | 1.0 | Toom |
| 1,000 | .024ms | .018ms | .018ms | 1.0 | Toom |
| 2,500 | .15ms | .080ms | .082ms | 1.0 | Toom |
| 5,000 | .57ms | .23ms | .23ms | 1.0 | Toom |
| 7,500 | 1.3ms | .43ms | .44ms | 1.0 | Toom |
| 10,000 | 2.3ms | .64ms | .66ms | 1.0 | Toom |
| 25,000 | 14ms | 2.5ms | 2.6ms | 1.0 | Toom |
| 50,000 | 57ms | 7.2ms | 7.0ms | 1.0 | Toom |
| 75,000 | .13s | 13ms | 6.5ms | 2.0 | SS |
| 100,000 | .23s | 20ms | 14ms | 1.4 | SS |
| 250,000 | 1.4s | 76ms | 30ms | 2.5 | SS |
| 500,000 | 5.7s | .22s | 77ms | 2.9 | SS |
| 750,000 | 13s | .38s | .16s | 2.4 | SS |
| 1,000,000 | 23s | .62s | .16s | 3.9 | SS |
| 2,500,000 | 151s | 2.3s | .44s | 5.2 | SS |
| 5,000,000 | 620s | 6.7s | .89s | 7.5 | SS |
| 7,500,000 | 1395s | 12s | 2.3s | 5.2 | SS |
| 10,000,000 | 2488s | 18s | 2.3s | 7.8 | SS |
| 25,000,000 | 67s | 12s | 5.6 | SS | |
| 50,000,000 | 181s | 25s | 7.2 | SS | |
| 75,000,000 | 339s | 25s | 14 | SS | |
| 100,000,000 | 454s | 61s | 7.4 | SS |
Benchmark results for division of a 2n-digit number by a n-digit number (Intel i3 @3.1 GHz, 64-bit mode):
| n | OpenJDK 7 BigInteger | OpenJDK 8 BigInteger | Improved BigInteger | Speedup vs JDK8 | Algorithm |
|---|---|---|---|---|---|
| 10 | .00016ms | .00016ms | .000016ms | 1.0 | Long |
| 25 | .00030ms | .00031ms | .00031ms | 1.0 | Long |
| 50 | .00052ms | .00054ms | .00054ms | 1.0 | Long |
| 75 | .00072ms | .00074ms | .00074ms | 1.0 | Long |
| 100 | .0011ms | .0011ms | .0011ms | 1.0 | Long |
| 250 | .0037ms | .0036ms | .0037ms | 1.0 | Long |
| 500 | .013ms | .012ms | .012ms | 1.0 | Long |
| 750 | .026ms | .23ms | .022ms | 1.0 | BZ |
| 1,000 | .045ms | .036ms | .035ms | 1.0 | BZ |
| 2,500 | .26ms | .15ms | .15ms | 1.0 | BZ |
| 5,000 | 1.0ms | .45ms | .44ms | 1.0 | BZ |
| 7,500 | 2.3ms | .82ms | .83ms | 1.0 | BZ |
| 10,000 | 4.0ms | 1.3ms | 1.3ms | 1.0 | BZ |
| 25,000 | 25ms | 5.5ms | 5.4ms | 1.0 | BZ |
| 50,000 | 99ms | 15ms | 15ms | 1.0 | BZ |
| 75,000 | .22s | 29ms | 25ms | 1.2 | BZ |
| 100,000 | .40s | 45ms | 42ms | 1.1 | BZ |
| 250,000 | 2.5s | .17s | .12s | 1.4 | Barr |
| 500,000 | 9.9s | .48s | .29s | 1.7 | Barr |
| 750,000 | 22s | .88s | .66s | 1.3 | BZ |
| 1,000,000 | 40s | 1.4s | .64s | 2.2 | Barr |
| 2,500,000 | 250s | 5.2s | 1.6s | 3.2 | Barr |
| 5,000,000 | 1066s | 15s | 3.5s | 4.3 | Barr |
| 7,500,000 | 2346s | 26s | 8.3s | 3.1 | Barr |
| 10,000,000 | 4464s | 41s | 8.4s | 4.9 | Barr |
| 25,000,000 | 156s | 45s | 3.5 | Barr | |
| 50,000,000 | 421s | 96s | 4.4 | Barr | |
| 75,000,000 | 800s | 96s | 8.3 | Barr | |
| 100,000,000 | 1151s | 247s | 4.7 | Barr |