数学研发论坛

 找回密码
 欢迎注册
查看: 4718|回复: 38

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

[复制链接]
发表于 2015-10-10 13:19:28 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
我用C++和x64汇编实现了二进制大整数乘法,包括 硬乘法,Karatsuba 和 SSA (Schönhage–Strassen algorithm)
没有使用任何SSE指令或者任何MMX,XMM寄存器。
测试两个 三百五十万字(约定1字=64bit=19.266十进制位)整数相乘,比HugeCalc慢约十二分之一。
intel i5 @2.6GHz,单线程 。
我的乘法:5.9s
HugeCalc:5.5s
想问SSA有什么加速技巧么?还是说我需要实现Toom-Cook 3对递归底层加速处理?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-10-10 13:32:34 | 显示全部楼层
蛮不错啊。

HugeCalc 已暂停开发好几年了,注意,只是暂停而已。
一来工作忙,二来一直在等待比较好的CPU后再继续。
就大整数计算而言,带宽越大越好,所以64位(甚至128、256位)比32位更好,
楼主已走在前面了,因为我还没写过64位下的汇编。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-10-14 22:47:13 | 显示全部楼层
能否举个例子解释下你们的SSA是如何运作的?!

比方说 基为 2^32的
A[256] 和 B[256]两个数组乘积.
这时选取的 512阶根和模值分别是多少的呢?!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2015-10-18 14:52:51 | 显示全部楼层
@knate
SSA从来不需要选择什么模值和根。
我给你个论文吧,我就是从什么都不知道开始看这个论文最后实现了SSA的。
SSA.pdf (288.63 KB, 下载次数: 39)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2015-10-18 15:04:53 | 显示全部楼层
Ickiverar 发表于 2015-10-18 14:52
@knate
SSA从来不需要选择什么模值和根。
我给你个论文吧,我就是从什么都不知道开始看这个论文最后实现 ...

http://www.loria.fr/~gaudry/publis/issac07.pdf
论文的出处网址在这里。和附件是同一个内容。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-10-21 11:46:11 | 显示全部楼层
Ickiverar 发表于 2015-10-18 15:04
http://www.loria.fr/~gaudry/publis/issac07.pdf
论文的出处网址在这里。和附件是同一个内容。


这PDF看了.就是没弄明白.
特别是和FFT搅和在一起的时候就乱套了.

P168
1.1例子
里的 1000448 分解为2^10 ,需要 1964位长度,这里是看明白了.
后面部分就看不懂了.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2015-10-23 18:37:09 | 显示全部楼层
knate 发表于 2015-10-21 11:46
这PDF看了.就是没弄明白.
特别是和FFT搅和在一起的时候就乱套了.

那说明你之前的内容没看懂。
选择K值是实现的细节,后面的都是实现的方法,如果看懂算法了就应该知道他在说什么。
算法的理论部分在第一页(167页)的右下角到第二页(168页)的前四分之三。仔细看这些吧。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-10-24 09:55:14 来自手机 | 显示全部楼层
64比特乘法在intel64位处理器上直接用乘法指令已经非常快了。但是对于位数更多的整数乘法,需要选择使用各种高级乘法,这方面gxqcn应该非常有经验
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-10-24 12:52:42 | 显示全部楼层
Ickiverar 发表于 2015-10-23 18:37
那说明你之前的内容没看懂。
选择K值是实现的细节,后面的都是实现的方法,如果看懂算法了就应该知道他 ...

终于今天完成了基本的SSA.
原来一直以为变换长度是几百W长度的.
所以想不通.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-10-30 12:14:21 | 显示全部楼层
我也一直想实现SSA算法,如果搞懂了这个,则所有关于大数乘法的算法都攻克了。自己也可以实现一个高速的大数运算库了。

问一下楼主,SSA算法对基于10^k进制的大数是否适用。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-6-25 06:24 , Processed in 0.063863 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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