Can you name this square root algorithm on an unsigned integer through the manipulation of the binary number?

Question

Apparently this algorithm is well known.

The algorithm will build the square root answer bit by bit starting from the left-most bit to the last.

Let's say we will support squaring up to a 8 bit unsigned integer for simplicity.

let res be result

let x be 8 bit unsigned integer

let n be the nth bit in the result where the 0th bit is the last bit.

set res to 0
for nth bit from 3 down to 0
    change the nth bit of the res to 1
    if res * res > x then: <- The Comparison
         restore the nth bit back to 0
return res

The return result will be a 4 bit unsigned integer

For Example: Finding the square root of 4

(see image)

Is this perhaps the Digit by Digit Calculation: Binary Numeral System (base 2)? Wiki Link here

Thank you for your time!

Answer 1

i might call it successive approximation or maybe binary search to invert a monotonic function.

if you are able to perform a function f(x), and if you know that f(x) is strictly monotonic (strictly increasing or strictly decreasing) in the domain of x that is salient, then you can always invert f(x) to whatever finite degree of precision you want with this binary search. one iteration for every bit you need in your result.

Answer 2

Yes, that's essentially the same algorithm described at the article that you linked.

The main difference is your pseudo-code's use of multiplication, which costs more than what can be done, as the same article points out, "... the operations needed to compute ... e * e can be replaced with faster bit shift operations."

'HTH,

Answer 3

Put simply, if it is given that X == Y^2 (a reformulation of sqrt(X) == Y), and you would like to solve (N*N*X + m) == (N*Y + k)^2 for k where the value of N is fixed for the entire algorithm, you can simply substitute values into k from k = 0, 1, ..., N-1 and compare the magnitude between the left hand side (which is fixed) and the right hand side (which depend on the value substituted into k).

For N = 2, the possible value of k is simply 0, 1 so that it reduces to a binary search.