approx_rat_cfrac.rs

// type Int = i128;
type Int = i64;

type Rat = (Int, Int);

/// Quick and dirty (no overflow handling) continued fraction-based
/// rational approximation.
///
/// Returns `(p/q, was_exact)` where p/q is an approximation of `n/d`,
/// where neither `p` nor `q` are above `limit`. `was_exact` is true if
/// the result is exact.
pub fn approx_rat(n: Int, d: Int, limit: Int) -> (Rat, bool) {
    let mut prev: Rat = (0, 1);
    let mut cur: Rat = (1, 0);
    let mut rest = (n, d);
    // let mut rest = if (n & d) < 0 { (-n, -d) } else { (n, d) };
    while rest.1 != 0 {
        // next term of continued fraction
        let int = rest.0 / rest.1;
        let rem = rest.0 % rest.1;
        let last = core::mem::replace(&mut prev, cur);
        // incorporate the term (todo: consider overflow, i guess).
        cur = (cur.0 * int + last.0, cur.1 * int + last.1);
        if cur.0.abs() > limit || cur.1 > limit {
            // next term exceeds limit, return prev
            return (prev, false);
        }
        rest = (rest.1, rem);
    }
    (cur, true)
}

#[test]
fn test() {
    let pi_n = 31415926535;
    let pi_d = 10000000000;
    assert_eq!(approx_rat(-pi_n, pi_d, 256), ((22, -7), false));
    assert_eq!(approx_rat(pi_n, pi_d, 1024), ((355, 113), false));
    assert_eq!(
        approx_rat(-pi_n, pi_d, 1000000000000),
        ((6283185307, -2000000000), true),
    );
    assert_eq!(approx_rat(10, -4, 100), ((5, -2), true));
    assert_eq!(approx_rat(-10, -4, 100), ((5, 2), true));
}