What's the name of this finding square root algorithm?

user_7744673 0
Viewed 728

The algorithm is as follows:

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?

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

x86-64 assembly algorithm
1 Answers

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

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.

user_8444160
Related