二进制大整数乘法

liangbch

mathe 发表于 2015-10-24 09:55
64比特乘法在intel64位处理器上直接用乘法指令已经非常快了。但是对于位数更多的整数乘法，需要选择使用各 ...

确实是这样，在64位模式，直接使用64位乘i法指令是最快的，SSE2,SSE4,AVX这些指令起不到加速作用。

knate

我就是二进制实现后,改进为基于10^9下的也可以处理

但不知还算SSA还是其他的了

liangbch

knate 发表于 2015-11-2 13:51
我就是二进制实现后,改进为基于10^9下的也可以处理

但不知还算SSA还是其他的了

好消息，不知理论上能否站得脚，可否证明。

liangbch

刚看到一篇题为《Big Integer Multiplication with CUDA FFT(cuFFT) Library》的文章，
该文的测试表明，在只有96stream单元的GT630显卡，当数的长度超过5万位时，使用
CUFA FFT的大数乘法的速度超过GMP。
原文见：http://www.ijircce.com/upload/2014/november/3_big.pdf

注：该文发表于2014年11月，文中没有提到GMP的版本。

knate

只是用几十W长度左右的随机数据和比较特殊的几类数
和FNT+CRT结果对比！
得到的结论！

有个论文链接，明天上来发出来！

http://arxiv.org/pdf/1502.02800v1.pdf

liangbch

加入两个本站资源链接，便于查找相关资料
数论变换原理简述
数论变换论文集

Ickiverar

liangbch 发表于 2015-10-30 12:14
我也一直想实现SSA算法，如果搞懂了这个，则所有关于大数乘法的算法都攻克了。自己也可以实现一个高速的大 ...

不适用。
SSA的精妙之处在于模(2^N±1)的计算可以由二进制移位来计算。
如果是2^32或2^64进制，直接在内存中进行非常长的移位即可。如果是10^k进制，移位之后什么都不是。

liangbch

从另一种角度上，SSA算法实际上与进制无关，SSA算法的实质是，
  1. 将参于计算的被乘数和乘数切割成2^k片段，我们称之为A0和B0
  2. 然后对被乘数和乘数分别做类似于FFT的数论变换，得到A1，B1。这里数论变换的模为费马数，2^k次单位根为2的方幂。
  3. 对两个变换后的序列A1和B1做点积运算，得到C0
  4. 对C0做一次反变换得到C1
  5. 对C1做进位处理，得到最终乘积。

对于基于10进制表示的大数乘法，和基于二进制表示的大数稍有不同，
  1. 将将大数切割成2^k个片段后，需要转化为2进制表示，接下来的步骤2,3,4均为二进制运算。
  2. 在步骤5，需要将2进制表示的大数转化为10进制，并做进位处理。


和apfloat相比，SSA算法与apfloat的都采用数论变换算法。
不同点：
    1. apfloat使用的模很小，并且模m是一个质数，不超过一个机器字，需要使用不同的m,得到多个C1.最后使用中国剩余定理，得到最终结果。
      计算(x % m)没有快速算法，一般使用以乘代除法，需要使用2次乘法，并调整商; SSA使用的模m是费马数，在实践中，使用的费马数都是合数，
      它比apfloat使用的模m大得多,在计算(x % m)时有快速算法。
    2. apfloat中2^k次单位根w一般不是2的方幂，故在变换过需要使用乘法;而SSA算法中的w一般为2，4,sqrt(2), 故在变换过程不需要使用乘法。

Ickiverar

无论如何。
我这里有个好消息，经过一个多月的完善，我的算法库从开始的只有整数乘法，到现在已经实现了浮点数加减乘除平方根了。效率还算不错，单线程比MMA8慢2到4倍。
我现在随时可以使用Chudovsky的算法计算圆周率的二进制表达。
等我写完进制转换和输入输出算法，就能算至少两亿位圆周率了。

Ickiverar

计算三百五十万字精度的 根2 二进制浮点数值（相当于6743万位十进制精度），用时 9.51 秒，使用内存 182 MB，结果经Mathematica检验正确。
Mathematica 8 用时 5.094 秒。
虽然我的程序会慢一些，但我觉得这个比例还可以接受。