如何增加太字节大小的数字？

Question

当乘以非常大的数字时,可以使用基于FFT的乘法(参见Schönhage-Strassen算法).出于性能原因,我正在缓解旋转因素.问题是对于大量(技嘉大小)我需要大小为2 ^ 30或更多的FFT表,这占用了太多的RAM(16 GB及以上).所以我似乎应该使用另一种算法.

有一个名为y-cruncher的软件,用于计算Pi和其他常数,它们可以乘以太字节大小的数字.它使用称为混合NTT的算法和另一种称为VST的算法(参见VST乘法算法部分中的A峰到y-cruncher v0.6.1).

任何人都可以对这些算法或任何其他可用于乘以TB级数字的算法有所了解吗？

Answer 1

FFT可以在具有恒定数量的额外存储器的相同阵列上完成(可能需要巧妙地交换数字).因此它也可以在硬盘上完成.在最坏的情况下,它是磁盘访问的日志(N)*N倍.它似乎比在RAM上做得慢得多,但整体复杂性仍然相同.