3 ms·
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 b
by 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 agoFor 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 agoOhh, 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 agoI 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".