Efficiently finding approximate fraction, with tolerance for fp rounding

I needed to convert floating point numbers to int/int fractions. Python technically has this functionality, but has issues with rounding errors:

>>> (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 += 1

• You do realize that 0.1+0.2 is actually 0.30000000000000004, right? Which happens to be exactly 1351079888211149 / 4503599627370496, so it's your function which has issues with rounding errors. Unless I misunderstood your question. In either case, your function returns the wrong result for 0.1+0.2 with accuracy 0.0000000000000001. With finer accuracy, it doesn't even return a result (in a reasonable time). – kyrill Apr 3 '17 at 21:42
• @kyrill yes, I know that 0.1+0.2 != 0.3, the problem is that my program receives 0.30000000000000004 as input and needs to read it as 0.3 (rounding errors add up over time, causing problems), but fractions such as 1/7 prevent me from simply using round(x) – Mirac7 Apr 3 '17 at 22:07
• You're making some assumptions here. How exactly does your program know that the input is actually supposed to be 0.3? But I agree that this function will hopefully in most cases reduce rounding errors, if the user of that function is aware of the implications. – kyrill Apr 3 '17 at 22:10
• @kyrill any valid input should be representable as n/d, where d has up to 5 digits. I checked and 1/d is calculated correctly for all d < 100000 given small enough accuracy. I believe that for other numerators it should also work correctly? – Mirac7 Apr 3 '17 at 22:26
• I can't say. I can just advise you to test the results of the built-in as_integer_ratio versus your function, and choose the one which better fits your needs – the one which gives better overall results for your application. – kyrill Apr 3 '17 at 22:35

Convert 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.