二进制32位整数快速平方根
本帖涉及到众多技术点，符合加精标准。假设输入整数n，是32位二进制无符号整数求二进制无符号整数$r, r * r <= n < (r + 1)^2$
$r$称为$n$的平方根
汇编和c均可，要求速度 我已经实现了一个算法较优的C 语言版本，等汇编算法完成后，将代码贴出来.
这个算法的特点是,对于不同大小的被开方数采用不同的算法。主要技术点有
1. 使用查表和牛顿迭代法相结合，需要一个256BYTE的表格。
2. 需要使用bsr指令和跳转表
3. 不同范围的数使用不同的算法
3.1 当被开方数<64, 直接查表。
3.2 当被开方数<64K, 需要查表，移位，1次调整运算结果(需要乘法，比较指令）。
3.3 当被开方数<256M, 需要查表，移位，1次牛顿迭代，1次调整运算结果(需要乘法和比较指令)
3.4 当被开方数>=256M, 需要查表，移位，2次牛顿迭代，1次调整运算结果(需要乘法和比较指令) 也就是说r= ?
那样的话直接查表就行了
n是32位的话,表只要65536个项... 提高计算速度和减小表的大小是一对矛盾。我的算法仅需要一个256BYTE的表格，但又不知使得速度太慢。
回复 3# 仙剑魔 的帖子
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
一次查表，一次牛顿迭代就能得到结果
不过，太大的也要二次迭代 你是如何得到上述结论的，你能用具体的方法证明吗？ 手算的
可能会用程序验证