二进制32位整数快速平方根

无心人 · 发表于 2009-2-9 11:04:29

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

您需要登录才可以下载或查看，没有账号？欢迎注册

×

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

汇编和c均可，要求速度

liangbch · 发表于 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个项...

liangbch · 发表于 2009-2-10 10:50:53

提高计算速度和减小表的大小是一对矛盾。我的算法仅需要一个256BYTE的表格，但又不知使得速度太慢。

liangbch · 发表于 2009-2-10 10:55:57

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
一次查表，一次牛顿迭代就能得到结果

不过，太大的也要二次迭代

liangbch · 发表于 2009-2-10 20:53:23

你是如何得到上述结论的，你能用具体的方法证明吗？

无心人 · 发表于 2009-2-10 21:12:06

手算的

可能会用程序验证

账号		自动登录	找回密码
密码			欢迎注册

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

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

回复 3# 仙剑魔的帖子

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

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

回复 3# 仙剑魔 的帖子

回复 3# 仙剑魔的帖子