如何计算千兆字节级别的数字乘积？

Question

当乘以非常大的数字时，您可以使用基于FFT的乘法（参见Schönhage–Strassen algorithm）。出于性能原因，我正在缓存旋转因子。问题是对于巨大的数字（占用几GB），我需要2 ^ 30及更大的FFT表，这将占用太多RAM（16 GB或以上）。因此，似乎我应该使用另一种算法。

有一个名为y-cruncher的软件，用于计算Pi和其他常数，可以乘以千兆字节级别的数字。它使用称为Hybrid NTT的算法和另一个称为VST的算法（请参见A Peak into y-cruncher v0.6.1中的The VST Multiplication Algorithm部分）。

有人可以介绍这些算法或任何其他可用于乘以千兆字节级别的数字的算法吗？

- iblue

---

我将此投票为“范围过大”，因为对于“如何实现外部存储整数乘法”的好答案可能不会很简短。然而，由于Mysticial是一个活跃的SO贡献者，如果确实有人给出了好的答案，我很乐意取消我的关闭投票。 - tmyklebu

没问题。除了数字不是1234567890，而是有10^12位数。我不想求它的平方，而是想要两个任意数的乘积。并且我希望它能快速计算。普通学校的方法运行时间为O(n^2)。 - iblue

是的，@chux，我想计算两个n,m大小为1TB的数字的确切n+m（或n+m-1）大小的乘积。 - iblue

Jerry说得很对。重点在于实现而不是算法。如果你遇到的问题是twiddle因子，记住缓存twiddle因子是一种时空权衡。你不必处于权衡的任何极端。如果你需要将它们交换到磁盘上，考虑动态生成它们可能是值得的。所以你可以缓存一些，但不是所有的twiddles。此外，Schönhage-Strassen算法不需要twiddle因子，因为它们会退化为移位。 - Mysticial

特别是对于Schönhage-Strassen算法，它是NTT的一种特殊情况。这是目前已知唯一具有微不足道旋转因子的算法。(旋转因子都是二的幂次方，所以它们不需要被缓存。) - Mysticial

Answer 1

FFT可以在同一个数组上进行，只需额外使用少量的内存（可能需要巧妙地交换数字）。因此，它也可以在硬盘上执行。最坏情况下，需要对硬盘进行log(N)*N次访问，看起来比在RAM上执行要慢得多，但总体复杂度保持不变。

- DU Jiaen

---

复杂度可能保持不变，但实际读取时间要慢得多。不要忘记这些常数因素在实践中很重要。 - wchargin

它仅需要对整个数组进行log(N)次顺序硬盘访问，应该比随机访问快得多。如果您以聪明的方式实现FFT（在开头重新排列数字），则会更快。 - DU Jiaen

对于大于4GB的数字，我可以通过FFT将10位或更少的数字适配到一个复杂的数据点中（2个双精度浮点数=128位），因此如果我对其进行FFT，则必须编写实际数字大小的12.8倍。这样做效率不高。 - iblue