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次（暂定），测量时间 从划分开的数字输入，到划分开的数字输出