数学研发论坛

 找回密码
 欢迎注册
楼主: 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指令集, 看起来对我来说直接就是一个折磨。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-1-8 11:44:58 | 显示全部楼层
小小嘚瑟 !
终于在  笔记本上追上了HugeCalc8 (无注册) 的速度了.
[ ( (10^9) ^ 3670016 - 1 ) / 11]  * [ ( (10^9) ^ 3670016 - 1 ) / 11]    (不能再大了. 数据量翻倍HugeCalc8 会挂掉)
硬件条件:
戴尔 vostro 3400  11代I5 1135 @ 3.8G   16G 内存, SSD 固态 轻负载情况下.
在1.1-1.4秒左右.   
HugeCalc8  基本在1.2秒附近.
基本认为速度已经相差无几了.满足了

PS:
联想R9000P  3060TI
下运行实际不会超过0.7秒.

在双显卡台式机,配置更好的.
一般在0.5x , 不会超过0.6秒.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-1-9 18:48:46 | 显示全部楼层
@knate

同样的计算,我也在我的电脑上(i7-7700HQ @ 2.8GHz,睿频3.6 GHz)试了一下我的库(四年没更新了)和MMA(均为单线程;内部都使用二进制,所以输出结果需要进制转换,会比较慢),结果如下:

屏幕截图 2022-01-09 183512.png

显然MMA是自动用平方计算乘法的,c = a*b 和 d = a^2 耗时一样,比我用平方稍微慢点。而它的进制转换输出比我慢将近40%
附件是测试用程序和MMA文件,你可以在你的电脑上试试结果。

MulTest.zip (116.15 KB, 下载次数: 4)

点评

后面优化方向预计是以下几个, X64,基16的FFT, GMP内的有限域看有没有可能使用蒙哥马利约化. 第三个可能性有点小, 事关发现 转换后,对于任意长度的加(减)法链,这个居然是不成立的. FFT配合toom-cook试验过很差,  发表于 2022-1-12 09:16
虽然叫实现了toom-cook 实际跟直接抄过来差不多. X86下编译的. 后面看有没有可能改到X64下,目前实在没时间和精力玩这个玩意.  发表于 2022-1-12 09:09
我的库 使用了多线程. FFT 分两种情况 一种 CPU 内调用的是oouraFFT , 一种是GPU 使用的是基4FFT (两者不能混用,oouraFFT 没有逆序). 更小规模下toom-cook 实现了toom 5 以下的所有(55,54,53,52,44,43....22)  发表于 2022-1-12 09:05
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-1-10 08:47:24 | 显示全部楼层
Ickiverar 发表于 2022-1-9 18:48
@knate  

同样的计算,我也在我的电脑上(i7-7700HQ @ 2.8GHz,睿频3.6 GHz)试了一下我的库(四年没 ...

你这个我运行了. multiply 0.6x ,square 0.4x
进制转换10秒左右.
你这个库CPU 运行效率比我的高多了.

自己的CPU 运行 使用的是基于 oouraFFT 改造的FFT模板.
稍微测试过. 运行时间大约只有这论坛上的 60--75%左右(大约估计),(基本相当于 它的1.2秒,大约运行2秒左右)

我的库计算最终是基于GPU计算的. CPU 由于没有调用SSE ,也没有什么汇编(仅仅有十来个基础函数,几十百来行嵌入汇编),效率上,比你们的都低很多很多 ,没法比的.

但是GPU计算和多线程关系不大, 这边测试单线程和多线程并发, 时间上差距不会超过10% 预计在5%左右. 影响不大.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2022-5-20 08:20 , Processed in 0.083188 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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