来点复杂的吧

无心人

  谁能利用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多条
无用的很多

难道只有汇编才可以

无心人

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