纯C下的长乘法最佳算法讨论
假设纯C语言编程，硬件CPU支持32位整数，如何写长乘法速度最快？使用 int64还是自己写代码？
请大家讨论
GxQ最近写的程序应该最清楚吧
呵呵
以两个32个双字的整数相乘做例子说明
不使用任何乘法加速算法
仅考虑硬乘法算法，即模拟手算的算法 我能想到的是
模拟一个通过4个16X16 位的乘法计算32X32位乘法的过程
当然也可以考虑3次乘法的那个算法 我为了减少内存读写操作，尤其是写操作的次数，
每个段并未用足32bit，而是与HugeCalc内部的一致——仅28bits，
这样最大的好处是：可以完全模拟小学生的计算，
把结果每个位上的乘积全部累加到一个64bit的变量中后再规格化。
（是否最优，因时间紧迫缘故，尚未与其它算法进行比较） 原帖由 无心人 于 2008-9-29 11:14 发表 http://bbs.emath.ac.cn/images/common/back.gif
我能想到的是
模拟一个通过4个16X16 位的乘法计算32X32位乘法的过程
当然也可以考虑3次乘法的那个算法
我移植的那款DSP型号是BalckFin531，内部居然是16位的，
它的32位乘就是通过4次乘法实现的（是它编译器自动生成的），
我也怀疑是否可用Karatsuba算法减少一次乘法来加速。 不过
我中午想了
Karatsuba乘法无论哪种写法
中间的那个乘法结果可能存在进位的
如何处理？
倾向于使用
$(X_1-X_0)(Y_0-Y_1) + X_1X_0 + Y_1Y_0$
这种写法
也许能简化进位的测试
但此写法要提前测试
$(X_1-X_0)(Y_0-Y_1)$
乘法的符号
呵呵
所以我倾向于
3乘法算法也许并不比4乘法快多少 机器内部指令对有无符号差别不大，
其中加减法指令是不分有无符号的，
乘法有无符号差别不大，
除法指令才对此要敏感点吧。 我的意思
3个乘法的需要计算2次加法
如果不区分符号
怎么知道是否产生进位了？ 这方面不是流行用FFT做卷积么？ 16个双字下，用FFT不合适吧
回复 4# gxqcn 的帖子
应该不能提速，只有当n达到一定程度，通过使用3次 n *n 乘法来计算2n * 2n 的乘法才能加速，这个n 应该不会太小，我记得GMP中，对于乘法这个n大于17，对于平方这个n也需要大于11.
页:
[1]
2