x86上128位二进制乘法最快速算法征解

liangbch

你不知道我的具体做法，怎么能说我这个方案行不通呢？
  第一个问题的答案： 我的算法和那个128bit×128bit的代码完全不同。采用我的算法：解包的操作非常少，平均每32次 30bit × 30bit的乘法才需要1次解包，解包可忽略不计。
  至于加法，也是不需要ADC指令的， 而采用更为灵巧的add,and,shr,shl等指令。

  最后，最重要的，我的这个方案基本上已经实现，而非构想，大量的实际问题已经获得解决。你就不要担心了。这个方案的一个类似的实现主要是2006-2007年进行的。对大整数运算的优化（包括使用汇编，SSE2指令），我是做的多，说的少，也很少公布其细节。在2008年，我的相当一部分精力投入到这个论坛，因此关于大整数乘法的工作基本上限于停顿。

gxqcn

个人比较赞同 liangbch 的观点。

因为为了解决进位问题，无论是ALU还是SIMD系列指令，代价都很大。

CHugeIntX 内部每个单元仅存28bits（也可存到30bits，但输出略微麻烦），在计算乘法时累加时甚至不必考虑所谓的“高96bis进位问题”，因为只有参与乘法的两数长度均超过256个单元时才存在该类似问题，而此时更快的算法Karatsuba早已粉墨登场了。

无心人

思考了一个中午，我认为你们的说法是错误的
第一， 每个乘法的两次加法能得到减少么？
第二， 无论如何，普通乘法的程序也不会因为缩小进制而
      得到简化

无心人

这个共识我们应该能达成吧
====================
进制的二进制位不得大于CPU的位数

gxqcn

原帖由 无心人 于 2008-4-1 13:41 发表
思考了一个中午，我认为你们的说法是错误的
第一， 每个乘法的两次加法能得到减少么？
第二， 无论如何，普通乘法的程序也不会因为缩小进制而
      得到简化

但因为有冗余bit，可以减少进位的次数，这是相当划算的。

至于上楼的结论那是当然的。（任何数据结构至微部分位数都不可能大于系统的位数，何不顺应之？）

无心人

减少进位次数只对ALU指令有效
SSE2指令乘法是不考虑进位的
====================
能写个示例代码么？
和我贴的通用乘法类似的
我要比较下

gxqcn

进位并不是指相乘产生的，
而是指对积累加过程中产生的。

所以大数计算往往特意留一丁点冗余bit，就是方便这个处理，
当然，我也反复说过，也与照顾大数乘法高级算法相关。

无心人

高级算法
可以多层运算啊
比如
第一层FFT算法
调用底层的240位乘法
再底层调用汇编乘法

无心人

怎么说这个事情呢
======================
高级算法在我的理解就是乘和除了
其他的应该算更高级的了
乘存在很大的分段运算可能，
在FFT里和高级的Toom-n算法里， 每段都要扩充很大的空余空间
但这个无论是否压缩bit表示的位数都是不可避免的
压缩基的位数将大大增加表示的空间
也仅在加法里有效果
可是你们想到没？
一个加法的进位就1个bit
一个64bit SIMD寄存器就能容纳多少进位啊？
还用在32位里压缩bit容纳么？
GxQ的表示是28位，正好是容纳256个乘加而不进位
但256个乘加在大FFT里是根本不够的
除非用多重FFT算法，但多重算法也无法避免bit冗余外的额外分配空间吧
===================================
我想你小bit比GMP慢的原因就是这个原因造成的吧
===================================
还一个要说的事情是， apfloat基的选择我想更多的是因为是C语言，无法处理低级运算造成的
===================================

无心人

要不就选一个位数咱测试下效果
28 * 32* 30位如何？
你的，liangbch的，我的选择都正好能划分开
从划分开的数字输入
但输出必须也划分开，你的必须输出28Bit一个字的数据
重复运算10000次（暂定），测量时间
从划分开的数字输入，到划分开的数字输出