この平方根アルゴリズムの名前は何ですか？次のように

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

ピーター・コルドはコメントで述べたように、これはdigit-by-digit algorithm（ここでは二進数）です。

これはバイナリ検索の一種です。二乗結果がxに近づいてもそれを超えていない場合はi番目のビットを設定しますので、2つの近似値を必要に応じて加算すると、より良い結果が得られます。