algorithm - 这个求平方根算法的名称是什么？

Question

算法如下:

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 上寻找平方根的计算方法，但无济于事。这是逐个数字的方法吗？

(相关:How to compute the integer square root of a number in x86-64, without using div?)

Answer 1

正如 Peter Cordes 在评论中提到的，这是 digit-by-digit algorithm (此处为二进制数字)。

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