二进制大整数乘法

Ickiverar · 发表于 2016-9-5 15:49:51

最近写了ToomCook33.
正在准备写TC42和TC32.
这三个算法应该叫最小ToomCook支持……是最简单也是最必要的三个。
而且……我的电脑性能似乎有下降，同样的源码，一年前能跑进6秒，现在得6.7秒以上。

Ickiverar · 发表于 2016-9-7 23:57:52

ToomCook33写完，以前只用了Karatsuba。
对短字长，几十到几万字的乘法有百分之十几到至多百分之几十的加速，而对百万字以上的乘法……几乎没什么影响。
看来还得从SSA上下功夫……

knate · 发表于 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,

liangbch · 发表于 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。

knate · 发表于 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来进行计算。

mathematica · 发表于 2019-2-21 08:57:35

prime95是不是有源代码?加减乘除有现成的源代码,为什么要自己写呢?这个软件肯定比你快多了成熟多了!

knate · 发表于 2019-2-21 15:09:13

mathematica 发表于 2019-2-21 08:57
prime95是不是有源代码?加减乘除有现成的源代码,为什么要自己写呢?这个软件肯定比你快多了成熟多了!

看过一下，似乎是调用了GMP库。
有些奇怪，自身上还包含了OOURA 分裂基FFT ，而且FFT似乎有很多个实现，
中间有一堆的ASM 文件还带SSE指令集，看起来对我来说直接就是一个折磨。

knate · 发表于 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秒.

Ickiverar · 发表于 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, 下载次数: 12)

（我注意到你提到了显卡，你的算法需要用到显卡吗？或者CPU多线程？）

knate · 发表于 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%左右. 影响不大.

账号		自动登录	找回密码
密码			欢迎注册

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

点评