3 ms·

Often it will be preferable to limit the error instead of the denominator. "Find the fraction with the smallest denominator that's within 0.005 of 0.33." Does p

Often it will be preferable to limit the error instead of the denominator. "Find the fraction with the smallest denominator that's within 0.005 of 0.33." Does python support this as well?

eesmith 3y ago
Not directly that I know of, but that's definitely a straight-forward mediant calculation. I'll do it all in integer ratios and assume the answer is somewhere between 0.0 and +inf, exclusive: from fractions import Fraction mid = Fraction("0.33") delta = mid * Fraction("0.005") lo = (mid - delta) lo_p, lo_q = lo.as_integer_ratio() hi = (mid + delta) hi_p, hi_q = hi.as_integer_ratio() p0, q0, p1, q1 = 0, 1, 1, 0 while True: p = p0 + p1 q = q0 + q1 if p * lo_q < lo_p * q: # p/q < lo_p/lo_q p0, q0 = p, q continue if p * hi_q > q * hi_p: # p/q > hi_p/hi_q p1, q1 = p, q continue break # in range frac = Fraction(p, q) print(f"Found: {p}/{q}") print(f"{lo} <= {frac} <= {hi}? {lo <= frac <= hi}") For your test case: Found: 22/67 6567/20000 <= 22/67 <= 6633/20000? True A grep of the CPython distribution found no use of the word "mediant".
- jepler 3y ago
  For anyone else who was puzzled at this result (rather than 1/3): The above algorithm is finding something with the relative error of at most .005 times the input value 0.33. 1/3 is the best value for the absolute error of at most .005.
  - eesmith 3y ago
    Ohh, indeed. I was thinking of measurement tolerances. Replace: delta = mid * Fraction("0.005") with delta = Fraction("0.005") and I get: Found: 1/3 13/40 <= 1/3 <= 67/200? True
  - CodesInChaos 3y ago
    I definitely meant an absolute error of 0.005, since the error approach was a generalization of "produces 0.33 when rounded to 2 decimal digits".

Often it will be preferable to limit the error instead of the denominator. "Find the fraction with the smallest denominator that's within 0.005 of 0.33." Does python support this as well?

eesmith 3y ago

Not directly that I know of, but that's definitely a straight-forward mediant calculation. I'll do it all in integer ratios and assume the answer is somewhere between 0.0 and +inf, exclusive: from fractions import Fraction mid = Fraction("0.33") delta = mid * Fraction("0.005") lo = (mid - delta) lo_p, lo_q = lo.as_integer_ratio() hi = (mid + delta) hi_p, hi_q = hi.as_integer_ratio() p0, q0, p1, q1 = 0, 1, 1, 0 while True: p = p0 + p1 q = q0 + q1 if p * lo_q < lo_p * q: # p/q < lo_p/lo_q p0, q0 = p, q continue if p * hi_q > q * hi_p: # p/q > hi_p/hi_q p1, q1 = p, q continue break # in range frac = Fraction(p, q) print(f"Found: {p}/{q}") print(f"{lo} <= {frac} <= {hi}? {lo <= frac <= hi}") For your test case: Found: 22/67 6567/20000 <= 22/67 <= 6633/20000? True A grep of the CPython distribution found no use of the word "mediant".

jepler 3y ago
For anyone else who was puzzled at this result (rather than 1/3): The above algorithm is finding something with the relative error of at most .005 times the input value 0.33. 1/3 is the best value for the absolute error of at most .005.
- eesmith 3y ago
  Ohh, indeed. I was thinking of measurement tolerances. Replace: delta = mid * Fraction("0.005") with delta = Fraction("0.005") and I get: Found: 1/3 13/40 <= 1/3 <= 67/200? True
- CodesInChaos 3y ago
  I definitely meant an absolute error of 0.005, since the error approach was a generalization of "produces 0.33 when rounded to 2 decimal digits".