Function nekolib::math::stern_brocot

pub fn stern_brocot(
    n: i128,
    large: impl FnMut(i128, i128) -> bool,
    ok: impl FnMut(i128, i128) -> bool
) -> Result<(i128, i128), ((i128, i128), (i128, i128))>

Stern–Brocot tree

$a/b = 0/1=0$ と $c/d = 1/0=\infty$ で初期化し、その mediant $x/y = (a+b)/(c+d)$ を探索する。

$x/y$ が所望の条件 ok を満たすならそれを Ok として返す。 条件 large を満たすなら $c/d\gets x/y$、そうでなければ $a/b\gets x/y$ として探索を進める。 分母が $n$ を超えても ok を満たさなければ、$((a, b), (c, d))$ を Err として返す。

Examples

use nekolib::math::stern_brocot;

let (num, den) =
    stern_brocot(10_i128.pow(18), |n, d| n * n > 3 * d * d, |_, _| false)
    .err().unwrap().0;

let sqrt3 = num as f64 / den as f64;
assert!((sqrt3 - 3.0_f64.sqrt()).abs() < 1.0e-16);
assert_eq!((num, den), (734231055024833855, 423908497265970753));