用于非常大的数字的快速乘法的 Java 库

Question

我正在编写一个程序，该程序需要在某个点乘以非常大的数字(百万位)。任何人都可以建议一个 java 库来快速乘以大数吗？我找到了 this ，但我不确定这是否是正确的解决方案，所以我正在尝试寻找其他解决方案。

Answer 1

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

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

忘记告诉您使用 Karatsuba 的答案。Java 不仅已经实现了这一点，甚至更快(对于非常大的 BigIntegers)Toom-Cook 算法，它也慢得多(对于如此巨大的值(value))比 Schönhage-Strassen。

结论

同样:对于小值，使用简单的教科书乘法(但使用 – 无符号 – 整数作为“digits”或“bigits”)。对于更大的值，使用 Karatsuba(这是一种递归算法，将大的 BigIntegers 分解为几个较小的值并将它们相乘——一种分而治之的算法)。对于更大的 BigIntegers，使用 Toom-Cook(也是分而治之)。对于非常大的 BigIntegers，请使用 Schönhage-Strassen(IIRC，一种基于 FFT 的算法)。请注意，Java 已经为不同大小的 Bigintegers 实现了教科书(或“基本案例”)、Karatsuba 和 Toom-Cook 乘法。它尚未实现 Schönhage-Strassen。

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

---

注意事项:

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