[讨论] 二进制32位整数快速平方根 相关搜索: 二进制, 平方根, 整数

无心人

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

汇编和c均可，要求速度

liangbch

我已经实现了一个算法较优的C 语言版本，等汇编算法完成后，将代码贴出来.
这个算法的特点是,对于不同大小的被开方数采用不同的算法。主要技术点有
  1. 使用查表和牛顿迭代法相结合，需要一个256BYTE的表格。
  2. 需要使用bsr指令和跳转表
  3. 不同范围的数使用不同的算法
   3.1 当被开方数<64, 直接查表。
   3.2 当被开方数<64K, 需要查表，移位，1次调整运算结果(需要乘法，比较指令）。
   3.3 当被开方数<256M, 需要查表，移位，1次牛顿迭代，1次调整运算结果(需要乘法和比较指令)
     3.4 当被开方数>=256M, 需要查表，移位，2次牛顿迭代，1次调整运算结果(需要乘法和比较指令)

仙剑魔

也就是说r=[sqrt(n)] ?
那样的话直接查表就行了
n是32位的话,表只要65536个项...

liangbch

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

liangbch

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

这样的话，查表就可能麻烦些，可能需要使用2分查找。
我的这个算法中的查表是直接定位的。

无心人

如果使用二分法

不见得比用浮点汇编指令要快

无心人

看来BSR是无法避免的
是否有比BSR更好的指令定位初始值？
=============================
另外
假设输入$n, a * a <= n$
$b = n - a * a$
$x = b / {3a} = n / {3a} - a / 3$
是否是一个比$a$更好的结果？
============================
上面想法不行

无心人

假设构造255以内的表
==============================
64 * 2^24 + 2^24 - 1
一次查表，一次牛顿迭代就能得到结果

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

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

liangbch

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

无心人

手算的

可能会用程序验证