Skip to content

Instantly share code, notes, and snippets.

# thomcc/approx_rat_cfrac.rs

Created April 2, 2021 09:57
Show Gist options
• Save thomcc/e1702ea6bc4bd0216943931071a4ab5e to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 // 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)); }
to join this conversation on GitHub. Already have an account? Sign in to comment