查找平方根算法的名称是什么？ [英] What's the name of this finding square root algorithm?

问题描述

算法如下：

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

我完全理解它是如何工作的，但是我不知道这种方法叫什么。我一直在看维基百科，了解平方根的计算方法，但无济于事。这是逐位方法吗？

I completely understand how it works, but I don't know what this method is called. I've been looking at the wiki for computing methods of square root but to no avail. Is this the digit-by-digit method?

（相关：如何在不使用div的情况下在x86-64中计算数字的整数平方根？）

推荐答案

正如彼得·科德斯（Peter Cordes）在评论中提到的，这是数位算法（此处为二进制数字）。

As Peter Cordes mentioned in comments, this is digit-by-digit algorithm (here binary digits).

It是一种二进制搜索。如果平方的结果变得更接近 x 但不超过它，则可以设置第i个位，因此将所需的两个近似幂相乘会得到更好的结果。

It is kind of binary search. You set i-th bit if squared result becomes closer to x but does not exceed it, so adding needed powers of two approximates result better and better.

这篇关于查找平方根算法的名称是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！