找回密码
 欢迎注册
楼主: litaoye

[求助] 关于一个运算优化的问题

[复制链接]
 楼主| 发表于 2009-3-13 16:43:10 | 显示全部楼层
原帖由 无心人 于 2009-3-13 16:37 发表
楼主的这个结论是错误的:
如果最高位m高于10^n,且低于10^n+1,那么这个数同最高位小于m的数进行Xor并取log10后的结果,都是n,


10^20 - 2^20的最高位同10^20是相等的,并不高于10^20,我说的是高于,不包括等于,等于的情况必须要逐个计算
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-13 16:43:25 | 显示全部楼层
我还能构造出
B << A
log(A XOR B) < log(A)的例子来

呵呵
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-13 16:45:07 | 显示全部楼层
To 81#

   等于的情况占38 / 128
   也太多了点
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-3-13 16:47:41 | 显示全部楼层
现在是0.34秒跑到Test#10出错了,对于c#,0.34应该还可以,一个A+B都需要0.125呢,呵呵!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-13 16:48:17 | 显示全部楼层
To 81#
我修改了那个回复

虽然你的说法没错误
也不妥当,容易引起误解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-3-13 16:50:09 | 显示全部楼层
原帖由 无心人 于 2009-3-13 16:45 发表
To 81#

   等于的情况占38 / 128
   也太多了点


是呀,等于的情况确实不少,因此这种优化能够减少的计算量有限,且不可预测,所以未必是一种好的方法!

不过如果数据差异较大,效果还是过的去。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-3-13 16:51:10 | 显示全部楼层

回复 85# 无心人 的帖子

呵呵,能帮我改一下最好了!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-13 16:58:27 | 显示全部楼层
如果两整数分别为 a, b(a≥b),其 bit 数相差不小于 d,
则取较大者数 a 的前 d 位(bit数),
然后左移 r 位使之与 a 位数相等,记该数为 x。

显然 $b < 2^r <= x <= a$,
则两数XOR后:$x <= a\quad"XOR"\quadb <= x + 2^r - 1$
所以,若 $10^k <= x <= 10^(k+1)-2^r$
则可保证两数XOR后的LOG10结果为 k.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-13 17:05:17 | 显示全部楼层


都是为了避免对数运算吧
看宝宝的对数汇编出来后

对数运算占多少的比重就知道了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-13 17:51:53 | 显示全部楼层
今天是没有时间搞了,到星期天,看看能不能完成。
To 楼主,使用C# 确实吃亏,C#应该没有C++ 和汇编混合编程来的快些。楼主可考虑用C++编程。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 21:07 , Processed in 0.042764 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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