数学研发论坛

 找回密码
 欢迎注册
楼主: 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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-2-21 03:24:56 | 显示全部楼层
Ickiverar 发表于 2015-11-24 22:14
PiFast是使用的10^k进制进行内部计算的,输出基本不用时间。
算得比我用二进制还要快。
果然是非常优化了 ...

我实现 十进制里面使用类似SSA算法的处理是这样的!

比如 在SSA 算法里面, 使用 2为 N阶根, 2^(N/2) + 1为模的情况下处理。
在十进制里面  那么  就使用 10为N阶根, 10^(N/2) + 1为模的情况下处理。

途中,SSA 里面乘 2^x的移位处理, 在10进制里面的处理就变成 乘以10^x 来处理。
乘10^x 实际上只比2^x稍微复杂那么一丁点.速度上慢一些, 但是实际效果比 进制变换花费的实际要少很多.

当时测试的时候,也想过不使用10作为N阶根, 而是直接使用10^9(一个int保存的最大值)作为N阶根, 这样的话,乘以10^x 所需要使用的乘除法都可以省略,直接只剩下移位
(当然2进制里面也可以使用类似的办法, 使用2^31 作为N阶根,那样也就是连移位都不用处理,)
但是由于这样处理的话, 能处理的数据长度变小很多,我这边的测试,这个10^9作为N阶根, 并不比10作为N阶根快, 放弃这样的处理。

之后不久就发现了GPU这个新大陆, 之后的更细节优化处理觉得意义不大,就不再继续, 而改用GPU来进行计算。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-2-21 08:57:35 | 显示全部楼层
prime95是不是有源代码?加减乘除有现成的源代码,为什么要自己写呢?这个软件肯定比你快多了成熟多了!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-2-21 15:09:13 | 显示全部楼层
mathematica 发表于 2019-2-21 08:57
prime95是不是有源代码?加减乘除有现成的源代码,为什么要自己写呢?这个软件肯定比你快多了成熟多了!

看过一下,  似乎是调用了GMP库。
有些奇怪, 自身上还包含了OOURA 分裂基FFT , 而且FFT似乎有很多个实现,
中间有一堆的ASM 文件还带SSE指令集, 看起来对我来说直接就是一个折磨。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-4-25 23:43 , Processed in 0.052951 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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