用于超大数快速乘法的biginteger Java库

Question

我正在写一个程序，需要在一个点上乘以非常大的数字（百万位数）。有人能推荐一个java库来实现大数的快速乘法吗？我找到了this，但我不确定这是否是正确的解决方案，所以我正在尝试另一种方法

Answer 1

就我的思维能力而言Karatsuba Algorithm可以通过以下方式实现：

^ a2}链接提供了C++的相同实现，这也可以很容易地被用于类似java的实现。p>

import java.math.BigInteger;
import java.util.Random;

class Karatsuba {
    private final static BigInteger ZERO = new BigInteger("0");

    public static BigInteger karatsuba(BigInteger x, BigInteger y) {

        // cutoff to brute force
        int N = Math.max(x.bitLength(), y.bitLength());
        if (N <= 2000) return x.multiply(y);                // optimize this parameter

        // number of bits divided by 2, rounded up
        N = (N / 2) + (N % 2);

        // x = a + 2^N b,   y = c + 2^N d
        BigInteger b = x.shiftRight(N);
        BigInteger a = x.subtract(b.shiftLeft(N));
        BigInteger d = y.shiftRight(N);
        BigInteger c = y.subtract(d.shiftLeft(N));

        // compute sub-expressions
        BigInteger ac    = karatsuba(a, c);
        BigInteger bd    = karatsuba(b, d);
        BigInteger abcd  = karatsuba(a.add(b), c.add(d));

        return ac.add(abcd.subtract(ac).subtract(bd).shiftLeft(N)).add(bd.shiftLeft(2*N));
    }


    public static void main(String[] args) {
        long start, stop, elapsed;
        Random random = new Random();
        int N = Integer.parseInt(args[0]);
        BigInteger a = new BigInteger(N, random);
        BigInteger b = new BigInteger(N, random);

        start = System.currentTimeMillis(); 
        BigInteger c = karatsuba(a, b);
        stop = System.currentTimeMillis();
        StdOut.println(stop - start);

        start = System.currentTimeMillis(); 
        BigInteger d = a.multiply(b);
        stop = System.currentTimeMillis();
        StdOut.println(stop - start);

        StdOut.println((c.equals(d)));
    }
}

希望这能很好地回答你的问题

Answer 2

你链接到的解决方案——Schönhage Strassen——确实是一个让非常大的大整数相乘更快的好方法

由于大的开销，小得多的大整数的运算速度并不快，所以你可以使用它，递归地降低到某个阈值（你必须从经验上找出这个阈值是什么），然后使用大整数自己的乘法，它已经实现了Toom Cook和Karatsuba分治算法（从Java 8开始，IIRC），也递归下降到某些阈值

忘记告诉你如何使用Karatsuba的答案Java不仅已经实现了这一点，而且实现了更快（对于非常大的大整数）的Toom Cook算法，它还比Schönhage Strassen慢得多（对于如此大的值）

结论

同样：对于较小的值，使用简单的教科书乘法（但使用–无符号–整数作为“数字”或“大整数”）。对于更大的值，请使用Karatsuba（这是一种递归算法，将大整数分解为几个小整数，并将它们相乘，形成分治算法）。对于更大的大整数，使用Toom Cook（也是一种分而治之的方法）。对于非常大的大整数，请使用Schönhage Strassen（IIRC，一种基于FFT的算法）。请注意，Java已经为不同大小的大整数实现了教科书（或“基本情况”）、Karatsuba和Toom Cook乘法。它还没有实施舍恩哈格·斯特拉森

但即使有了所有这些优化，非常大的值的乘法也往往很慢，所以不要期待奇迹出现

---

注：

您链接到的Schönhage-Strassen算法对于较小的子产品恢复到Karatsuba。取而代之的是Karatsuba，从那时起（2012年圣诞节），BigInteger中的实现得到了很大的改进，只需直接使用BigInteger::multiply()，而不是Karatsuba。您可能还必须更改使用的阈值