ibl*_*lue 30 c performance arbitrary-precision
我想计算e到2万亿(2,000,000,000,000)个数字.这约为1.8 TiB的纯e.我刚刚使用GMP实现了一个泰勒系列扩展算法(代码可以在这里找到).
不幸的是,当我在计算机上总计超过4000个术语时,它会崩溃,可能是因为内存不足.
计算e的当前技术水平是什么？哪种算法最快？任何值得关注的开源实现？请不要提及y-cruncher,这是封闭的来源.
Mys*_*ial 63
由于我是你提到的y-cruncher程序的作者,我将加上我的2美分.
对于这么大的任务,必须解决的两个最大障碍如下:
记忆
2万亿位是极端的 - 至少可以说.这是Shigeru Kondo和我自己在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)并结合以下算法:
幸运的是,GMP已经使用了基于FFT的大型乘法.但它缺乏两个关键特征:
第二点并不重要,因为你可以等待更长时间.但是出于所有实际目的,你可能需要推出自己的产品.这就是我写y-cruncher时的所作所为.
也就是说,还有许多其他松散的东西需要照顾:
由于你有一个目标你想要多少位数(2万亿),你可以估计你需要计算e多少个数字到这个位数.由此,您可以估计需要跟踪的精确度的额外数字,以避免在2万亿分之一处出现舍入误差.
如果我根据斯特林的近似计算是正确的,那么10到2万亿的倒数大约相当于1000亿阶乘的倒数.这就是你需要多少个术语(1000亿).不过,这个故事要好一点,因为在此之前你就可以在计算条款时丢掉很多数字了.
由于e计算为逆因子的总和,因此所有项均为有理数,因此它们可表示为重复小数.因此,您的术语的十进制扩展将是(a)指数,(b)非重复部分,以及(c)重复部分.如果以这种方式查看术语,可以利用一些效率.
无论如何,祝你好运!