二进制大整数乘法

Ickiverar

我用C++和x64汇编实现了二进制大整数乘法，包括 硬乘法，Karatsuba 和 SSA (Schönhage–Strassen algorithm)
没有使用任何SSE指令或者任何MMX,XMM寄存器。
测试两个 三百五十万字（约定1字=64bit=19.266十进制位）整数相乘，比HugeCalc慢约十二分之一。
intel i5 @2.6GHz，单线程 。
我的乘法：5.9s
HugeCalc：5.5s
想问SSA有什么加速技巧么？还是说我需要实现Toom-Cook 3对递归底层加速处理？

gxqcn

蛮不错啊。

HugeCalc 已暂停开发好几年了，注意，只是暂停而已。
一来工作忙，二来一直在等待比较好的CPU后再继续。
就大整数计算而言，带宽越大越好，所以64位（甚至128、256位）比32位更好，
楼主已走在前面了，因为我还没写过64位下的汇编。

knate

能否举个例子解释下你们的SSA是如何运作的?!

比方说 基为 2^32的
A[256] 和 B[256]两个数组乘积.
这时选取的 512阶根和模值分别是多少的呢?!

Ickiverar

@knate
SSA从来不需要选择什么模值和根。
我给你个论文吧，我就是从什么都不知道开始看这个论文最后实现了SSA的。
SSA.pdf (288.63 KB, 下载次数: 52)

2015-10-18 14:50 上传

点击文件名下载附件

主要来说，SSA就是超长字长但相对的变换长度就会短一些的FFT。模一定是2^N±1（基本算法），单位根一定是2的幂（不考虑√2trick）。N可能很大，几十万那么大。

Ickiverar

Ickiverar 发表于 2015-10-18 14:52
@knate
SSA从来不需要选择什么模值和根。
我给你个论文吧，我就是从什么都不知道开始看这个论文最后实现 ...

http://www.loria.fr/~gaudry/publis/issac07.pdf
论文的出处网址在这里。和附件是同一个内容。

knate

Ickiverar 发表于 2015-10-18 15:04
http://www.loria.fr/~gaudry/publis/issac07.pdf
论文的出处网址在这里。和附件是同一个内容。

这PDF看了.就是没弄明白.
特别是和FFT搅和在一起的时候就乱套了.

P168
1.1例子
里的 1000448 分解为2^10 ,需要 1964位长度,这里是看明白了.
后面部分就看不懂了.

Ickiverar

knate 发表于 2015-10-21 11:46
这PDF看了.就是没弄明白.
特别是和FFT搅和在一起的时候就乱套了.

那说明你之前的内容没看懂。
选择K值是实现的细节，后面的都是实现的方法，如果看懂算法了就应该知道他在说什么。
算法的理论部分在第一页(167页)的右下角到第二页(168页)的前四分之三。仔细看这些吧。

mathe

64比特乘法在intel64位处理器上直接用乘法指令已经非常快了。但是对于位数更多的整数乘法，需要选择使用各种高级乘法，这方面gxqcn应该非常有经验

knate

Ickiverar 发表于 2015-10-23 18:37
那说明你之前的内容没看懂。
选择K值是实现的细节，后面的都是实现的方法，如果看懂算法了就应该知道他 ...

终于今天完成了基本的SSA.
原来一直以为变换长度是几百W长度的.
所以想不通.

liangbch

我也一直想实现SSA算法，如果搞懂了这个，则所有关于大数乘法的算法都攻克了。自己也可以实现一个高速的大数运算库了。

问一下楼主，SSA算法对基于10^k进制的大数是否适用。