c - 如何乘以 TB 大小的数字？

Question

当乘以非常大的数字时，您使用基于 FFT 的乘法(参见 Schönhage–Strassen algorithm)。出于性能原因，我正在缓存旋转因子。问题是对于巨大的数字(千兆字节大小)我需要大小为 2^30 或更大的 FFT 表，它们占用太多 RAM(16 GB 及以上)。所以看来我应该使用另一种算法。

有一个叫y-cruncher的软件，用来计算Pi和其他常量，可以乘以TB级的数字。它使用一种称为 Hybrid NTT 的算法和另一种称为 VST 的算法(请参阅 VST 乘法算法 部分中的 A Peak into y-cruncher v0.6.1)。

谁能阐明这些算法或任何其他可用于乘以 TB 大小的数字的算法？

Answer 1

FFT 可以在具有恒定数量的额外内存的同一阵列上完成(可能需要巧妙地交换数量)。因此它也可以在硬盘上完成。在最坏的情况下，它是 log(N)*N 次磁盘访问。这似乎比在 RAM 上执行要慢很多，但总体复杂性保持不变。