数学研发论坛

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

[讨论] 二进制大整数乘法

[复制链接]
发表于 2015-10-30 15:56:36 | 显示全部楼层
mathe 发表于 2015-10-24 09:55
64比特乘法在intel64位处理器上直接用乘法指令已经非常快了。但是对于位数更多的整数乘法,需要选择使用各 ...

确实是这样,在64位模式,直接使用64位乘i法指令是最快的,SSE2,SSE4,AVX这些指令起不到加速作用。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-11-2 13:51:10 | 显示全部楼层
我就是二进制实现后,改进为基于10^9下的也可以处理

但不知还算SSA还是其他的了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-11-3 10:40:55 | 显示全部楼层
knate 发表于 2015-11-2 13:51
我就是二进制实现后,改进为基于10^9下的也可以处理

但不知还算SSA还是其他的了

好消息,不知理论上能否站得脚,可否证明。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-11-3 11:39:59 | 显示全部楼层
刚看到一篇题为《Big Integer Multiplication with CUDA FFT(cuFFT) Library》的文章,
该文的测试表明,在只有96stream单元的GT630显卡,当数的长度超过5万位时,使用
CUFA FFT的大数乘法的速度超过GMP。
原文见:http://www.ijircce.com/upload/2014/november/3_big.pdf

注:该文发表于2014年11月,文中没有提到GMP的版本。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-11-4 00:02:40 来自手机 | 显示全部楼层
只是用几十W长度左右的随机数据和比较特殊的几类数
和FNT+CRT结果对比!
得到的结论!

有个论文链接,明天上来发出来!

http://arxiv.org/pdf/1502.02800v1.pdf
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-11-4 15:10:23 | 显示全部楼层
加入两个本站资源链接,便于查找相关资料
数论变换原理简述
数论变换论文集
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2015-11-20 11:13:41 | 显示全部楼层
liangbch 发表于 2015-10-30 12:14
我也一直想实现SSA算法,如果搞懂了这个,则所有关于大数乘法的算法都攻克了。自己也可以实现一个高速的大 ...

不适用。
SSA的精妙之处在于模(2^N±1)的计算可以由二进制移位来计算。
如果是2^32或2^64进制,直接在内存中进行非常长的移位即可。如果是10^k进制,移位之后什么都不是。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-11-20 14:26:38 | 显示全部楼层
从另一种角度上,SSA算法实际上与进制无关,SSA算法的实质是,
  1. 将参于计算的被乘数和乘数切割成2^k片段,我们称之为A0和B0
  2. 然后对被乘数和乘数分别做类似于FFT的数论变换,得到A1,B1。这里数论变换的模为费马数,2^k次单位根为2的方幂。
  3. 对两个变换后的序列A1和B1做点积运算,得到C0
  4. 对C0做一次反变换得到C1
  5. 对C1做进位处理,得到最终乘积。

对于基于10进制表示的大数乘法,和基于二进制表示的大数稍有不同,
  1. 将将大数切割成2^k个片段后,需要转化为2进制表示,接下来的步骤2,3,4均为二进制运算。
  2. 在步骤5,需要将2进制表示的大数转化为10进制,并做进位处理。


和apfloat相比,SSA算法与apfloat的都采用数论变换算法。
不同点:
    1. apfloat使用的模很小,并且模m是一个质数,不超过一个机器字,需要使用不同的m,得到多个C1.最后使用中国剩余定理,得到最终结果。
      计算(x % m)没有快速算法,一般使用以乘代除法,需要使用2次乘法,并调整商; SSA使用的模m是费马数,在实践中,使用的费马数都是合数,
      它比apfloat使用的模m大得多,在计算(x % m)时有快速算法。
    2. apfloat中2^k次单位根w一般不是2的方幂,故在变换过需要使用乘法;而SSA算法中的w一般为2,4,sqrt(2), 故在变换过程不需要使用乘法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2015-11-21 01:48:33 | 显示全部楼层
无论如何。
我这里有个好消息,经过一个多月的完善,我的算法库从开始的只有整数乘法,到现在已经实现了浮点数加减乘除平方根了。效率还算不错,单线程比MMA8慢2到4倍。
我现在随时可以使用Chudovsky的算法计算圆周率的二进制表达。
等我写完进制转换和输入输出算法,就能算至少两亿位圆周率了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2015-11-21 02:11:15 | 显示全部楼层
计算三百五十万字精度的 根2 二进制浮点数值(相当于6743万位十进制精度),用时 9.51 秒,使用内存 182 MB,结果经Mathematica检验正确。
Mathematica 8 用时 5.094 秒。
虽然我的程序会慢一些,但我觉得这个比例还可以接受。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-1-16 12:49 , Processed in 0.102079 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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