patternpythonMinor
Efficiently finding approximate fraction, with tolerance for fp rounding
Viewed 0 times
efficientlyapproximatewithfindingfortolerancefractionrounding
Problem
I needed to convert floating point numbers to int/int fractions. Python technically has this functionality, but has issues with rounding errors:
This is what I wrote and I was wondering whether it could be further improved for performance?
>>> (0.1+0.2).as_integer_ratio()
(1351079888211149, 4503599627370496)This is what I wrote and I was wondering whether it could be further improved for performance?
def as_fraction(number: float, accuracy: float) -> (int, int):
whole, x = divmod(number, 1)
if not x:
return int(whole), 1
n = 1
while True:
d = int(n/x)
if n/d-x < accuracy:
return int(whole)*d+n, d
d += 1
if x-n/d < accuracy:
return int(whole)*d+n, d
n += 1Solution
Convert the
(this gives you the same ratio as
If you're interested in the maths behind the
float to a Fraction:>>> from fractions import Fraction
>>> Fraction(0.1 + 0.2)
Fraction(1351079888211149, 4503599627370496)(this gives you the same ratio as
float.as_integer_ratio), and then use the limit_denominator method to return the closest fraction with a denominator of limited size:>>> Fraction(0.1 + 0.2).limit_denominator(1000000)
Fraction(3, 10)If you're interested in the maths behind the
limit_denominator method, see this answer on Stack Overflow.Code Snippets
>>> from fractions import Fraction
>>> Fraction(0.1 + 0.2)
Fraction(1351079888211149, 4503599627370496)>>> Fraction(0.1 + 0.2).limit_denominator(1000000)
Fraction(3, 10)Context
StackExchange Code Review Q#159758, answer score: 4
Revisions (0)
No revisions yet.