数学研发论坛

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

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

[复制链接]
 楼主| 发表于 2015-11-23 23:25:04 | 显示全部楼层
输出算法写完了。
接楼上,虽然我10秒不到就算出了根2的值,但我要用120秒来输出它。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-11-24 13:11:34 | 显示全部楼层
如果采用10^k进制,输出时间就快了。

/thread-143-1-10.html中,我写了个计算sqrt(2)程序,下面是性能数据。

调用站长的Hugecalc,计算sqrt(2)的性能数据
|10进制位数|计算时间|输出到文件时间|
|100000|0.064|0.135|
|1000000|0.552|0.166|
|10000000|8.026|1.852|

测试环境:Windows XP SP2,Intel Pentium 4 CPU 2.93GHz,512MB DDR - 133MHz
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-11-24 13:20:59 | 显示全部楼层
楼主可以和Pifast比较一下。
在我的Core2 Duo CPU E8500 3.16GHZ CPU, 计算6800万位sqrt(2),pifast4.3总时间为18.42秒。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2015-11-24 22:14:07 | 显示全部楼层
PiFast是使用的10^k进制进行内部计算的,输出基本不用时间。
算得比我用二进制还要快。
果然是非常优化了的。
计算根2,67108864 位用时五秒多,
计算圆周率1000万位用十六秒多。我要用40秒,其中11秒多用来输出。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-12-7 17:47:07 | 显示全部楼层
 我一直在想,对于通常规模的大数乘法,其于小质数模(在32位系统模小于2^32,在64位系统模小于2^64))的快速数论变换+中国剩余定理的算法,应该比使用大的费马数模变换(SSA算法)算法更快,因为在SSA算法中,第1级费马数变换完成,计算点积时依然有很高的复杂度。只有当数的规模非常大时,计算点积时,才有必要再次使用Fermat变换算法,否则,直接乘更快。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2015-12-18 17:53:51 | 显示全部楼层
通常来说
FNT的大致的复杂度为 9nlogn
SSA的复杂度大约为 nlogn logn

FNT内限制速度的主要是 a * b % p这个运算.
这个通常为 为一个普通乘法的 4--5倍以上,因此大致时间需要放大不少.
SSA 更多依赖的我认为是 大整数的长加减法和数据移动,一般来说,这两个 和 a * b % p 这个运算的优化比较,相对容易一些.

具体实现上,我实现的SSA 大致为FNT速度的2 / 3,这个优化还不是很到位的情况的下的结果.

如果说能找到SSA能只用加法而不用减法来处理的话,估计SSA要完胜 FNT,
而FNT则基本放弃寻找更好的 p来进行优化.

点评

我觉定放弃实现SSA算法,将尝试实现一个优化的FNT算法. 32位版本用SSE2指令实现模乘法,64位版本则直接使用ALU指令,看看效果如何。  发表于 2015-12-21 10:58
我的SSA比FNT(十进制)快一倍左右……  发表于 2015-12-19 17:53
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-1-13 13:12:47 | 显示全部楼层
knate 发表于 2015-12-18 17:53
通常来说
FNT的大致的复杂度为 9nlogn
SSA的复杂度大约为 nlogn logn

最终实现的SSA大致是FNT的 1/3到 1/2之间浮动,少于 1/2
速度已经不慢于 1楼的速度.
二进制比十进制更快.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-1-13 16:08:42 | 显示全部楼层
新的MULX, ADDX指令是极大的有助于大整数乘法运算的
ADDX把对CF的依赖改为其他标志,于是可以一次并发执行多个加法流
MULX则摆脱了对RDX:RAX寄存器的结果依赖,可以更自由的使用寄存器,同样是增加了并发度

另外我觉得是时候放弃32位了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-4-17 13:21:26 | 显示全部楼层
WIN7 64
I5 @2.8GHZ
8G内存
GMT860M
的笔记本

两个大约 3000W位十进制数的相乘,
按前期的测试计算.
非常有望时间能压缩到1秒以内.
由于 以前FNT ,SSA所用的分裂基FFT并不适用.需要进行大改.
在查BUG.

补充内容 (2016-6-10 17:01):
跟之前预计的差不多。
在0.85秒左右。
可惜对资料不是熟悉,加速器内如何 快速计算32位整数的  a * b % p这个老大难问题。还不清楚有什么好的办法。
要不然可能还能提高速度。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2016-9-5 15:47:38 | 显示全部楼层
knate 发表于 2016-4-17 13:21
WIN7 64
I5 @2.8GHZ
8G内存

0.85秒,3000万位相乘……
我需要2.6秒以上……
求问你内部都用了什么算法……
我只实现了 笔算/karatsuba/SSA……
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-1-16 11:21 , Processed in 0.050800 second(s), 19 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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