Java 大数快速乘法库

Question

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

Answer 1

就我的思维能力而言Karatsuba Algorithm可以这样实现：

This link 提供了相同的 C++ 实现，这也可以很容易地用于 Java 之类的实现。

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

您 link 的解决方案 — Schönhage-Strassen — 确实是使非常非常大的 BigIntegers 相乘更快的好方法。

由于开销很大，对于更小的 BigIntegers 来说它并不快，所以你可以使用它，递归地下降到某个阈值（你必须凭经验找出那个阈值是什么）然后使用 BigInteger 的自己的乘法，它已经实现了 Toom-Cook 和 Karatsuba divide-and-conquer 算法（自 Java 8，IIRC），也递归到某些阈值。

忘记告诉你使用 Karatsuba 的答案。 Java 不仅已经实现了这个，而且速度更快（对于非常大的 BigIntegers）Toom-Cook 算法，它也比 Schönhage-Strassen.

慢很多（对于如此巨大的值）

结论

同样：对于小值，使用简单的教科书乘法（但使用 – 无符号 – 整数如 "digits" 或 "bigits"）。对于更大的值，使用 Karatsuba（这是一种递归算法，将大的 BigIntegers 分解为几个较小的值并将它们相乘——divide-and-conquer 算法）。对于更大的 BigIntegers，使用 Toom-Cook（也是 divide-and-conquer）。对于非常大的 BigIntegers，使用 Schönhage-Strassen（IIRC，一种 FFT-based 算法）。请注意，Java 已经为不同大小的 Bigintegers 实现了教科书（或 "base case"）、Karatsuba 和 Toom-Cook 乘法。它还没有实现 Schönhage-Strassen。

但即使进行了所有这些优化，非常大的值的乘法往往很慢，所以不要指望奇迹。

注：

Schönhage-Strassen 算法你 link 恢复到 Karatsuba 更小 sub-products。从那时起（2012 年圣诞节），BigInteger 中的实现有了很大改进，而不是 Karatsuba，而是直接使用 BigInteger::multiply()，而不是 Karatsuba。您可能还必须更改使用的阈值。

Java 大数快速乘法库

Java library for fast multiplication of very big numbers

java

biginteger

multiplication

结论

注：