纯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 的帖子