nekolib/math/
continued_fraction_.rs

1//! 連分数展開。
2
3/// 連分数展開。
4///
5/// $[a\_0, a\_1, \\dots, a\_{i-1}]$ の連分数展開。
6/// $a\_\\bullet$ を生成するイテレータから
7/// $$
8/// a\_0 + \\frac{1}{a\_1 + \\frac{1}{\\cdots\\, + \\frac{1}{a\_{\\bullet}}}}
9/// $$
10/// を生成するイテレータを作る。
11///
12/// # Implementation notes
13/// [`std::iter::successors`](https://doc.rust-lang.org/std/iter/fn.successors.html)
14/// によって次の項が計算されるタイミングの関係で、
15/// 実際には必要ない値の計算のせいでオーバーフローし、panic するのを避けるため、
16/// 同等の処理を `map` 中に再度書いている。
17///
18/// Pell 方程式を解く際、解は [`i128`](https://doc.rust-lang.org/std/primitive.i128.html)
19/// に収まるが上記の問題で panic したのでこうなった。
20/// 実際には release build では問題なく動くことが予想されるので無視してもいい気もするが...
21///
22/// # Examples
23/// ```
24/// use nekolib::math::continued_fraction;
25///
26/// let frac_exp = [1, 2];
27/// let sqrt3 = std::iter::once(1).chain(frac_exp.iter().copied().cycle());
28/// let mut it = continued_fraction(sqrt3);
29/// assert_eq!(it.next(), Some((1, 1)));
30/// assert_eq!(it.next(), Some((2, 1)));
31/// assert_eq!(it.next(), Some((5, 3)));
32/// assert_eq!(it.next(), Some((7, 4)));
33/// assert_eq!(it.next(), Some((19, 11)));
34/// assert_eq!(it.next(), Some((26, 15)));
35///
36/// let (x, y) = it.nth(24).unwrap();
37/// assert!(((x as f64 / y as f64) - 3.0_f64.sqrt()).abs() < 1.0e-16);
38/// ```
39pub fn continued_fraction(
40    mut a: impl Iterator<Item = i128>,
41) -> impl Iterator<Item = (i128, i128)> {
42    let a0 = a.next().unwrap();
43    let frac = std::iter::successors(
44        Some(((1, a0), (0, 1), a.next().unwrap())),
45        move |&((nx, ny), (dx, dy), ai)| {
46            Some(((ny, nx + ai * ny), (dy, dx + ai * dy), a.next().unwrap()))
47        },
48    )
49    .map(|((nx, ny), (dx, dy), ai)| (nx + ai * ny, dx + ai * dy));
50    std::iter::once((a0, 1)).chain(frac)
51}
nekolib/math/continued_fraction_.rs

nekolib/math/
continued_fraction_.rs
