计算百万位e

liangbch

7# 提到的算法实际上和 http://numbers.computation.free.fr/Constants 网站所说的 Binary splitting method 是一致的， http://numbers.computation.free.fr/Constants 关于Binary splitting method的论述非常数学化，不易理解。所以我在7#对计算e的算法给出一个容易理解的算法。Binary splitting method 原文请参见 http://numbers.computation.free.fr/Constants/Algorithms/splitting.html

无心人

能不能如计算$n!$那样 对数据进行因数分解 再进行更高效的合并？

liangbch

回 无心人， 我以为：计算e的算法几乎已经基本到头了（可以再提高，但提高的幅度非常有限），其提高速度的关键是大数乘法。

计算e的效率不如pi？

计算e的算法已经很好了，效率也不会有本质的改进了，在重申一次，提高速度的关键在于提高大数乘法的效率。 计算e和计算阶乘很相像，当然后者更简单一些，编写过计算大数阶乘的人都知道，做乘法时，要尽量使2个乘数长度相当。使用单精度整数 乘以 大整数 只会使速度更慢。 采用分解质因素的方法我以为不可行，因为计算e的算法比计算阶乘法复杂，经常需要对相邻的几个数进行相乘。

无心人

也就是说 除非发现更好的极限表示？

liangbch

原帖由 无心人 于 2008-4-17 11:38 发表 也就是说 除非发现更好的极限表示？

这几乎是不可能的。我没有做个精确分析，但估计计算e到n位有效数字 同 计算两个 n 位大整数乘法的复杂度相同，这已经几乎是一个O(n)的算法。

liangbch

原帖由 无心人 于 2008-4-17 11:09 发表 另外 任何FFT均慢于最优化的NTT

你是怎么得出这个结论的？我们可以比较一下这两者的差异。 假如 我们需要做 2个n 位有效数字的乘法，当n不是特别大时（比如1000万） 用 FFT 每个复数的虚部和实部 可表示4位有效数字（参见http://topic.csdn.net/u/20071224 ... d-b2a01ddc388f.html）， 采用实数变换算法 变换长度 Len1= n/4 *2 则需要 1）对被乘数和乘数各种1次长为Len1的正变换 3）计算两者的内积 4）做一次逆变换 （共3次FFT) 用 FNT 每个元素 可表示9位有效数字，采用FNT变换，变换长度 Len2= n/9 *2（可参见apfloat) 1.需要6次FNT 变换，3次FNT 逆变换 2.需要1次 利用CRT((中国剩余定理）求结果的过程。 利用FNT计算大数乘法的算法可参考：http://topic.csdn.net/t/20040720/09/3190781.html 我们略去耗时较小的CRT，求内积过程，仅当FNT的效率达到FFT的 133%以上，FNT计算大数乘法才比FFT计算大数乘法更有优势。 上述的说明是以 1000万位数字而言的，当计算长度小于这个值，比如几十万，则FFT的变换长度仅为n/5 *2，如此则FFT更有优势。 在一般情况下，FFT/FNT的效率之比如何，我尚没有得到准确的数字，不知无心人何以得出FNT快于FFT的结论。 另外，刘楚雄的阶乘计算器证实，当不使用SSE2指令优化程序时，gxq的使用FNT算法的大数乘法 要 慢于 刘楚雄 使用 ooura FFT 的大数乘法。

无心人

说过啦 NTT+CRT 不等于FNT NTT是数论变换 FNT是费马数变换 MNT是麦森数变换 还有三项式变换 还有伪费马数变换 NTT+CRT仅是其中为减少字长而衍生的变种 FNT变换只需要移位和加减法 FNT大乘法包括三次变换和中间的乘法， 而且FNT大乘法的中间乘法也是可以用FNT加速的 有定论的，在适当长度上，NTT算法以FNT最快速

无心人

FFT计算大数乘法存在几个问题 1、中间结果存在不确定性，所以要预留精度 2、目前的CPU浮点数计算精度有限，所以用于大整数计算的可变换长度是有最大值的 另外一个问题就是，GxQ的NTT+CRT算法并不是大整数最快速的算法 包括GMP都不是 乘法的最快速算法是以极端的复杂和大的空间占用为代价的 好像目前的工业级算法库都没实现吧

无心人

反过来 目前的FFT因为流程简单 也解决了非2次幂的算法的问题 所以很容易优化到骨头 而NTT目前的限制在于$M, N, \alpha$值相互关联，且如果$M, N, \alpha$ 不合适，则需要扩充到合适的长度，很容易浪费时间和空间 而适用范围很大的参数的组合很可能需要若干种NTT的组合才能达到 即一个范围用FNT一个范围用伪FNT一个范围用三项式变换等等 造成算法库极度复杂 这就是目前没有算法库实现全部NTT算法的原因 GMP也只能称目前最快的库 他不敢称最快的库吧

gxqcn

这是在我的机器上的运行结果：

calculate e (fast version1) defined 'MODIFIED_BY_GxQ' How many digital is needed(0 will exit)?100000 计算用时 0.389722 秒 其中除法用时 0.140000秒 输出到文件用时 0.008421 秒 How many digital is needed(0 will exit)?1000000 计算用时 3.357377 秒 其中除法用时 1.359000秒 输出到文件用时 0.053458 秒 How many digital is needed(0 will exit)?

我用北大刘楚雄老师最新的版本（2007-01-28 发给我的，比公开的提速不少），测试结果如下：

计算精度：100000 0.427517s 计算精度：1000000 2.731985s

时间比 3.357377 / 2.731985 = 1.2289 而楼主的测试结果为（数据分别见：9#、24#）： 时间比 8.35 / 3.50 = 2.39 感觉比值差异太大。可否请 liangbch 兄再测试一遍？