二进制大整数乘法

Ickiverar

输出算法写完了。
接楼上，虽然我10秒不到就算出了根2的值，但我要用120秒来输出它。

liangbch

如果采用10^k进制，输出时间就快了。

在http://bbs.emath.ac.cn/thread-143-1-10.html中，我写了个计算sqrt(2)程序，下面是性能数据。

调用站长的Hugecalc,计算sqrt(2)的性能数据
｜10进制位数｜计算时间｜输出到文件时间｜
｜100000｜0.064｜0.135｜
｜1000000｜0.552｜0.166｜
｜10000000｜8.026｜1.852｜

测试环境：Windows XP SP2，Intel Pentium 4 CPU 2.93GHz，512MB DDR - 133MHz

liangbch

楼主可以和Pifast比较一下。
在我的Core2 Duo CPU E8500 3.16GHZ CPU, 计算6800万位sqrt(2),pifast4.3总时间为18.42秒。

Ickiverar

PiFast是使用的10^k进制进行内部计算的，输出基本不用时间。
算得比我用二进制还要快。
果然是非常优化了的。
计算根2，67108864 位用时五秒多，
计算圆周率1000万位用十六秒多。我要用40秒，其中11秒多用来输出。

liangbch

　我一直在想，对于通常规模的大数乘法，其于小质数模（在32位系统模小于2^32,在64位系统模小于2^64））的快速数论变换+中国剩余定理的算法，应该比使用大的费马数模变换(SSA算法)算法更快，因为在SSA算法中，第1级费马数变换完成，计算点积时依然有很高的复杂度。只有当数的规模非常大时，计算点积时，才有必要再次使用Fermat变换算法，否则，直接乘更快。

knate

通常来说
FNT的大致的复杂度为 9nlogn
SSA的复杂度大约为 nlogn logn

FNT内限制速度的主要是 a * b % p这个运算.
这个通常为 为一个普通乘法的 4--5倍以上,因此大致时间需要放大不少.
SSA 更多依赖的我认为是 大整数的长加减法和数据移动,一般来说,这两个 和 a * b % p 这个运算的优化比较,相对容易一些.

具体实现上,我实现的SSA 大致为FNT速度的2 / 3,这个优化还不是很到位的情况的下的结果.

如果说能找到SSA能只用加法而不用减法来处理的话,估计SSA要完胜 FNT,
而FNT则基本放弃寻找更好的 p来进行优化.

knate

knate 发表于 2015-12-18 17:53
通常来说
FNT的大致的复杂度为 9nlogn
SSA的复杂度大约为 nlogn logn

最终实现的SSA大致是FNT的 1/3到 1/2之间浮动,少于 1/2
速度已经不慢于 1楼的速度.
二进制比十进制更快.

无心人

新的MULX, ADDX指令是极大的有助于大整数乘法运算的
ADDX把对CF的依赖改为其他标志，于是可以一次并发执行多个加法流
MULX则摆脱了对RDX:RAX寄存器的结果依赖，可以更自由的使用寄存器，同样是增加了并发度

另外我觉得是时候放弃32位了

knate

WIN7 64
I5 @2.8GHZ
8G内存
GMT860M
的笔记本

两个大约 3000W位十进制数的相乘,
按前期的测试计算.
非常有望时间能压缩到1秒以内.
由于 以前FNT ,SSA所用的分裂基FFT并不适用.需要进行大改.
在查BUG.

补充内容 (2016-6-10 17:01):
跟之前预计的差不多。
在0.85秒左右。
可惜对资料不是熟悉，加速器内如何 快速计算32位整数的  a * b % p这个老大难问题。还不清楚有什么好的办法。
要不然可能还能提高速度。

Ickiverar

knate 发表于 2016-4-17 13:21
WIN7 64
I5 @2.8GHZ
8G内存

0.85秒，3000万位相乘……
我需要2.6秒以上……
求问你内部都用了什么算法……
我只实现了 笔算/karatsuba/SSA……