二进制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

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

无心人

手算的 可能会用程序验证