rough2/
lib.rs

1#[inline]
2fn get_err(actual: f64, denominator: i128, numerator: i128) -> f64 {
3    (actual - (numerator as f64 / denominator as f64)).powi(2)
4}
5
6fn multi_for_err(err: f64, verbose: bool) -> i128 {
7    let el = (err).log2();
8
9    // PERF: Find a better way to calculate the large_room_factor. Multiplying
10    // el with a factor f > 1 improves performance quite a bit, but if f is too
11    // large, it degrades again. There must be some mathmatical relationship
12    // we could abuse for performance here.
13
14    // WARN: a too high large_room_factor >= 16 (maybe lower too) also produces wrong results...
15
16    let large_room_factor = 4.0;
17    let m = (el * large_room_factor).max(1.0).round() as i128;
18    if verbose {
19        println!("log_2(e)={el}; m={m}");
20    }
21    m
22}
23
24#[inline]
25pub fn find_closest_numerator(
26    actual: f64,
27    denominator: i128,
28    verbose: u8,
29    max_iterations: u32,
30) -> i128 {
31    find_closest_numerator_with_err(actual, denominator, verbose, max_iterations).1
32}
33
34pub fn find_closest_numerator_with_err(
35    actual: f64,
36    denominator: i128,
37    verbose: u8,
38    max_iterations: u32,
39) -> (f64, i128) {
40    let mut numerator: i128 = 1;
41    let mut err: f64 = f64::MAX;
42    let mut lerr: f64 = err;
43    let mut uerr: f64;
44    let mut derr: f64;
45
46    // edge case outputs the maximum error with correct result if we dont account for it
47    if denominator == 1 && actual == 1.0 {
48        return (0.0, 1);
49    }
50
51    let mut i = 0;
52    loop {
53        debug_assert!(lerr.abs() >= err.abs(), "|{lerr}| >= |{err}|");
54        lerr = err;
55
56        uerr = get_err(actual, denominator, numerator + 1);
57        derr = get_err(actual, denominator, numerator - 1);
58
59        if err == 0.0 || (uerr >= lerr && derr >= lerr) {
60            break;
61        } else if uerr < derr {
62            numerator += multi_for_err(uerr, verbose >= 2);
63            err = uerr;
64        } else {
65            numerator -= multi_for_err(derr, verbose >= 2);
66            err = derr;
67        }
68
69        if verbose >= 2 {
70            println!(
71                "i={i:03} => n={numerator} | e={err}{}\n",
72                if uerr < derr { "⬆" } else { "⬇" }
73            );
74        }
75        if max_iterations > 0 {
76            i += 1;
77            if i >= max_iterations {
78                eprintln!("Reached maximum iterations of {i}, returning");
79                break;
80            }
81        }
82    }
83    (err, numerator)
84}
85
86#[cfg(test)]
87mod tests {
88    use crate::{find_closest_numerator, get_err};
89
90    #[test]
91    fn test_get_err() {
92        assert_eq!(0.0, get_err(0.5, 2, 1));
93        assert_eq!(0.25, get_err(0.5, 2, 2));
94        assert_eq!(0.25, get_err(0.5, 2, 0));
95        assert!(get_err(0.5, 2, 2) > get_err(0.5, 2, 1));
96    }
97
98    #[test]
99    fn test_fcn_2() {
100        assert_eq!(find_closest_numerator(0.5, 2, 0, 0), 1);
101        assert_eq!(find_closest_numerator(0.6, 2, 0, 0), 1);
102        assert_eq!(find_closest_numerator(0.4, 2, 0, 0), 1);
103        assert_eq!(find_closest_numerator(2.0, 2, 0, 0), 4);
104        assert_eq!(find_closest_numerator(2.1, 2, 0, 0), 4);
105        assert_eq!(find_closest_numerator(15.0, 2, 0, 0), 30);
106        assert_eq!(find_closest_numerator(15.4, 2, 0, 0), 31);
107    }
108
109    #[test]
110    fn test_fcn_edgecases() {
111        assert_eq!(find_closest_numerator(15.0, 19, 0, 0), 285);
112        assert_eq!(find_closest_numerator(11.541, 4941, 0, 0), 57024);
113    }
114}
rough2/lib.rs

rough2/
lib.rs
