HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Efficiently finding approximate fraction, with tolerance for fp rounding

Submitted by: @import:stackexchange-codereview··
0
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:

>>> (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

Solution

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.

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.