来点复杂的吧

无心人

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

gxqcn

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

mathe

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

mathe

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

无心人

还是要改代码 呵呵 我倾向于扩展的Euclid算法

无心人

谁推荐个重构工具 独立运行，免费的 比较强的替换工具也可以 支持函数替换

无心人

游客，本帖隐藏的内容需要积分高于 100 才可浏览，您当前积分为 0

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

gxqcn

你的“乘法”return 语句前半截右移1位错了（应右移31位）。 也可改为下面的：

1. DWORD modMul31(DWORD l, DWORD r)
2. {
3. long long t = (long long)l * (long long) r;
4. return modAdd31((DWORD)((t) >> 31), ((DWORD)(t)) & 0x7FFFFFFF);
5. }

复制代码

这样乘法就没问题了，即便有问题也是在“加法”上。

无心人

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

无心人

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