【数の構成】互除法と仲良し「連分数」

いま、b/a という分数があるとして、同じ分数を「分子が1」の単位分数で表す方法を考えます。

この節を最初から読む
この節の目次にもどる


分数「4/20」は、分子分母を分子の「4」で割ってやって「1/5」、「3/9」も分子の「3」で割ってやって「1/3」ですから、「b/a」は、分母分子を等しく分子の「b」で割ってやれば、分子が1の分数になります。これを以下のように書くことにします。

連分数

このように、分数の中に分数が入れ子で入っている分数を、連分数(continued fraction)といいます。連分数自体は、入れ子になっていさえすればよく、別に分子が1でなくてもかまいませんし、入れ子は1層だけでなく、入れ子のまた入れ子で何層になっていてもかまいません。ただ、上記のように、ある分数があって、同じ値のまま分子を1にしてやりたいときは、分母と分子をくるっとひっくり返して、その分数を分母に入れてやればよいということは、ちょっと頭にとめておいてください。このことは逆数を掛け算する分数の割り算からも明らかですね。

逆数の割り算

さて、それでは本題に入ります。前回までみてきたユークリッドの互除法ですが、計算の中身は、余り付き割り算ですから、これを整数+分数がセットになった「帯分数」を使って以下のように表現することができます。

互除法の分数表記

互除法で大きい方の数を小さい方の数で割る時、小さい方の数(module)と一致して割り算の商になる部分は、帯分数の整数部として分数の外に追い出され、分母と残りの余りの新しい比が現れるわけです。

ここで、互除法の次ステップの割り算は、今度は余りで元の小さい方の数を割ることになりますので、これを先ほどの連分数を使って、たこ焼き屋さんがたこ焼きをひっくり返すように分母分子をくるっとひっくり返して、以下のように書いてみます。

互除法と連分数

すると、この割り算は再び整数部の商と分数の組み合わせの帯分数で書き直せますので、以下この帯分数/連分数のやり取りを地道に繰り返していくと、元の分数は以下のような複数層の入れ子になった連分数として書き換えることができます。

互除法と連分数

ユークリッドの互除法と連分数はこのように相性がよく、連分数は互除法の計算過程を分数の形式で表現したものだといえます(逆に連分数からスタートして深い階層から丹念に入れ子を解いていくと、当然ながら元の2数の比をとった分数に戻ります)。


連分数の「フラット」な表記法

互除法と連分数の表記を比べると、互除法の割り算の「商」の部分が、帯分数の整数部に残っていきますから、連分数では分子に残していった「1」と、この「商」の数字だけを使って分数が構成されることになります。いいかえれば、このタイプの連分数では、商の数値だけ分かれば、全体の形を特定でき、元の分数も復元できるのです。

互除法それ自体の計算では、商はどうでもよくて余りを使っていっしょうけんめい計算していましたが、連分数では反対に商だけが重要というわけです。

そこで、上の連分数の表記を、この商の部分だけを抜き出して、ぺったんこに [1,1,1,3 ] のように書くことがあります。連分数をまともに分数で書くと、上のようにものすごくスペースを食って邪魔くさいので、こう書くと1行で書けて便利です。いわば連分数をカラカラに干した「干もの」、連分数のインスタントラーメンみたいなもので、もとの膨らんだ姿は、頭の中でお湯をかけて戻してやります。

連分数の簡略表記

さらに、前回、互除法の計算を簡単に行うツールを試作しましたが、上記の話をベースにこれを改造し、互除法のプロセスの流れを逆にたどって、商の部分の数値を入れると、互除法の元の2数(元の分数)を復元するツールというのを作ってみることにします。関数の設定は以下のとおりです。

連分数計算マシン

上の例からわかるように、このツールは、連分数に膨らませた分数を、一層づつ畳んでいって、もとの2つの整数の分数に戻す計算をしていることになります。

これで互除法計算マシンが「連分数計算マシン」へと発展しました。


さて、ここまでは実は水泳の前の準備運動で、以上を土台にして、次で連分数のほんとうの威力、目眩めくその不思議世界(オオゲサ)へと進みます。


<参考にさせていただいた資料>
 Continued Fractions - An introduction ( University of Surrey )


posted by oto-suu 11/12/10 | TrackBack(0) | 数の構成 | このブログの読者になる | 更新情報をチェックする
<< 前のページ | TOP | 次のページ >>
この記事へのトラックバックURL
http://blog.seesaa.jp/tb/225308520
※ブログオーナーが承認したトラックバックのみ表示されます。

この記事へのトラックバック