二分法

探索アルゴリズムにおける二分探索と同じように、$\epsilon$ を徐々に小さくしていくことで、真値の探索範囲を効率的に絞り込んでいくことができます。

$x_0$と$x_1 = x_0 + \epsilon$について、$\epsilon \geq \left| \sqrt{n} - x_0 \right|$ かつ $\epsilon < \left| \sqrt{n} - (x_0 - \epsilon) \right|$であるとします。 このとき、$\epsilon \geq \left| \sqrt{n} - x_1 \right|$ であり、 $x_0 \leq \sqrt{n} \leq x_1$ となります。

ここで$x_0$と$x_1$の中間地点$x = \frac{x_0 + x_1}{2}$について考えます。 $x$について、$x_0 \leq \sqrt{n} \leq x$と$x \leq \sqrt{n} \leq x_1$のどちらかが成り立ちます。 前者のときに$x_1 \leftarrow x$、後者のときに$x_0 \leftarrow x$とすることで、許容誤差を$\frac{\epsilon}{2}$としたときの探索条件に当てはまります。

すなわち、$\epsilon \leftarrow \frac{\epsilon}{2}$、$x_0 \leftarrow x$（$x^2 < n$のとき）、$x_1 \leftarrow x$（$x^2 > n$のとき）と更新すれば探索範囲の条件を保ったまま$\epsilon$を半分に小さくできます。 $x_1 - x_0$が許容可能な誤差を下回るまでこの手順を繰り返すことで$\sqrt{n}$の値を得ることができます。 この方法を二分法と呼びます。

平方根の算出法に開平法と呼ばれる方法があります。 開平法では、$x^2$が$n$を越えないように 10 進数の一桁ずつ値を決めていきます。 2 進数において、ある値を半分にすることは小数点を一桁スライドさせることです。 二分法は 2 進法版の開平法であると言えるでしょう。