tbuktu / bigint

An asymptotically fast version of java.math.BigInteger

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

bigint's Issues

Override Java's BigInteger

Is is possible to use this code on our code in order to override the default BigInteger?
I just added it to my project but I am still using the default implementation.

ToomCook will not activate in certain situations?

At line 1399 you have code like this:

        if ((xlen < KARATSUBA_THRESHOLD) || (ylen < KARATSUBA_THRESHOLD))
        {
            int resultSign = signum == val.signum ? 1 : -1;
            if (val.mag.length == 1) {
                return multiplyByInt(mag,val.mag[0], resultSign);
            }
            if(mag.length == 1) {
                return multiplyByInt(val.mag,mag[0], resultSign);
            }
            int[] result = multiplyToLen(mag, xlen,
                                         val.mag, ylen, null);
            result = trustedStripLeadingZeroInts(result);
            return new BigInteger(result, resultSign);
        }
        else
            if ((xlen < TOOM_COOK_THRESHOLD) && (ylen < TOOM_COOK_THRESHOLD))
                return multiplyKaratsuba(this, val);
            else

I've been implementing my own bigint for scala based on your code, and I noticed that even though the TOOM_COOK algorithm is supposed to activate if either xlen or ylen is at or over 75, the KARATSUBA threshold is not passed if xlen AND ylen are equal to or over 50. This means that if you are multiplying a humongous BigInteger(like one with a magnitude of 1000) against one with a magnitude of 49, it will use the multiplyToLen method. Is this behaviour intended?

Schönhage-Strassen Java 9

Schönhage-Strassen and Barrett algorithms are planned for Java 9. Are they already there? if not, is it still planned?

Burnikel Division threshold on ARM Cortex-A53

I'm trying to tune Burnikel Division Threshold on my Samsung J7 Pro that has ARM Cortex-A53 processor, the burnikel division outperform knuth division when the mag length is 225, why it takes so large value? Should I change the Burnikel offset value too?

Will it merged to Java?

will this implementation merged to JDK?

Please add license

would you please add your intended license for this?
Thanks!

Line 1558 in BigInteger.java has a bug.

        // result = p1 * 2^(32*2*half) + (p3 - p1 - p2) * 2^(32*half) + p2
        BigInteger result = p1.shiftLeft(32*half).add(p3.subtract(p1).subtract(p2)).shiftLeft(32*half).add(p2);

should be

        BigInteger result = p1.shiftLeft(64*half).add(p3.subtract(p1).subtract(p2)).shiftLeft(32*half).add(p2);

as per your comment. I have confirmed the current code does not give the correct results when compared to the original BigInteger.

Serialization not working: java.lang.SecurityException: Unsafe

BigInteger serialization not working due to UnsafeHolder (line 5633) which holds sun.misc.Unsafe:

java.lang.SecurityException: Unsafe
	at sun.misc.Unsafe.getUnsafe(Unsafe.java:90)

Can you give some workaround?

Thanks!

java.lang.ArrayIndexOutOfBoundsException: 10

Hi, I am using your BigInt to implement a encryption algorithm. By testing, your BigInt has a better performance than BigInteger, so thanks for you creating a so excellent BigInt. But I occured one problem.
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10 at com.zqx.ivhe.BigInt.subMag(BigInt.java:1153) at com.zqx.ivhe.BigInt.add(BigInt.java:1172)

I need to calcuate multiplication between a vector and a matrix, the size of them is (1025) (1025,1025). The element of the vector and matrix is a BigInt Object, and every element is a very big integer. I test for another vector and matrix with size of (65), (65,65) and successfully. But the size of them is (1025) (1025,1025) occur the above problem.
Please help me.
Thansk.