最近写了ToomCook33.
正在准备写TC42和TC32.
这三个算法应该叫最小ToomCook支持……是最简单也是最必要的三个。
而且……我的电脑性能似乎有下降，同样的源码，一年前能跑进6秒，现在得6.7秒以上。
ToomCook33写完，以前只用了Karatsuba。
对短字长，几十到几万字的乘法有百分之十几到至多百分之几十的加速，而对百万字以上的乘法……几乎没什么影响。
看来还得从SSA上下功夫……
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,
有一个《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。
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来进行计算。
prime95是不是有源代码?加减乘除有现成的源代码,为什么要自己写呢?这个软件肯定比你快多了成熟多了!
mathematica 发表于 2019-2-21 08:57
prime95是不是有源代码?加减乘除有现成的源代码,为什么要自己写呢?这个软件肯定比你快多了成熟多了!
看过一下，似乎是调用了GMP库。
有些奇怪， 自身上还包含了OOURA 分裂基FFT ， 而且FFT似乎有很多个实现，
中间有一堆的ASM 文件还带SSE指令集， 看起来对我来说直接就是一个折磨。
小小嘚瑟 !
终于在笔记本上追上了HugeCalc8 (无注册) 的速度了.
[ ( (10^9) ^ 3670016 - 1 ) / 11]* [ ( (10^9) ^ 3670016 - 1 ) / 11] (不能再大了. 数据量翻倍HugeCalc8 会挂掉)
硬件条件:
戴尔 vostro 340011代I5 1135 @ 3.8G 16G 内存, SSD 固态 轻负载情况下.
在1.1-1.4秒左右.
HugeCalc8基本在1.2秒附近.
基本认为速度已经相差无几了.满足了
PS:
联想R9000P3060TI
下运行实际不会超过0.7秒.
在双显卡台式机,配置更好的.
一般在0.5x , 不会超过0.6秒.
@knate :b:
同样的计算，我也在我的电脑上（i7-7700HQ @ 2.8GHz，睿频3.6 GHz）试了一下我的库（四年没更新了）和MMA（均为单线程；内部都使用二进制，所以输出结果需要进制转换，会比较慢），结果如下：
显然MMA是自动用平方计算乘法的，c = a*b 和 d = a^2 耗时一样，比我用平方稍微慢点。而它的进制转换输出比我慢将近40%;P 。
附件是测试用程序和MMA文件，你可以在你的电脑上试试结果。
（我注意到你提到了显卡，你的算法需要用到显卡吗？或者CPU多线程？）
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%左右. 影响不大.