数学研发论坛

 找回密码
 欢迎注册
楼主: 无心人

[原创] 来点复杂的吧

[复制链接]
 楼主| 发表于 2009-2-22 09:11:00 | 显示全部楼层


  谁能利用P = 2^31 - 1的特殊性质, 设计一个高效的除法??
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-22 10:15:31 | 显示全部楼层
在 P=2^31-1 域上的除法可用乘法代替:
$a/b -= a*b^(p-2)\quad(mod p)$
只是这里的“除法”是不存在“商/余数”概念的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-22 11:12:54 | 显示全部楼层
计算b^(p-2)复杂度可能有点高
可以直接计算b关于p的数论倒数,这个可以使用辗转相除法来计算
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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 | 显示全部楼层
游客,本帖隐藏的内容需要积分高于 100 才可浏览,您当前积分为 0

放点资料
明天用
不许看, 谁看谁帮助改
乘法存在问题
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-23 07:34:24 | 显示全部楼层
你的“乘法”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. }
复制代码
这样乘法就没问题了,即便有问题也是在“加法”上。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-23 08:15:30 | 显示全部楼层
关键是无法控制其编译器行为啊
要么丢精度
要么生成很复杂汇编
比如不加优化选项
加减自动生成的汇编比我预期的多三倍
优化后5条,优化前10多条
无用的很多

难道只有汇编才可以
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-23 08:17:07 | 显示全部楼层
我倾向于乘法就不要调用加减了
光一个函数调用的开销就够算一次加法了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-10-24 09:09 , Processed in 0.057106 second(s), 15 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表