这个发现平方根算法的名称是什么？

问题描述：

res <- 0 
for i from 15 downto 0 do: 
    change the ith bit of result to 1 
    if res^2 > x then: 
     change the ith bit of res back to 0 
return res

我完全理解它是如何工作的，但我不知道这是什么方法被调用。我一直在寻找wiki的平方根计算方法，但无济于事。这是数字的方法吗？

在其他领域（尤其是模数转换）中，该过程称为“逐次逼近”。尽管如此，牛顿的方法也被称为“逐次逼近”。你可以把这种方法称为“二进制逐次逼近”来区分它。它不用于平方根，因为牛顿的方法收敛速度更快。 –

这个很清楚，*称之为[按位数算法]（https://en.wikipedia.org/wiki/Integer_square_root#Digit-by-digit_algorithm），使用位运算来实现基-2。顺便说一下，在现代x86硬件上，最快的整数sqrt是使用FP双精度硬件。在Haswell中，转换为/来自'double'的每个方法都是4个周期的延迟，再加上'sqrtsd'的16个周期延迟。（而且它只有3个指令/ 5个微指令，所以如果还有别的事情需要，无序执行可以很容易地隐藏这个等待时间。） –

它看起来像是一个时代的古老遗迹，CPU甚至没有乘法指令。可以很容易地避免使用res^2（通过使用res和res 2的两个不同值，用0x8000和0x40000000初始化：一个res - 右移1位，另一个res - 每个循环2位），之后这可以很容易地实现在6502和类似的CPU – Tommylee2k

答

正如彼得·柯德斯在评论中提到的，这是digit-by-digit algorithm（这里二进制位）。

这是一种二分查找。如果平方结果接近于x但不超过它，则设置第i位，因此添加两个近似值所需的功率结果会越来越好。

我不确定这实际上是否回答了这个问题，虽然..“...种类的二进制搜索”不是一个真正的名字。 –

@David：但是“逐位数算法”确实会回答它，IMO。 –

我同意。这不是原来的答案。 –

这个发现平方根算法的名称是什么？

相关推荐