Function nekolib::math::continued_fraction

pub fn continued_fraction(
    a: impl Iterator<Item = i128>
) -> impl Iterator<Item = (i128, i128)>

連分数展開。

$[a_0, a_1, \dots, a_{i-1}]$ の連分数展開。 $a_\bullet$ を生成するイテレータから $$ a_0 + \frac{1}{a_1 + \frac{1}{\cdots\, + \frac{1}{a_{\bullet}}}} $$ を生成するイテレータを作る。

Implementation notes

std::iter::successors によって次の項が計算されるタイミングの関係で、 実際には必要ない値の計算のせいでオーバーフローし、panic するのを避けるため、 同等の処理を map 中に再度書いている。

Pell 方程式を解く際、解は i128 に収まるが上記の問題で panic したのでこうなった。 実際には release build では問題なく動くことが予想されるので無視してもいい気もするが…

Examples

use nekolib::math::continued_fraction;

let frac_exp = [1, 2];
let sqrt3 = std::iter::once(1).chain(frac_exp.iter().copied().cycle());
let mut it = continued_fraction(sqrt3);
assert_eq!(it.next(), Some((1, 1)));
assert_eq!(it.next(), Some((2, 1)));
assert_eq!(it.next(), Some((5, 3)));
assert_eq!(it.next(), Some((7, 4)));
assert_eq!(it.next(), Some((19, 11)));
assert_eq!(it.next(), Some((26, 15)));

let (x, y) = it.nth(24).unwrap();
assert!(((x as f64 / y as f64) - 3.0_f64.sqrt()).abs() < 1.0e-16);