ContFract!

ユークリッドの互除法 (Euclidean Algorithm) は最大公約数 (GCD) を求めるときに使うアルゴリズムとして有名ですが、連分数 (continued fraction) 展開にも適用できます。

連分数展開

`n`	部分商 `a_n`	近似分数 `p_n`/`q_n`

[ 戻る ]

使用方法

分子 (numerator) は0以上9007199254740991 (=2⁵³−1) 以下の実数 (real number)、分母 (denominator) は1以上9007199254740991以下の自然数 (natural number) を扱うことができます。
実数を連分数展開するときは、分子に実数、分母に1を入力します。
[計算]ボタンで計算します。
[クリア]ボタンで入力値と結果を消去できます。
算出する項目の意味は次の通りです。

部分商 (partial quotient)

実数 R を連分数展開したときに現れる各々の整数成分 $a_{n}$
$\begin{matrix} R = a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2} + \frac{1}{a_{3} + \dots}}} & ≕ [a_{0}; a_{1}, a_{2}, a_{3}, \dots] \end{matrix}$

近似分数 (convergent)

連分数展開を途中で打ち切って得られる分数 (fraction) $\frac{p_{n}}{q_{n}}$

[ 戻る ]

利用上の注意

Microsoft Edge、Internet Exploler 11、FireFox 45.0以降での動作を確認しています。
その他のブラウザでの動作は保証いたしません。
サポートは一切行いません。
気が向いたときに改良や修正をします。

[ 戻る ]

アルゴリズム

2つの自然数a, b(≠0)について、aをbで除したときの商 (quotient) をq、剰余 (remainder) をr としたとき、qが連分数の部分商 (項) となります。

a = b q + r \Leftrightarrow \frac{a}{b} = q + \frac{1}{\frac{b}{r}}

右側の式の $\frac{b}{r}$ を新たに $\frac{a}{b}$ とおいて、r=0 となるまで計算を繰り返すことで、全ての部分商を得ることができます。

var euclidean = function(a, b) {
/* Euclidean Algorithmによる連分数展開 */
	var q = [], r;
	var i = 0;
	const max_term = 100;	// 最大項数
	while (b !== 0 && i <= max_term) {
		q[i++] = Math.floor(a / b);
		r = a % b;
		a = b;
		b = r;
	}
	return q;
};

eucldiean(a,b)関数の第1引数 a は連分数展開する数値の分子、第2引数 b は分母で、戻り値は連分数の部分商配列です。

最大公約数の計算では停止性 (termination) が保証されていますが、実数の連分数展開では、丸め誤差 (rounding error) の蓄積や桁落ち (cancellation) による有功桁数 (significant digits) の減少により、停止性が確実に保証されているとは言い切れません。このため、最大項数 max_term によって停止性を保証しています。

アルゴリズム上では a≥b の必要がありますが、a<b であっても1周目のループで aとbが交換され、条件を満たすようになります。

部分商 a[n] から近似分数 p_n/q_n を以下の漸化式で求めることができます。

{\begin{matrix} p_{-2} = 0, p_{-1} = 1, p_{n} = a_{n} p_{n - 1} + p_{n - 2} \\ q_{-2} = 1, q_{-1} = 0, q_{n} = a_{n} q_{n - 1} + q_{n - 2} \end{matrix} (n ≧ 0)

若しくは上の漸化式を行列化して求めることもできます。当研究室ではこちらを採用しています。

(\begin{matrix} p_{0} & p_{-1} \\ q_{0} & q_{-1} \end{matrix}) = (\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}) (\begin{matrix} a_{0} & 1 \\ 1 & 0 \end{matrix}), (\begin{matrix} p_{n} & p_{n - 1} \\ q_{n} & q_{n - 1} \end{matrix}) = (\begin{matrix} p_{n - 1} & p_{n - 2} \\ q_{n - 1} & q_{n - 2} \end{matrix}) (\begin{matrix} a_{n} & 1 \\ 1 & 0 \end{matrix}) (n ≧ 1)

/* 連分数展開による近似分数 */
var multi_matrix = function(a, b) {
/* 2×2行列の積 */
	return [[a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
			[a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]]];
};
var a = euclidean(num, denom);		// num/denomの連分数展開
var convergent = [[1, 0], [0, 1]];	// 連分数展開における近似分数(convergent)
var conv_text = [];					// 近似分数の文字列配列
for (var i = 0; i < a.length; i++) {
		convergent = multi_matrix(convergent, [[a[i], 1], [1, 0]]);
		conv_text[i] = convergent[0][0] + '/' + convergent[1][0];
}

表の可変行数に関するアルゴリズムは、小技集 "Tips!" で公開しています。

[ 戻る ]

参考文献

奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、平成6年9月25日初版第12刷（平成3年2月25日初版第1刷）

[ 戻る ]