论坛 › 随笔涂鸦 › 来点复杂的吧

无心人 发表于 2009-2-22 09:11:00

:)

谁能利用P = 2^31 - 1的特殊性质， 设计一个高效的除法？？

gxqcn 发表于 2009-2-22 10:15:31

在 P=2^31-1 域上的除法可用乘法代替：
a/b -= a*b^(p-2)\quad(mod p)
只是这里的“除法”是不存在“商/余数”概念的。

mathe 发表于 2009-2-22 11:12:54

计算b^(p-2)复杂度可能有点高
可以直接计算b关于p的数论倒数,这个可以使用辗转相除法来计算

mathe 发表于 2009-2-22 12:08:34

两种算法时间复杂度没有本质区别,都是log(p)次乘除运算.
不过果树问题里面用到除法通常都是一个循环里面出现,所有除数都相同,所以更好的优化是先计算逆,然后循环里全部改成乘法.

无心人 发表于 2009-2-22 12:48:55

:)

还是要改代码
呵呵

我倾向于扩展的Euclid算法

无心人 发表于 2009-2-22 14:46:40

谁推荐个重构工具
独立运行，免费的

比较强的替换工具也可以
支持函数替换

无心人 发表于 2009-2-22 18:53:49

**** Hidden Message *****
放点资料
明天用
不许看， 谁看谁帮助改
乘法存在问题

gxqcn 发表于 2009-2-23 07:34:24

你的“乘法”return 语句前半截右移1位错了（应右移31位）。

也可改为下面的：DWORD modMul31(DWORD l, DWORD r)
{
    long long t = (long long)l * (long long) r;
    return modAdd31((DWORD)((t) >> 31), ((DWORD)(t)) & 0x7FFFFFFF);
}这样乘法就没问题了，即便有问题也是在“加法”上。:lol

无心人 发表于 2009-2-23 08:15:30

关键是无法控制其编译器行为啊
要么丢精度
要么生成很复杂汇编
比如不加优化选项
加减自动生成的汇编比我预期的多三倍
优化后5条，优化前10多条
无用的很多

难道只有汇编才可以

无心人 发表于 2009-2-23 08:17:07

我倾向于乘法就不要调用加减了
光一个函数调用的开销就够算一次加法了

查看完整版本: 来点复杂的吧