Rational 連分数と最良有理近似

概要

有理数 $p/q$ の連分数展開は

$$\frac{p}{q} = a_0 + \cfrac{1}{a_1 + \cfrac{1}{a_2 + \cfrac{1}{a_3 + \cdots}}} = [a_0; a_1, a_2, a_3, \ldots]$$

と書ける表示で、$a_0 \in \mathbb{Z}$, $a_k \in \mathbb{Z}_{>0}$ ($k \geq 1$) を満たす。 有理数の場合は有限長 (連分数係数の列が有限) で終わり、無理数の場合は無限に続く。

sangi の Rational は連分数展開 toContinuedFraction() と 復元 fromContinuedFraction() を提供する。 これにより分母制約下での最良有理近似や、Float ↔ Rational 変換の応用が可能となる。

API の使い方については Rational API リファレンス — 連分数 を参照。

連分数展開 — Euclidean 過程

アルゴリズム

連分数係数 $a_k$ はユークリッドの互除法と同型の手続きで得られる。

$$\begin{aligned} (r_0, r_1) &\leftarrow (p, q), \\ a_k &= \lfloor r_k / r_{k+1} \rfloor, \\ r_{k+2} &= r_k - a_k \, r_{k+1} = r_k \bmod r_{k+1}, \\ &\text{stop when } r_{k+2} = 0. \end{aligned}$$

$\gcd(p, q)$ を求めるユークリッドの互除法と完全に同じ反復であり、 商 $a_k$ をすべて記録すれば連分数係数列が得られる。

計算量: $O(\log \min(|p|, q))$ 回の除算。 Lamé の定理により、係数列の長さは Fibonacci 数列により上から $O(\log_\phi q)$ で抑えられる ($\phi = (1+\sqrt{5})/2$)。

例

$355/113$ の連分数展開:

$$\begin{aligned} 355 &= 3 \cdot 113 + 16, & a_0 &= 3, \\ 113 &= 7 \cdot 16 + 1, & a_1 &= 7, \\ 16 &= 16 \cdot 1 + 0, & a_2 &= 16. \end{aligned}$$

よって $355/113 = [3; 7, 16]$ である。

復元

係数列 $[a_0; a_1, \ldots, a_n]$ から有理数を復元するには末尾から畳み込む。

$$x = a_n, \quad x \leftarrow a_k + 1/x \quad (k = n-1, n-2, \ldots, 0)$$

逆向きに収束分数を漸化式で生成する (次節) より高速で、整数演算のみで完結する。

収束分数の漸化式

連分数 $[a_0; a_1, \ldots, a_n]$ を $k$ 番目で打ち切った値を $k$ 番目の収束分数 (convergent) と呼ぶ:

$$\frac{p_k}{q_k} = [a_0; a_1, \ldots, a_k]$$

収束分数は次の漸化式で生成される。

$$\begin{aligned} p_{-1} &= 1, & p_0 &= a_0, & p_k &= a_k p_{k-1} + p_{k-2}, \\ q_{-1} &= 0, & q_0 &= 1, & q_k &= a_k q_{k-1} + q_{k-2}. \end{aligned}$$

$2 \times 2$ 行列の積として書くと:

$$\begin{pmatrix} p_k & p_{k-1} \\ q_k & q_{k-1} \end{pmatrix} = \begin{pmatrix} a_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} a_1 & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} a_k & 1 \\ 1 & 0 \end{pmatrix}$$

各行列の行列式は $-1$ なので、積の行列式は $(-1)^{k+1}$ となり、次の恒等式が得られる:

$$p_k q_{k-1} - p_{k-1} q_k = (-1)^{k+1}$$

これにより $p_k$ と $q_k$ は常に互いに素であり、収束分数は最初から約分済みである。

例: π の収束分数

$\pi = 3.14159265\ldots$ の連分数展開は $[3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, \ldots]$ で、最初の数項の収束分数は:

$a_4 = 292$ という大きな係数のおかげで、$355/113$ は分母を 100 倍に増やしただけで誤差が $3$ 桁向上し、 分母 $113$ までの中では極めて良い近似となる。

Stern-Brocot 木との関係

Stern-Brocot 木は、$0/1$ と $1/0$ から始まり、左右の中間分数 (mediant) を順に挟むことで、 すべての正既約分数を一度ずつ生成する 2 分木である:

$$\operatorname{mediant}\!\left(\frac{a}{b}, \frac{c}{d}\right) = \frac{a + c}{b + d}$$

連分数係数 $[a_0; a_1, a_2, \ldots]$ は Stern-Brocot 木上の経路と次のように対応する:

• 根 $1/1$ から出発
• $a_0$ 回 R (右)
• $a_1$ 回 L (左)
• $a_2$ 回 R (右)
• $\ldots$ と交互

各収束分数 $p_k/q_k$ は、$k$ 番目の左折・右折の切り替わり地点 (列車の方向転換) に対応する。 連分数展開は本質的に Stern-Brocot 木の探索経路をランレングス圧縮した表示と見なせる。

