30

我想将e计算为 2 万亿（2,000,000,000,000）位。这大约是 1,8 TiB 的纯e。我刚刚使用GMP实现了一个泰勒级数展开算法（代码可以在这里找到）。

不幸的是，在我的计算机上汇总超过 4000 个术语时它会崩溃，可能是因为内存不足。

计算e的当前最新技术是什么？哪种算法最快？有什么值得一看的开源实现吗？请不要提及y-cruncher，它是封闭源代码。

4

2 回答 2

65

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

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

  1. 记忆
  2. 运行时复杂度

记忆

2 万亿位数是极端的——至少可以这么说。这是2010 年 Shigeru Kondo 和我自己创造的当前记录的两倍。（使用 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)并结合了以下算法：

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

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

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

也就是说，还有许多其他的松散端也需要注意：

  1. 最后的划分将需要像牛顿法这样的快速算法。
  2. 如果要以二进制计算，则需要进行基数转换。
  3. 如果计算需要大量时间和大量资源，您可能需要实现容错来处理硬件故障。
于 2012-11-09T23:04:54.947 回答
7

由于您有一个目标，您想要多少位数（2 万亿），您可以估计需要多少项来计算e该位数。由此，您可以估计需要跟踪多少额外的精度数字，以避免在第 2 万亿位出现舍入误差。

如果我从斯特林的近似计算是正确的，那么 10 到 2 万亿的倒数大约是 1000 亿阶乘的倒数。这就是您需要多少个术语（1000 亿）。不过，这个故事比这要好一些，因为在此之前，您将开始能够在计算术语时丢弃大量数字。

由于e计算为逆阶乘的总和，因此您的所有项都是有理数，因此它们可以表示为重复小数。因此，您的术语的十进制扩展将是（a）指数，（b）非重复部分，以及（c）重复部分。如果您以这种方式查看条款，您可能会利用一些效率。

无论如何，祝你好运！

于 2012-11-09T20:18:07.207 回答