連分数とは

連分数とは、以下のように分母に分数が含まれているような分数です。ただし、 $a_n$ と $b_n$ は整数です。また、 $b_n$ がすべて $1$ の場合、正則連分数と呼ばれます。（この記事では正則連分数のみを対象とするので、以降「連分数」と表記したものは正則連分数を指します。）

x = a_0 + \frac{b_1}{a_1 + \frac{b_2}{a_2 + \frac{b_3}{a_3 + ...}}}

上記の $x$ が有理数の場合 $a_n$ は有限ですが、無理数の場合は無限に続きます。例として、黄金数 $\varphi = \frac{1 + \sqrt{5}}{2}$ は以下のように $a_n$ がすべて $1$ で、それが無限に続きます。

x = 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + ...}}}

連分数展開とは

ある数を連分数に変形することを、連分数展開 と呼びます。小数は以下の手順で連分数展開できます。

整数部分と小数部分に分ける
分母と分子を分子で割る
分母に対して 1 ~ 3 を繰り返す

例として、 $1.6$ を連分数展開してみます。

\begin{align}
1.6 &= 1 + \frac{6}{10} & (1.6 を整数部分と小数部分に分ける) \\
    &= 1 + \frac{1}{\frac{10}{6}} & (分母と分子を分子で割る) \\
    &= 1 + \frac{1}{1 + \frac{4}{6}} & (10/6 を整数部分と小数部分に分ける) \\
    &= 1 + \frac{1}{1 + \frac{1}{\frac{6}{4}}} & (以下繰り返し) \\
    &= 1 + \frac{1}{1 + \frac{1}{1 + \frac{2}{4}}} \\
    &= 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{2}}} \\
\end{align}

できました。ちなみに、$1.6$ は黄金数 $1.618...$ に近い数なので、 $1.6$ の連分数展開も途中まで黄金数と同様に $a_n$ が $1$ になっています。このように、連分数は無理数を有理数で近似する際にも役立つらしいです。詳細は「ディオファントス近似」で調べてみてください。

他にも、連分数に関連する様々な情報が Wikipedia にも書かれていて、面白いのでおすすめです。

小数を連分数展開するプログラム

ここからが本題です。

手計算で連分数展開するのは面倒なので、プログラムで連分数展開しましょう。
先程紹介した手順を Rubyで書いてみます。

1. 整数部分と小数部分に分ける

Ruby には有理数の計算をするための Rational クラスがあるので、それを使います。
整数部分は Rational#floor を使い、小数部分は元の数から整数部分を引けば求まります。

x = Rational("1.6")

a = x.floor
b = x - a

p "a = #{a}, b = #{b}" #=> a = 1, b = 3/5

$1.6$ を $1 + \frac{3}{5}$ に変換できました。

2. 分母と分子を分子で割る

ステップ3では、 $1 + \frac{1}{t}$ の $t$ の部分が必要になります。

前のステップで b に小数部分が入っているので、 $b = \frac{1}{t}$ となり、これを変形すると $t = \frac{1}{b}$ になります。つまり、$\frac{1}{b}$ を求めればOKです。

Ruby では $\frac{1}{b}$ を Rational(1, b) と書けます。

t = Rational(1, b)
p "t = #{t}" # => t = 5/3

これで $1 + \frac{3}{5}$ を $1 + \frac{1}{5/3}$ に変換できました。

3. 分母に対して 1 ~ 3 を繰り返す

あとは $t = 5/3$ に対して 1 ~ 3 を繰り返すだけです。
なのでループを回せば完成ですが、注意点として b が 0 になったら止める必要があります。

完成したプログラムはこちらです。

def cf(x)
  tmp = x

  loop do
    a = tmp.floor # 整数部分
    b = tmp - a   # 小数部分

    if b == 0
      puts a
      break
    end

    print "#{a}, "
    tmp = Rational(1, b) # t = 1/b
  end
end

実行すると、$a_n$ が順番に出力されます。

> cf(Rational("1.6"))
1, 1, 1, 2

1.6 は $1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{2}}}$ なので、正しく動いていそうです。

（誤差などはあまり考慮していないので、入力によっては正しく計算されない可能性があります。）

あとがき

連分数展開のプログラムを作ったきっかけは、とある謎解きの問題です。その問題の鍵の一つに連分数展開が必要だったので、作ってみました。

業務などでは連分数展開のプログラムが役に立つことは少ないと思いますが、競技プログラミングやCTFで活用できる場面もあるらしいので、その時はこの記事を思い出してみてください。

Rubyで連分数展開のプログラムを書いてみた