ある数の平方根の近似値を求める

見出しの通り、ある数の平方根の近似値を求めてみたいと思います。コードだけ載せて「こう書けました！」と言っても仕方ないので、なるべく問題を解く際の思考回路を忠実に書き起こします。後、ゴチャゴチャ数式も書いてますが、数学的な議論はあまり厳密にやってないので気楽に読んでください。

まずコーディングに入る前に少し考察して方針を立てます。

ある数をx(>0)とし、xの正の平方根 $ \sqrt{x} $ の近似値を求める方法を考えてみましょう。
素朴に考えるなら、とりあえず1,2,3,...を順番に $ \sqrt{x} $ と比べます。
ただし、$ \sqrt{x} $の値は分からないので、2乗した値どうしを比べます。1,4,9,...をxと比べていき、初めてx以上の値が見つかったとしましょう。今見つかった、2乗してx以上になる数をaとすれば、

(a-1)^2 < x \leqq a^2

a-1 < \sqrt{x} \leqq a

となるので、とりあえず誤差1以内の、xの平方根の近似値aが求められます。
とまぁ一応近似値は出せますが、、、
・計算量が多すぎる。
・誤差がデカすぎる。
このままではダメそうですね。

だったらどうするかということで、
当てずっぽうで0からxの間にある適当な数aを選び、$ a^2 $ とxを比較してみます。
$ a^2 > x $ なら $ a > \sqrt{x} $ であるため、$ \sqrt{x} $は0からaの間にあります。
$ a^2 < x $ なら $ a < \sqrt{x} $ であるため、$ \sqrt{x} $はaからxの間にあります。
このように適当に区間を[0,a]と[a,x]の2つに分けると、 $ \sqrt{x} $ がどちらの区間に含まれるかは分かります。
$ \sqrt{x} $ が含まれている方の区間をさらに2つに分けて、とやっていけば $ \sqrt{x} $ の値をどんどん正確に絞り込んでいけそうです。

さて、適当に区間を分けると言いましたが、実際どこで2つに分けるのが良いでしょうか？
$ \sqrt{x} $ が0からxの間のどの地点に存在する確率も同様に確からしいとします。なるべく効率よく $ \sqrt{x} $ が存在する区間を絞りたいです。適当にaを取ったとき、絞り込める区間の長さの期待値を考えましょう。

[0,a]に$ \sqrt{x} $ が含まれる場合、
もう[a,x]を調べる必要はないので、次に調べる区間を[0,a]に絞れます。(区間の長さ=a)
[0,a]に$ \sqrt{x} $ が含まれる確率は、 $ \sqrt{x} $ がどこに存在する確率も同様に確からしいため、$ \frac{a}{x} $ です。
同様に、
[a,x]に $ \sqrt{x} $ が含まれる場合、
次に調べる区間を[a,x]に絞れます。(区間の長さ=x−a)
[a,x]に $ \sqrt{x} $ が含まれる確率は、 $ \frac{x−a}{x} $ です。
よって、絞り込める区間の長さの期待値は

a \frac{a}{x} + (x−a) \frac{(x−a)}{x}\\
= \frac{2a^2 − 2ax + x^2}{x}\\
= \frac{2(a − \frac{x}{2})^2 + \frac{x^2}{2}}{x}\\

なるべく $ \sqrt{x} $ の範囲を絞り込みたい、つまり区間の長さを最小にしたい。上の式が最小になるのは $ a = \frac{x}{2} $ のとき。
よって区間をちょうど半分に分けていくのが効率が良さそうだということが分かります。
後はこれをコードに落とし込むだけです。
以下になります。

def bisectionSearch(x, epsilon):
    """
    二分探索を行う関数
    xは近似値を調べたい数
    epsilonは誤差の許容範囲
    """
    low = 0.0 # √xが存在する区間の左端。初期値は0.0
    high = x # √xが存在する区間の右端。初期値はx
    ans = (low + high)/2.0 # lowとhighの真ん中。
    """
    ans<√x(⇔ans^2<x)なら、√xはansとhighの間にあるので、次に調べる区間は[ans,high]に
    ans>√x(⇔ans^2>x)なら、√xはlowとansの間にあるので次に調べる区間は[low,ans]に
    """

    # 二乗の誤差がepsilonに収まるまで二分探索
    while abs(ans**2 - x) >= epsilon:
        if ans**2 < x:
            low = ans
        else:
            high = ans
        ans = (low + high)/2.0 # 次に調べる区間の真ん中の値を再代入

    return ans

こういう方法を二分探索と言います。
おそらく聞いたことがあるかと思います。
後、コードを書きながら気付いたんですが、$ \sqrt{x} $ の場所を[0,x]の範囲で調べてるんで、x<1、即ち $ x < \sqrt{x} $ の場合いつまで経っても√xに近づいてくれませんね...(意外と見落としがち??)
x<1のとき $ x< \sqrt{x} < 1 $ が成り立つので

if x < 1.0:
    low = x
    high = 1.0
else:
    low = 0.0
    high = x

とでもしておけば良いでしょう。

素朴な疑問ですが二つに分けると言わず、三分、四分、...と $ \sqrt{x} $ を捜索する区間を細かくしていくとどうでしょう。
例えば1から100の整数から何か目当ての整数を探すとなった時、百分探索なんてしたら、1から順番に探してくのと同じようなものなので、直感的には区間を細かくしていくよりも二分探索の方が効率が良さそうです。
一応示します。
一度の試行で調べる区間の長さを1とします。
二分探索なら、次に調べる区間の長さを1/2にまで絞れます。
三分探索を考えます。
3等分した区間のうち、$ \sqrt{x} $ が存在する区間以外を選んだときは次に調べる区間の長さを $ \frac{2}{3} $ にまで絞れます。$ \sqrt{x} $ が存在する区間を選んだときは次に調べる区間の長さを $ \frac{1}{3} $ にまで絞れます。3等分した区間のうち、どの区間に $ \sqrt{x} $ があるかは同様に確からしく、それぞれ確率 $ \frac{1}{3} $ です。
よって、三分探索で絞り込める区間の長さの期待値は、

(\frac{2}{3} + \frac{2}{3} + \frac{1}{3} ) \frac{1}{3} = \frac{5}{9}

一般にN分探索( $ N \geqq 2 $ )で絞り込める区間の長さの期待値は、

(\frac{N−1}{N} + ・・・ + \frac{N-1}{N} + \frac{1}{N} ) \frac{1}{N}\\
= \frac{(N−1)^2 + 1}{N^2}\\

二分探索とN分探索の期待値を比較すると、

\frac{(N−1)^2 + 1}{N^2} − \frac{1}{2}\\
= \frac{(N−2)^2}{2N^2} \geqq 0\\
(等号成立はN=2)

従って、二分探索により絞り込める区間の長さの期待値が最小であること、即ち二分探索が最も効率が良さそうだということが分かりました。
二分探索、結構凄いんですね。
ただ、何でもかんでも二分探索すれば良いってわけではなく、三分探索が有効なケースもあるらしいです。
その辺も気が向いたら勉強したいです。