c - 将 e 计算到 2 万亿位的最快方法是什么？

Question

我想计算 e 到 2 万亿 (2,000,000,000,000) 位数字。这大约是 1.8 TiB 的纯 e。我刚刚使用 GMP 实现了泰勒级数展开算法(code can be found here)。

不幸的是，在我的计算机上对超过 4000 个项求和时它崩溃了，可能是因为它耗尽了内存。

计算 e 的当前技术水平如何？哪种算法最快？任何值得关注的开源实现？请不要提及 y-cruncher，它是闭源的。

Answer 1

因为我是 y-cruncher 的作者你提到的程序，我会加我的 2 美分。

对于如此庞大的任务，必须解决的两个最大障碍如下:

1. 内存
2. 运行时复杂度

内存

2 万亿位是极端 - 至少可以这么说。这是 current record set by Shigeru Kondo and myself back in 2010 的两倍. (使用 y-cruncher 计算 1 万亿位数字花了我们 9 天多的时间。)

在纯文本中，十进制约为 1.8 TiB。在压缩二进制表示中，这是 773 GiB。

如果您要对这种大小的数字进行算术运算，您将需要 每个操作数 773 GiB(不包括暂存内存)。

实际上，y-cruncher 实际上需要 8.76 TiB 的内存 才能在 ram 中完成此计算。因此，您可以预期其他实现最多需要相同的系数 2。

也就是说，我怀疑您是否有足够的内存。即使你这样做了，它也会是大量的 NUMA。所以另一种方法是使用磁盘。但这并非微不足道，为了提高效率，您需要将内存视为缓存并对内存和磁盘之间传输的所有数据进行微观管理。

---

运行时复杂度

这里我们还有另一个问题。对于 2 万亿位数字，您将需要一个非常快速的算法。不仅仅是任何快速算法，而是一种准线性运行时算法。

您当前的尝试运行时间约为 O(N^2)。所以即使你有足够的内存力，它也不会在你的一生中完成。

将 e 计算为高精度的标准方法在 O(N log(N)^2) 中运行，并结合了以下算法:

• Binary Splitting e 的泰勒级数展开。
• FFT-based large multiplication

幸运的是，GMP 已经使用了基于 FFT 的大乘法。但它缺少两个关键特性:

1. 在内存不足时使用磁盘进行核外(交换)计算。
2. 它不是并行化的。

第二点并不重要，因为您可以等待更长的时间。但出于所有实际目的，您可能需要推出自己的产品。这就是我在编写 y-cruncher 时所做的。

---

也就是说，还有许多其他的零散问题也需要处理:

1. 最后的除法将需要像牛顿法这样的快速算法。
2. 如果您要进行二进制计算，则需要进行基数转换。
3. 如果计算需要大量时间和资源，您可能需要实现容错来处理硬件故障。