http://numbers.computation.free.fr/Constants 关于Binary splitting method的论述非常数学化，不易理解。所以我在7#对计算e的算法给出一个容易理解的算法。Binary splitting method 原文请参见 http://numbers.computation.free.fr/Constants/Algorithms/splitting.html 能不能如计算$n!$那样
对数据进行因数分解
再进行更高效的合并？ 回 无心人， 我以为：计算e的算法几乎已经基本到头了（可以再提高，但提高的幅度非常有限），其提高速度的关键是大数乘法。
计算e的效率不如pi？计算e的算法已经很好了，效率也不会有本质的改进了，在重申一次，提高速度的关键在于提高大数乘法的效率。
计算e和计算阶乘很相像，当然后者更简单一些，编写过计算大数阶乘的人都知道，做乘法时，要尽量使2个乘数长度相当。使用单精度整数 乘以 大整数 只会使速度更慢。
采用分解质因素的方法我以为不可行，因为计算e的算法比计算阶乘法复杂，经常需要对相邻的几个数进行相乘。 :)
也就是说
除非发现更好的极限表示？ 原帖由 无心人 于 2008-4-17 11:38 发表 static/image/common/back.gif
:)
也就是说
除非发现更好的极限表示？
这几乎是不可能的。我没有做个精确分析，但估计计算e到n位有效数字 同 计算两个 n 位大整数乘法的复杂度相同，这已经几乎是一个O(n)的算法。 原帖由 无心人 于 2008-4-17 11:09 发表 static/image/common/back.gif
另外
任何FFT均慢于最优化的NTT
你是怎么得出这个结论的？我们可以比较一下这两者的差异。
假如 我们需要做 2个n 位有效数字的乘法，当n不是特别大时（比如1000万）
用 FFT 每个复数的虚部和实部 可表示4位有效数字（参见http://topic.csdn.net/u/20071224/23/9536bf4f-baab-434e-9b2d-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也只能称目前最快的库
他不敢称最快的库吧
我的测试数据
这是在我的机器上的运行结果：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 兄再测试一遍？