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

Question

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

Answer 1

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

由于开销很大，对于更小的 BigIntegers，它不会更快，因此您可以使用它，递归地降低到某个阈值（您必须凭经验找出该阈值是什么），然后使用 BigInteger 自己的乘法，它已经实现了 Toom-Cook 和 Karatsuba 分治算法（自 Java 8，IIRC），也递归地降低到某些阈值。

忘记告诉你使用唐叶的答案吧。Java 不仅已经实现了这一点，还有更快的（对于非常大的 BigIntegers）Toom-Cook 算法，它也比 Schönhage-Strassen 慢很多（对于如此巨大的值）。

结论

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

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

笔记：

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