Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
// 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));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment