好きをブチ抜く

「好き」をブチ抜く

本、映画、科学、哲学、心理、すごい人の考え方など。あらゆる情報を編集したい。

Pythonで平方根を求める 2分探索の利用【Pythonで数学パズル】

記事の内容

今回は、pythonに慣れるために簡単な数学パズルのようなものに挑戦します。

そのテーマは、「平方根を求める」です。どのようにコードを欠けば、効率よくある数の平方根を求めることができるのか、いろいろと工夫してみましょう。

python初心者の方にも、アルゴリズム初心者の方にもおすすめな記事です。「平方根」というテーマのもと、プログラミングの考え方に慣れていきましょう!

問題解決のPythonプログラミング

こちらの本にのっている題材を引用させてもらいます。そのほかにも、いろいろと面白い問題がのっているので、ぜひ読んでみてください。



反復法

まずは、素直に平方数を順に作っていく方法です。順に作っていき、もとめたいある数に一致するまで続けます。1,2,3,4,,,,の平方数を順に作成していきます。例えば、「64の平方根をもとめよ」という問題なら、1の2乗から8の2乗まで順に作ると、(8の2乗)=64となり、64の平方根は8だと求めることができます。

コンピュータが得意なしらみつぶしの方法と言えるでしょう。

ただし、注意点があります。それは、平方根がぴったりと整数になることはまれであるということです。よって、小数まで考えます。小数点以下のどの桁まで計算するか考えるべきです。

そのため、次の2点を工夫します。
・どれだけ平方根に近いのか基準値をもうける →epsilon
・whileループでどれくらい増やすか注意 →increment

この2点に注意したコードは次のようになります。


実装1

#探索空間を幅がincrementのスロットに分割している。平方根がどのスロットにあるのか次々に調べていく。

def findSquareRootWithinError(x, epsilon, increment):
   if x < 0:
       print("Sorry, no imaginary numbers")
       return
    numGuesses = 0 #whileループの繰り返し回数を計算
    ans = 0.0
    while x - ans**2 > epsilon:
       ans += increment
       numGuesses += 1
    print("numGuesses =", numGuesses)
    if abs(x - ans**2) > epsilon:
       print("Failed on square root of", x)
    else: 
       print(ans, "is close to square root of", x)

結果1

findSquareRootWithinError(64, .01, .001)
>>>numGuesses = 8000
8.000000000001005 is close to square root of 64

findSquareRootWithinError(65535, .01, .001)
>>>numGuesses = 255999
Failed on square root of 65535

findSquareRootWithinError(65535, .01, .00001)
>>>numGuesses = 25599803
255.99803007005775 is close to square root of 65535


スロットを細かくすればするほど、探索回数も増えていくのがわかります。すなわち、実行時間が増えていきます。もっと効率よく探索する方法はないでしょうか?




二分探索

もっと効率よく探索する方法があります。それは、探索する区間をしぼるというものです。各区間の中点の値とまずは比較することで、区間を右と左にわけることができます。右の区間に求める値があるだろうな、と絞ることができるので、左の区間の分はばっさりと捨てていいわけです。こうして、どんどん調べなくていい区間を捨てていくことができます。こうして、探索の効率をあげます。

それでは、2分探索を利用したコードを見てみましょう。

#2分法で探索

def bisetionSearchForSquareRoot(x, epsilon):
    if x < 0:
        print("Sorry, no imaginary numbers")
        return
    numGuesses = 0
    low = 0.0
    high = x
    ans = (high + low) / 2.0
    while abs(ans**2 - x ) >= epsilon:
        if ans**2 < x:
            low = ans
        else:
            high = ans
        ans = (high + low) / 2.0
        numGuesses += 1
    print("numGuesses = ", numGuesses)
    print(ans, "is close to square root of", x)
        

実行結果もみてみましょう。探索回数が飛躍的に減少しています。
bisetionSearchForSquareRoot(65535, .01)

>>>numGuesses = 24
255.99804684519768 is close to square root of 65535


ただし、2分探索を使うことができる条件に注意です。それは、探索するデータがあらかじめソートされていることです。たとえば、整数のデータなら、その大きさ順に並んでいる必要があります。ですので、ソートアルゴリズムと一緒に学習するのがいいかもしれません。