数学研发论坛

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

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

[复制链接]
 楼主| 发表于 2016-9-5 15:49:51 | 显示全部楼层
最近写了ToomCook33.
正在准备写TC42和TC32.
这三个算法应该叫最小ToomCook支持……是最简单也是最必要的三个。
而且……我的电脑性能似乎有下降,同样的源码,一年前能跑进6秒,现在得6.7秒以上。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2016-9-7 23:57:52 | 显示全部楼层
ToomCook33写完,以前只用了Karatsuba。
对短字长,几十到几万字的乘法有百分之十几到至多百分之几十的加速,而对百万字以上的乘法……几乎没什么影响。
看来还得从SSA上下功夫……
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-9-29 18:24:55 | 显示全部楼层
Ickiverar 发表于 2016-9-5 15:47
0.85秒,3000万位相乘……
我需要2.6秒以上……
求问你内部都用了什么算法……

内部顶层调用的是 NTT,(FNT + CRT)
内部有 硬乘法/ karatsuba /tomm-3,4,5,
SSA已经被我注释掉了.

相信还有挖掘的潜力,我的配置还不算很高.
毕竟FNT + CRT里面的9次FFT可以通过比我现在的办法更好地并行压缩时间
不过这已经不是算法层的事了.是用钱堆出来的..

还有一个优化没做就是实现一个基16的FFT,可惜目前手上没有一个好一些的基16的FFT,


毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-1-13 20:41:13 | 显示全部楼层
有一个《Internet Mersenne Prime Search》项目,是一个分布式的梅森素数搜寻程序,在windows平台,使用prime95实现,prime95中使用了大量的汇编代码,单几个.mac(宏)文件,就超过30万行汇编代码。其大数运算既不是通常的FFT,也不是NTT,而是一个FTT的变种,叫做Irrational base discrete weighted transform,这个算法的提出者是Richard E. Crandall,参见 https://en.wikipedia.org/wiki/Richard_Crandall。作者已在5年前去世。其算法请参阅论文Discrete weighted transforms and large-integer arithmetic
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

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

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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