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{array}{rcl}{a}_0& =& 1\\ b_0& =& \frac{1}{0.41421356\cdots }=\frac{1}{\sqrt{2}-1}=1+\sqrt{2}\end{array}$$ と置くと $$\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{array}{rcl}{a}_1& =& 2\\ b_1& =& \frac{1}{0.41421356\cdots }=\frac{1}{\sqrt{2}-1}=1+\sqrt{2}\end{array}$$ である。

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

以上をまとめると、$\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)