纯C下的长乘法最佳算法讨论

无心人 · 发表于 2008-9-29 11:07:54

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

假设纯C语言编程，硬件CPU支持32位整数，如何写长乘法速度最快？
使用 int64还是自己写代码？
请大家讨论
GxQ最近写的程序应该最清楚吧
呵呵

以两个32个双字的整数相乘做例子说明
不使用任何乘法加速算法
仅考虑硬乘法算法，即模拟手算的算法

无心人 · 发表于 2008-9-29 11:14:12

我能想到的是
模拟一个通过4个16X16 位的乘法计算32X32位乘法的过程

当然也可以考虑3次乘法的那个算法

gxqcn · 发表于 2008-9-29 13:04:25

我为了减少内存读写操作，尤其是写操作的次数，
每个段并未用足32bit，而是与HugeCalc内部的一致——仅28bits，
这样最大的好处是：可以完全模拟小学生的计算，
把结果每个位上的乘积全部累加到一个64bit的变量中后再规格化。
（是否最优，因时间紧迫缘故，尚未与其它算法进行比较）

gxqcn · 发表于 2008-9-29 13:34:53

原帖由 无心人 于 2008-9-29 11:14 发表
我能想到的是
模拟一个通过4个16X16 位的乘法计算32X32位乘法的过程

当然也可以考虑3次乘法的那个算法

我移植的那款DSP型号是BalckFin531，内部居然是16位的，
它的32位乘就是通过4次乘法实现的（是它编译器自动生成的），
我也怀疑是否可用Karatsuba算法减少一次乘法来加速。

无心人 · 发表于 2008-9-29 14:35:52

不过
我中午想了
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乘法快多少

gxqcn · 发表于 2008-9-29 14:49:36

机器内部指令对有无符号差别不大，
其中加减法指令是不分有无符号的，
乘法有无符号差别不大，
除法指令才对此要敏感点吧。

无心人 · 发表于 2008-9-29 15:34:46

我的意思
3个乘法的需要计算2次加法
如果不区分符号
怎么知道是否产生进位了？

fallening · 发表于 2008-10-2 22:00:38

这方面不是流行用FFT做卷积么？

无心人 · 发表于 2008-10-3 10:38:31

16个双字下，用FFT不合适吧

liangbch · 发表于 2008-10-5 11:43:00

应该不能提速，只有当n达到一定程度，通过使用3次 n *n 乘法来计算2n * 2n 的乘法才能加速，这个n 应该不会太小，我记得GMP中，对于乘法这个n大于17，对于平方这个n也需要大于11.

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 纯C下的长乘法最佳算法讨论

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

回复 4# gxqcn 的帖子