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 回答