Pythonプログラミング（ステップ４・反復処理・連分数）

１．連分数と実数の「よい」近似法

実数 $\sqrt{2} = 1.41421356\cdots$ をなるべく「良く」近似できるような分数の表式（有理数）を見つけたい。 いちばん荒い近似としては 1 が考えられるが、これでは大雑把すぎてあまり実用的とは言えない。 $\frac{141}{100} = 1.41$ くらいにすれば、かなり近い値と言えるかもしれないが、 たとえば $\frac{7}{5} = 1.4$ とした場合でも、それほど値に大きな違いは無い。 その意味では、$\frac{7}{5}$は$\frac{141}{100}$に比べて「無駄なく」$\sqrt{2}$を近似していると言えるだろう。

このように「無駄」が少なく良い近似を与えるような有理数を求める方法として、連分数展開（continued fraction expansion）が知られている。

$\sqrt{2}$を例に、実際にそれを行ってみよう。

調べたい数を (整数部) + (小数部) に分解する。$\sqrt{2}$の場合は $\sqrt{2} = 1 + (\sqrt{2}-1) = 1 + 0.41421356\cdots$である。 ここで、 $$ \begin{eqnarray} a_0 & = & 1 \\ b_0 & = & \frac{1}{0.41421356\cdots} = \frac{1}{\sqrt{2}-1} = 1 + \sqrt{2} \end{eqnarray} $$ と置くと $$ \sqrt{2} = a_0 + 1/b_0 $$ と分解できたことになる。小数部の逆数 $b_0$ を考えるところがミソである。

次に、$b_0$に対しても、同様に整数部と小数部に分け $$ b_0 = 1 + \sqrt{2} = 2 + 0.41421356\cdots $$ とすることで、 $$ b_0 = a_1 + 1/b_1 $$ とさらに分解できる。 ただし、ここで $$ \begin{eqnarray} a_1 & = & 2 \\ b_1 & = & \frac{1}{0.41421356\cdots} = \frac{1}{\sqrt{2}-1} = 1 + \sqrt{2} \end{eqnarray} $$ である。

同様の操作を繰り返すと、展開の$n$段目（ただし$n\ge 1$）では $$ \begin{eqnarray} a_n & = & 2\\ b_n & = & 1 + \sqrt{2} \end{eqnarray} $$ であることが確認できる。

以上をまとめると、$\sqrt{2}$の連分数展開として $$ \sqrt{2} = 1 + \frac{1}{ 2 + \frac{1}{ 2 + \frac{1}{ 2 + \frac{1}{\cdots} } } } $$ が得られたことになる。

連分数を数式で表現するのはなかなか厄介であるため、上記の連分数は $a_n$を並べて $$ [1 ; 2, 2, 2, 2, 2, \cdots] $$ のように表記することが多い。 同様に $\sqrt{3}$を連分数展開すると $$ [1 ; 1, 2, 1, 2, 1, 2, \cdots ] $$ であり、黄金比のそれは $$ [1 ; 1, 1, 1, 1, 1, 1, \cdots] $$ となる。

$\sqrt{2}$は無理数であることから、この展開は無限に続くが、それを$n$段目で打ち切った数を $c_n$ とすれば、 $$ c_0 = 1 $$ $$ c_1 = 1 + \frac{1}{2} = \frac{3}{2} = 1.5 $$ $$ c_2 = 1 + \frac{1}{2 + \frac{1}{2}} = \frac{7}{5} = 1.4 $$ $$ c_3 = 1 + \frac{1}{2 + \frac{1}{2 + \frac{1}{2}}} = \frac{17}{12} = 1.41666\cdots $$ といった具合に、「小さい」分数で良い近似値が得られていることがわかる。

　練習：連分数展開

以下に、実数値を入力すると、その連分数展開($a_n$の値）を出力するPythonコードの例を示す。

具体的な値を入力して動作を確認してみなさい。

リストや関数について知識のある者は、各段階での近似値（$c_n$）を出力するように改良してみなさい。

# coding: utf-8

import math

x = float(input("x="))
b = x
while True:
    a = math.floor(b)
    print(a,"+ 1/")    
    if abs(b-a) < 0.0001:
        break
    b = 1/(b-a)

　ヒント

　解説: fractionsモジュール

連分数の計算などを行う際に、分数は分数として計算したくなる。そのような用途に、Pythonの標準モジュールの中にfractionsが含まれている。

詳しい機能はマニュアル等を参照してもらうこととして、連分数展開を与えると、その値を有理数で表示するコードの例の以下に示す。

# coding: utf-8

from fractions import Fraction

contfrac = [1,2,2,2,2,2]

c = Fraction(contfrac.pop())

for a in reversed(contfrac):
    c = Fraction(a) + Fraction(1)/Fraction(c)

print(c)