找回密码
 欢迎注册
楼主: liangbch

[擂台] 计算百万位e

[复制链接]
 楼主| 发表于 2008-4-17 11:20:17 | 显示全部楼层
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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-17 11:26:36 | 显示全部楼层
能不能如计算$n!$那样
对数据进行因数分解
再进行更高效的合并?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-17 11:37:14 | 显示全部楼层
回 无心人, 我以为:计算e的算法几乎已经基本到头了(可以再提高,但提高的幅度非常有限),其提高速度的关键是大数乘法。
计算e的效率不如pi?
计算e的算法已经很好了,效率也不会有本质的改进了,在重申一次,提高速度的关键在于提高大数乘法的效率。
计算e和计算阶乘很相像,当然后者更简单一些,编写过计算大数阶乘的人都知道,做乘法时,要尽量使2个乘数长度相当。使用单精度整数 乘以 大整数 只会使速度更慢。
  采用分解质因素的方法我以为不可行,因为计算e的算法比计算阶乘法复杂,经常需要对相邻的几个数进行相乘。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-17 11:38:59 | 显示全部楼层


也就是说
除非发现更好的极限表示?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-17 11:45:27 | 显示全部楼层
原帖由 无心人 于 2008-4-17 11:38 发表


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


这几乎是不可能的。我没有做个精确分析,但估计计算e到n位有效数字 同 计算两个 n 位大整数乘法的复杂度相同,这已经几乎是一个O(n)的算法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-17 12:26:17 | 显示全部楼层
原帖由 无心人 于 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 的大数乘法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-17 13:50:44 | 显示全部楼层


说过啦
NTT+CRT 不等于FNT
NTT是数论变换
FNT是费马数变换
MNT是麦森数变换
还有三项式变换
还有伪费马数变换
NTT+CRT仅是其中为减少字长而衍生的变种

FNT变换只需要移位和加减法
FNT大乘法包括三次变换和中间的乘法, 而且FNT大乘法的中间乘法也是可以用FNT加速的
有定论的,在适当长度上,NTT算法以FNT最快速
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-17 13:51:44 | 显示全部楼层
FFT计算大数乘法存在几个问题
1、中间结果存在不确定性,所以要预留精度
2、目前的CPU浮点数计算精度有限,所以用于大整数计算的可变换长度是有最大值的

另外一个问题就是,GxQ的NTT+CRT算法并不是大整数最快速的算法
包括GMP都不是

乘法的最快速算法是以极端的复杂和大的空间占用为代价的
好像目前的工业级算法库都没实现吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-17 14:11:35 | 显示全部楼层
反过来
目前的FFT因为流程简单
也解决了非2次幂的算法的问题
所以很容易优化到骨头

而NTT目前的限制在于$M, N, \alpha$值相互关联,且如果$M, N, \alpha$
不合适,则需要扩充到合适的长度,很容易浪费时间和空间

而适用范围很大的参数的组合很可能需要若干种NTT的组合才能达到
即一个范围用FNT一个范围用伪FNT一个范围用三项式变换等等
造成算法库极度复杂
这就是目前没有算法库实现全部NTT算法的原因
GMP也只能称目前最快的库
他不敢称最快的库吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-17 14:12:06 | 显示全部楼层

我的测试数据

这是在我的机器上的运行结果:
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 兄再测试一遍?

HighCalc.rar

235.42 KB, 下载次数: 16, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

cxliucalchigh - 2007-01-28

pifast.zip

152.96 KB, 下载次数: 3, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

pifast V4.3

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 03:37 , Processed in 0.047762 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表