nekolib/math/
stern_brocot_.rs

1//! Stern--Brocot tree
2
3/// Stern--Brocot tree
4///
5/// $a/b = 0/1=0$ と $c/d = 1/0=\\infty$ で初期化し、その mediant
6/// $x/y = (a+b)/(c+d)$
7/// を探索する。
8///
9/// $x/y$ が所望の条件 `ok` を満たすならそれを [`Ok`] として返す。
10/// 条件 `large` を満たすなら $c/d\\gets x/y$、そうでなければ $a/b\\gets x/y$
11/// として探索を進める。
12/// 分母が $n$ を超えても `ok` を満たさなければ、$((a, b), (c, d))$ を
13/// [`Err`] として返す。
14///
15/// [`Ok`]: https://doc.rust-lang.org/nightly/std/result/enum.Result.html#variant.Ok
16/// [`Err`]: https://doc.rust-lang.org/nightly/std/result/enum.Result.html#variant.Err
17///
18/// # Examples
19/// ```
20/// use nekolib::math::stern_brocot;
21///
22/// let (num, den) =
23///     stern_brocot(10_i128.pow(18), |n, d| n * n > 3 * d * d, |_, _| false)
24///     .err().unwrap().0;
25///
26/// let sqrt3 = num as f64 / den as f64;
27/// assert!((sqrt3 - 3.0_f64.sqrt()).abs() < 1.0e-16);
28/// assert_eq!((num, den), (734231055024833855, 423908497265970753));
29/// ```
30pub fn stern_brocot(
31    n: i128,
32    mut large: impl FnMut(i128, i128) -> bool,
33    mut ok: impl FnMut(i128, i128) -> bool,
34) -> Result<(i128, i128), ((i128, i128), (i128, i128))> {
35    let (mut a, mut b) = (0, 1);
36    let (mut c, mut d) = (1, 0);
37    loop {
38        let x = a + c;
39        let y = b + d;
40        if y > n {
41            return Err(((a, b), (c, d)));
42        }
43        if ok(x, y) {
44            return Ok((x, y));
45        }
46        if large(x, y) {
47            c = x;
48            d = y;
49        } else {
50            a = x;
51            b = y;
52        }
53    }
54}
nekolib/math/stern_brocot_.rs

nekolib/math/
stern_brocot_.rs
