Continued Fraction Algorithm

個人的メモ

すべての有理数はちょうど $2$ つの連分数展開形(初めは非負整数で, その後自然数が続く形)を持つ. 例えば $13 / 36$ なら $\{ 0; 2, 1, 3, 2, 1 \}$ と $\{ 0; 2, 1, 3, 3 \}$ である. この列は $(13, 36)$ の組についてユークリッドの互除法を計算したときの商の列に等しく, 実際 $\{ 0, 2, 1, 3, 3 \}$ になることが分かる. そのため連分数展開したときの長さは $\log ( \max (分子, 分母))$ で計算量もこれに等しくなる.
Stern-Brocot 木との関係も深く例えば Stern-Brocot 木上の分数 $q = \{ a_0; a_1,\ldots, a_k \} = \{ a_0; a_1,\ldots, a_k-1, 1 \}$ についてその $2$ つの子は $\{ a_0; a_1,\ldots, a_k+1 \}$, $\{ a_0; a_1,\ldots, a_k-1, 2 \}$ となる. ここで $k$ が奇数のときは前者が左の子, $k$ が偶数のときは後者が左の子となる(連分数展開の大小は辞書順の大小と一致しないことに注意する.)
$p$ と $q$ の真に間に存在する有理数 $r$ で (分子) + (分母) が最も小さいものは　Stern-Brocot 木上で $p$ と $q$ の LCA を探索することでも求めることができるが, 以上の事実から根からの探索はだいたい連分数展開したときの項の和の分だけ時間がかかるため効率が良くない.
ただ連分数展開ベースで考えると, Stern-Brocot 木上の $p$, $q$ の LCA は { $p$, $q$ の連分数展開形での prefix, $\min$ ( $p$ におけるその次の項(無い場合は $\infty$), $q$ におけるその次の項(無い場合は $\infty$) ) $+ 1$ } の形で書けそうである. これは少し嘘で $p$, $q$ が Stern-Brocot 木上で先祖-祖先の関係になっているとき $r$ として $p$ や $q$ が出てきてしまうことがある. ただ各 $p$, $q$ それぞれについて $2$ 種類の連分数展開, 計 $4$ 種類の連分数展開の組を考えることでそのうちのどれかで, 得られた $r$ は valid になる.
この計算は連分数展開を行なったときの項の数分だけの計算で済むため, 時間計算量は値の $\log$ で抑えられることが分かる.