ユークリッド互除法と連分数と円周率の有理数近似

ユークリッド互除法

ユークリッドの互除法と言うのはご存知でしょうか。 2つの数の最大公約数を求めるアルゴリズムですね。例えば、390と91ではこうなります。

\[\begin{aligned} 390 &= 91 \times 4 + 26 \\ 91 &= 26 \times 3 + 13 \\ 26 &= 13 \times 2 + 0 \end{aligned}\]

商と余りを計算して、除数と余りでもう一度互除法に…と順番に繰り返していくと最終的に最大公約数が13であるとわかります。

連分数表示

これらの等式の両辺を除数で割って、次のように変形してみましょう。

\[\begin{aligned} \frac{390}{91} &= 4 + \frac{26}{91} \\ \frac{91}{26} &= 3 + \frac{13}{26} \\ \frac{26}{13} &= 2 \end{aligned}\]

更にこれを逆数に。

\[\begin{aligned} \frac{91}{390} &= \frac{1}{4 + \frac{26}{91}} \\ \frac{26}{91} &= \frac{1}{3 + \frac{13}{26}} \\ \frac{13}{26} &= \frac{1}{2} \end{aligned}\]

左辺と同じものがあるので代入します。(ついでに最大公約数も分かっているので、左辺を約分します。)

\[ \frac{7}{30} = \frac{91}{390} = \frac{1}{4 + \frac{1}{3 + \frac{1}{2}}} \]

これが連分数表示です。 $\frac{1}{4+}\frac{1}{3+}\frac{1}{2}$ と書いたり、 $[0;4,3,2]$ とすることもあります。

連分数に現れてくる数値は、ユークリッド互除法の商の順番と一致していますね。

円周率でユークリッド互除法

ユークリッド互除法を円周率 $\pi$ で実験してみると次のようになります。 $\pi$ は割り切れないのでいつまでも続きます。

\[\begin{aligned} \pi &= 1 \times 3 + (\pi - 3) \\ 1 &= (\pi - 3) \times 7 + (22 - 7\pi) \\ (\pi - 3) &= (22 - 7\pi) \times 15 + (106\pi - 333) \\ (22 - 7\pi) &= (106\pi - 333) \times 1 + (355 - 113\pi) \\ &\vdots \end{aligned}\]

これを使って先の連分数表示をすることができます。

\[ \pi = [3;7,15,1,\dots] \]

この無限連分数ですが、途中で打ち切れば当然近似値が得られます。有限の連分数は順に計算すれば必ず有理数になるので、以下のように計算できます。

\[\begin{aligned} \pi &\approx [3;7] = \frac{22}{7} = 3.1428571428\dots \\ \pi &\approx [3;7,15] = \frac{333}{106} = 3.1415094339\dots \\ \pi &\approx [3;7,15,1] = \frac{355}{113} = 3.1415929203\dots \\ & \vdots \end{aligned}\]

このようにして、小数以下6桁まで一致するシンプルな近似値$\frac{355}{113}$が得られます。