数学研发论坛

 找回密码
 欢迎注册
查看: 27695|回复: 142

[讨论] 二进制32位整数快速平方根

[复制链接]
发表于 2009-2-9 11:04:29 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
精华
假设输入整数$n$,是32位二进制无符号整数
求二进制无符号整数$r, r * r <= n < (r + 1)^2$
$r$称为$n$的平方根

汇编和c均可,要求速度
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-10 10:33:19 | 显示全部楼层
我已经实现了一个算法较优的C 语言版本,等汇编算法完成后,将代码贴出来.
这个算法的特点是,对于不同大小的被开方数采用不同的算法。主要技术点有
  1. 使用查表和牛顿迭代法相结合,需要一个256BYTE的表格。
  2. 需要使用bsr指令和跳转表
  3. 不同范围的数使用不同的算法
   3.1 当被开方数<64, 直接查表。
   3.2 当被开方数<64K, 需要查表,移位,1次调整运算结果(需要乘法,比较指令)。
   3.3 当被开方数<256M, 需要查表,移位,1次牛顿迭代,1次调整运算结果(需要乘法和比较指令)
     3.4 当被开方数>=256M, 需要查表,移位,2次牛顿迭代,1次调整运算结果(需要乘法和比较指令)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-10 10:45:58 | 显示全部楼层
也就是说r=[sqrt(n)] ?
那样的话直接查表就行了
n是32位的话,表只要65536个项...
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-10 10:50:53 | 显示全部楼层
提高计算速度和减小表的大小是一对矛盾。我的算法仅需要一个256BYTE的表格,但又不知使得速度太慢。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-10 10:55:57 | 显示全部楼层

回复 3# 仙剑魔 的帖子

n是32位的话,表只要65536个项。

这样的话,查表就可能麻烦些,可能需要使用2分查找。
我的这个算法中的查表是直接定位的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-10 14:25:11 | 显示全部楼层
如果使用二分法

不见得比用浮点汇编指令要快
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-10 14:32:27 | 显示全部楼层


看来BSR是无法避免的
是否有比BSR更好的指令定位初始值?
=============================
另外
假设输入$n, a * a <= n$
$b = n - a * a$
$x = b / {3a} = n / {3a} - a / 3$
是否是一个比$a$更好的结果?
============================
上面想法不行
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-10 20:32:11 | 显示全部楼层
假设构造255以内的表
==============================
64 * 2^24 + 2^24 - 1
一次查表,一次牛顿迭代就能得到结果

225 * 2^24 + 2^24 - 1
一次查表,一次牛顿迭代就能得到结果

不过,太大的也要二次迭代
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-10 20:53:23 | 显示全部楼层
你是如何得到上述结论的,你能用具体的方法证明吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-10 21:12:06 | 显示全部楼层
手算的

可能会用程序验证
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-1-16 11:21 , Processed in 0.054422 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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