sangi の nextMinimal() (Stern-Brocot 順で次の正有理数) や nextCalkinWilf() (Calkin-Wilf 列で次の正有理数) はこの木構造を直接たどる関数である。

最良有理近似

最良近似の定義

実数 $x$ と分母制約 $D$ に対し、 分母 $q \leq D$ の有理数 $p/q$ のなかで $|x - p/q|$ を最小化するものを最良有理近似と呼ぶ。

Lagrange の定理

$x$ の連分数展開 $[a_0; a_1, a_2, \ldots]$ の収束分数 $p_k/q_k$ は最良近似であり、 次の不等式を満たす:

$$\left| x - \frac{p_k}{q_k} \right| < \frac{1}{q_k q_{k+1}} < \frac{1}{q_k^2}$$

かつ、$q \leq q_k$ なる任意の分数 $p/q \neq p_k/q_k$ に対し

$$\left| x - \frac{p_k}{q_k} \right| < \left| x - \frac{p}{q} \right|$$

これが連分数の本質的な性質であり、$\pi$ の良い有理近似 $22/7$ や $355/113$ がなぜ「良い」のかを説明する。

アルゴリズム: 分母 D 以下の最良近似

実数 $x$ の連分数係数を逐次計算し、収束分数の分母が $D$ を超える直前で打ち切る。 途中の $a_k$ を超える小さな係数 $a'_k$ を取って中間収束分数 (semiconvergent) を試す経路もあり、 この場合は分母 $D$ ぎりぎりの semiconvergent が最良近似となることがある。

Float ↔ Rational 変換

Float → Rational (精確変換)

Rational(double value) および Rational(const Float&) は IEEE 754 ビット列 (仮数 $m$ と指数 $e$) からそのまま $m \cdot 2^e$ を構成する精確変換である。 $0.1$ のような十進表記で簡単な数も IEEE 754 では 3602879701896397 / 2^55 のような近似値であり、 精確変換するとこの値がそのまま Rational になる。

Float → Rational (連分数による有理近似)

精確変換は「double 値の正確な再現」を目指すが、 「人間が意図したであろう簡潔な分数」を得たい場合は連分数による近似が有効である。 分母制約 $D$ の下での最良近似を取ることで、$0.1 \to 1/10$ や $0.3333\ldots \to 1/3$ のような自然な復元ができる。

典型的なユースケースは:

• テスト用の期待値を double で書いたあと、ハッシュ用の安定 ID として Rational 化
• UI から受け取った小数値を有理数として保管 (CAS で正確な記号計算を続けるため)
• 機械学習モデルの重みを既約分数で表現して再現性を確保

Rational → Float

逆変換 toDouble(), toFloat(), toMpFloat(prec) は 分子・分母をそれぞれ Float に変換して除算する。 $p$ と $q$ の桁数が double の有効桁数 (16 桁) を大きく超える場合、 変換結果は IEEE 754 の最近接丸めに従う。

Hurwitz の定理

連分数の最良近似性をさらに精密化した定理として Hurwitz の定理がある:

Hurwitz の定理 (1891): 任意の無理数 $\alpha$ に対し、 無限個の有理数 $p/q$ が次を満たす:

$$\left| \alpha - \frac{p}{q} \right| < \frac{1}{\sqrt{5} \, q^2}$$

定数 $\sqrt{5}$ はベストポシブルであり、これより小さい定数では成り立たない無理数が存在する。 等号を達成する無理数は黄金比 $\phi = (1+\sqrt{5})/2$ の連分数展開 $[1; 1, 1, 1, \ldots]$ に関連する数族である。

$\phi$ の連分数係数がすべて $1$ であることが、$\phi$ を「最も近似しにくい無理数」にしている。 この性質はDiophantine 近似の出発点である。

設計判断

係数列の型

toContinuedFraction() は std::vector<Int> を返す。 係数は理論上 int に収まらない場合があり (特に Float 近似経由の係数)、 Int を採用することで型変換とオーバーフローの両方を回避する。

有限長と無限長

有理数の連分数は必ず有限長で終わる。 無理数の場合は無限長になるため、sangi の toContinuedFraction() は Rational 専用 (有限長保証) であり、無理数の連分数は別 API (将来予定の Float 用 lazy continued fraction) で扱う。

末尾係数の正規化

連分数 $[a_0; a_1, \ldots, a_n]$ は $a_n = 1, n \geq 1$ のとき $[a_0; a_1, \ldots, a_{n-1} + 1]$ と同一の有理数を表す。 sangi は末尾 $a_n \neq 1$ または長さ 1 のいずれかになるよう正規化する。 これにより連分数表現が一意になり、ハッシュ・比較が単純化される。

参考文献

• Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers. 6th ed. Oxford University Press, 2008. Chapter X (連分数).
• Khinchin, A. Ya. Continued Fractions. Dover, 1997.
• Graham, R. L., Knuth, D. E., and Patashnik, O. Concrete Mathematics. 2nd ed. Addison-Wesley, 1994. §4.5 (Stern-Brocot 木).