# Allow fractions.Fraction to return 1/6 for "0.17", "0.167", "0.1667", etc

Be default, `fractions.Fraction("0.1667")` returns `Fraction(1667, 10000)` and one would have to guess at the appropriate value for `limit_denominator(...)` in order to get that to instead be `Fraction(1, 6)`.

I propose for discussion: instead of using a default or user-specified maximum denominator, we add a option to the fractions.Fraction constructor to allow an alternative approach. If the parameter is explicitly set for the new behavior then the code assumes that the input `target` is a string representing a rounded decimal value. It infers `left` as the lowest value that `target` could have been rounded from, and `right` as the highest value that `target` could have been rounded from. By default, the subroutine then returns a Fraction that approximates `target` with low denominator, from within the half-open interval `[left, right)`. (Extra bells and whistles: whether the interval from `left` to `right` should be closed, open, or half-open the other way might be changed by changing the values of additional options `left_open` and `right_open`.)

The implementation uses a continued fraction expansion of the `left` and `right` values. These will match for a number of terms but then will have a first term where they do not match. The returned value comes from the matching part of continued fraction expansion plus a single additional term. The single additional term is chosen so that the fraction will be nearest the `target` value.

For example, “3.14” could be assumed to be rounded from any value in [3.135, 3.145). best_fraction(“3.14”) will return Fraction(22, 7) as the best fraction. In contrast, Fraction(“3.14”).limit_denominator() returns Fraction(157, 50).

So, just to be sure I understand, best_fraction(“0.1”) would return
1/6 instead of 1/10? It seems like the simplest denominator approach
will yield mostly absurd results, while the useful ones you’re
looking for would only arise from carefully-chosen decimal values
where you already know what “best” approximation you’re expecting.

I apologize that that wasn’t clear. No, `"0.1"` would not return `Fraction(1, 6)`. The continued fraction expansion of `left=0.05` is `(0; 20)` and the continued fraction expansion of `right=0.15` is `(0; 6, 1, 2)`. They agree up to only `(0;)`. So, the result will be `(0; N)` for some integer `N`. The chosen `N` will be the one that gives a value nearest to `"0.1"`, so `N=10`. That is, the returned value is `Fraction(1, 10)`.

I just fixed a typo in post 3, correcting `(1;)` and `(1; N)` to `(0;)` and `(0; N)`.

This sounds interesting, but potentially fragile (in the sense of giving results that aren’t what I’d expect). It’s the sort of thing I’d like to play with, but wouldn’t be keen on adding to the stdlib without some experience.

Is the implementation available somewhere (i.e. on PyPI)? Is the mathematical basis for the algorithm documented anywhere? (Your description is suggestive, but as someone with a fondness for continued fractions I’d be interested in the details).

1 Like

Much of the underlying math is on Wikipedia. First, Continued_fraction: Best rational within an interval gets us to look at how many terms of the continued fraction expansion of `left` and `right` match. The previous section, Continued_fraction: Best rational approximations, helps us to choose the single value to tack onto the end of the continued fraction expansion. Admittedly these Wikipedia sections could be better written. Admittedly, a primary or secondary source might be better than Wikipedia here.

Here is some code that implements the idea. Please try it out to see whether / where it does not do what you would hope.

``````from fractions import Fraction
import math
import re

def best_fraction(target, left_open=False, right_open=True):
"""

best_fraction computes a low-denominator fraction that
approximates the input `target` string.

This is much in the spirit of
fractions.Fraction.limit_denominator() but, instead of using a
default or user-specified maximum denominator, the code assumes
that the input `target` is a string representing a rounded decimal
value.  It infers `left` as the lowest value that `target` could
have been rounded from, and `right` as the highest value that
`target` could have been rounded from.  By default, the subroutine
then returns a Fraction that approximates `target` with low
denominator, from within the half-open interval [left, right).
Whether the interval from left to right should be closed, open, or
half-open the other way can be changed by changing the values of
`left_open` and `right_open`.

The implementation uses a continued fraction expansion of the
`left` and `right` values.  These will match for a number of terms
but then will have a first term where they do not match.  The
returned value comes from the matching part of continued fraction
term is chosen so that the fraction will be nearest the `target`
value.

For example, "3.14" could be assumed to be rounded from any value
in [3.135, 3.145).  best_fraction("3.14") will return Fraction(22,
7) as the best fraction.  In contrast,
Fraction("3.14").limit_denominator() returns Fraction(157, 50).
"""

# Check types of inputs
if not isinstance(target, str):
raise ValueError(f"target ({target}) must be a str")
if not isinstance(left_open, bool):
raise ValueError(
f"left_open ({left_open}) must be True or False"
)
if not isinstance(right_open, bool):
raise ValueError(
f"right_open ({right_open}) must be True or False"
)

# If supplied string is malformed, this will throw an exception
target_fraction = Fraction(target)

# If `target` is positive then we can figure the right end of the
# rounding interval by attaching a "5" suffix to the mantissa.  If
# the mantissa does not include a decimal point then append a
# decimal point before appending the "5".
right = re.sub(
r"^([+-]?[0-9_]*)(\.([0-9_]*))?([eE][+-]?[0-9_]+)?\$",
r"\g<1>.\g<3>5\g<4>",
target,
)
if right == target:
raise ValueError(
f"target ({target}) not recognized as a decimal number"
)
right_fraction = Fraction(right)

# The left side of the rounding interval is equidistant from the
# target, but on the other side.
left_fraction = 2 * target_fraction - right_fraction

# If `target` is negative, we have left and right swapped
if left_fraction > right_fraction:
(left_fraction, right_fraction) = (
right_fraction,
left_fraction,
)

# We now know the rounding interval
return best_fraction_from_interval(
target_fraction,
left_fraction,
right_fraction,
left_open,
right_open,
)

def best_fraction_from_interval(
target, left, right, left_open=False, right_open=True
):
"""

best_fraction_from_interval computes a low-denominator fraction
that approximates the input `target`; much in the spirit of
fractions.Fraction.limit_denominator().

Specifically, this subroutine assumes that `target` is a rounded
decimal value, `left` is the lowest value that `target` could have
been rounded from, and `right` is the highest value that `target`
could have been rounded from.  By default, the subroutine then
returns a Fraction that approximates `target` with low
denominator, from within the half-open interval [left, right).
Whether the interval from left to right should be closed, open, or
half-open the other way can be changed by changing the values of
`left_open` and `right_open`.

The implementation uses a continued fraction expansion of the
`left` and `right` values.  These will match for a number of terms
but then will have a first term where they do not match.  The
returned value comes from the matching part of continued fraction
term is chosen so that the fraction will be nearest the `target`
value.

For example, "3.14" could be assumed to be rounded from any value
in [3.135, 3.145).  best_fraction_from_interval(Fraction("3.14"),
Fraction("3.135"), Fraction("3.145")) will return Fraction(22, 7)
as the best fraction.
"""

# Check types of inputs
if not isinstance(target, Fraction):
raise ValueError(
f"target value ({target}) must be a Fraction"
)
if not isinstance(left, Fraction):
raise ValueError(f"left value ({left}) must be a Fraction")
if not isinstance(right, Fraction):
raise ValueError(f"right value ({right}) must be a Fraction")
if not target > left:
raise ValueError(
f"target value ({target}) must be greater than left value ({left})"
)
if not target < right:
raise ValueError(
f"target value ({target}) must be less than right value ({right})"
)
if not isinstance(left_open, bool):
raise ValueError(
f"left_open ({left_open}) must be True or False"
)
if not isinstance(right_open, bool):
raise ValueError(
f"right_open ({right_open}) must be True or False"
)

# Define useful helper function
def update_fraction(endpoint, endpoint_plus, endpoint_floor):
endpoint = (
1 / (endpoint - endpoint_floor)
if endpoint != endpoint_floor
else math.inf
)
endpoint_plus = not endpoint_plus
endpoint_floor = (
math.inf
if endpoint == math.inf
else math.floor(endpoint)
if endpoint_plus
else math.ceil(endpoint) - 1
)
return (endpoint, endpoint_plus, endpoint_floor)

# Is each endpoint effectively plus epsilon (as opposed to minus
# epsilon)?
left_plus = left_open
right_plus = not right_open

# To get to the next iteration of the continued fraction
# expansion, we need to know the floor of each endpoint.  Note
# that an exact integer has a "floor" that depends upon whether
# our value is implicitly +epsilon or -epsilon.
left_floor = (
math.floor(left) if left_plus else math.ceil(left) - 1
)
right_floor = (
math.floor(right) if right_plus else math.ceil(right) - 1
)

# The start up convergents for a continued fraction expansion
(prev_numer, prev_denom) = (0, 1)
(curr_numer, curr_denom) = (1, 0)

while left_floor == right_floor:
# Compute one more convergent and retain one previous
# convergent
(curr_numer, prev_numer) = (
left_floor * curr_numer + prev_numer,
curr_numer,
)
(curr_denom, prev_denom) = (
left_floor * curr_denom + prev_denom,
curr_denom,
)

# Update the values so that we can compute the next
# convergents
(left, left_plus, left_floor) = update_fraction(
left, left_plus, left_floor
)
(right, right_plus, right_floor) = update_fraction(
right, right_plus, right_floor
)

# We know the continued fraction so far, but we have reached the
# point where the continued fraction expanion for `left` and
# `right` are no longer the same.  We need to choose the last term
# within the interval and nearest the target.  In the general case
# there will be a nearest to the left and a nearest to the right.
best_floor_unrounded = Fraction(
prev_numer * target.denominator
- prev_denom * target.numerator,
curr_denom * target.numerator
- curr_numer * target.denominator,
)
best_floor_left = max(
math.floor(best_floor_unrounded),
min(left_floor, right_floor) + 1,
)
best_floor_right = min(
math.ceil(best_floor_unrounded), max(left_floor, right_floor)
)
best_floor_left * curr_numer + prev_numer,
best_floor_left * curr_denom + prev_denom,
)
best_floor_right * curr_numer + prev_numer,
best_floor_right * curr_denom + prev_denom,
)

``````

I posted a code snippet, but a bot has asked for a staff member to review it before it is shown. I apologize for the delay.

1 Like

It’s still unclear to me how you determine the trade-off between
proximity and simplicity. Sure 1/10 is closer to 0.1 than 1/9 is,
but 1/9 has a smaller denominator than 1/10 while still being more
than twice as close as 1/8 (and that has a still smaller
denominator). Similarly, 11/20 is closest to 0.55 but 5/9 is
“simpler.”

It seems like what you want is some minimal rational representation
of repeating decimals and irrational numbers which have been rounded
to a terminating decimal approximation. However, for every
terminating decimal there is always a single irreducible fraction
which will be infinitely closest to it. For 1.6 would you choose 8/5
(closest) or 5/3 (simpler), and why?

There’s a (literally) infinite number of possible fractions any
decimal could have been rounded from. Denominators aside, how would
you even know which numerator to pick?

@fungi thank you for the questions. The trade off between accuracy and the size of the denominator is chosen based upon the continued fraction expansion. See the description above, and the code snippet (once it is made available).

“0.1” → 1/10.
“0.55” → 6/11 = 0.545454… (Note that 5/9 rounded to two digits would be “0.56” instead.)
“1.6” → 8/5. (Note that 5/3 rounded to two digits would be “1.7” instead.)

Similar math is present in Wikipedia’s Continued fraction: Best rational within an interval. That section demonstrates comparing the terms of the continued fraction expansion for the `left` and `right` interval boundaries, and discusses that the interesting point is where the expansions start to disagree. The previous section of that Wikipedia article talks about how to choose one more term of the expansion in order to get a good approximation to the target value.

Trying again to get the Akismet bot to let me post this code snippet

``````from fractions import Fraction
import math
import re

def best_fraction(target, left_open=False, right_open=True):
"""

best_fraction computes a low-denominator fraction that
approximates the input `target` string.

This is much in the spirit of
fractions.Fraction.limit_denominator() but, instead of using a
default or user-specified maximum denominator, the code assumes
that the input `target` is a string representing a rounded decimal
value.  It infers `left` as the lowest value that `target` could
have been rounded from, and `right` as the highest value that
`target` could have been rounded from.  By default, the subroutine
then returns a Fraction that approximates `target` with low
denominator, from within the half-open interval [left, right).
Whether the interval from left to right should be closed, open, or
half-open the other way can be changed by changing the values of
`left_open` and `right_open`.

The implementation uses a continued fraction expansion of the
`left` and `right` values.  These will match for a number of terms
but then will have a first term where they do not match.  The
returned value comes from the matching part of continued fraction
term is chosen so that the fraction will be nearest the `target`
value.

For example, "3.14" could be assumed to be rounded from any value
in [3.135, 3.145).  best_fraction("3.14") will return Fraction(22,
7) as the best fraction.  In contrast,
Fraction("3.14").limit_denominator() returns Fraction(157, 50).
"""

# Check types of inputs
if not isinstance(target, str):
raise ValueError(f"target ({target}) must be a str")
if not isinstance(left_open, bool):
raise ValueError(
f"left_open ({left_open}) must be True or False"
)
if not isinstance(right_open, bool):
raise ValueError(
f"right_open ({right_open}) must be True or False"
)

# If supplied string is malformed, this will throw an exception
target_fraction = Fraction(target)

# If `target` is positive then we can figure the right end of the
# rounding interval by attaching a "5" suffix to the mantissa.  If
# the mantissa does not include a decimal point then append a
# decimal point before appending the "5".
right = re.sub(
r"^([+-]?[0-9_]*)(\.([0-9_]*))?([eE][+-]?[0-9_]+)?\$",
r"\g<1>.\g<3>5\g<4>",
target,
)
if right == target:
raise ValueError(
f"target ({target}) not recognized as a decimal number"
)
right_fraction = Fraction(right)

# The left side of the rounding interval is equidistant from the
# target, but on the other side.
left_fraction = 2 * target_fraction - right_fraction

# If `target` is negative, we have left and right swapped
if left_fraction > right_fraction:
(left_fraction, right_fraction) = (
right_fraction,
left_fraction,
)

# We now know the rounding interval
return best_fraction_from_interval(
target_fraction,
left_fraction,
right_fraction,
left_open,
right_open,
)

def best_fraction_from_interval(
target, left, right, left_open=False, right_open=True
):
"""

best_fraction_from_interval computes a low-denominator fraction
that approximates the input `target`; much in the spirit of
fractions.Fraction.limit_denominator().

Specifically, this subroutine assumes that `target` is a rounded
decimal value, `left` is the lowest value that `target` could have
been rounded from, and `right` is the highest value that `target`
could have been rounded from.  By default, the subroutine then
returns a Fraction that approximates `target` with low
denominator, from within the half-open interval [left, right).
Whether the interval from left to right should be closed, open, or
half-open the other way can be changed by changing the values of
`left_open` and `right_open`.

The implementation uses a continued fraction expansion of the
`left` and `right` values.  These will match for a number of terms
but then will have a first term where they do not match.  The
returned value comes from the matching part of continued fraction
term is chosen so that the fraction will be nearest the `target`
value.

For example, "3.14" could be assumed to be rounded from any value
in [3.135, 3.145).  best_fraction_from_interval(Fraction("3.14"),
Fraction("3.135"), Fraction("3.145")) will return Fraction(22, 7)
as the best fraction.
"""

# Check types of inputs
if not isinstance(target, Fraction):
raise ValueError(
f"target value ({target}) must be a Fraction"
)
if not isinstance(left, Fraction):
raise ValueError(f"left value ({left}) must be a Fraction")
if not isinstance(right, Fraction):
raise ValueError(f"right value ({right}) must be a Fraction")
if not target > left:
raise ValueError(
f"target value ({target}) must be greater than left value ({left})"
)
if not target < right:
raise ValueError(
f"target value ({target}) must be less than right value ({right})"
)
if not isinstance(left_open, bool):
raise ValueError(
f"left_open ({left_open}) must be True or False"
)
if not isinstance(right_open, bool):
raise ValueError(
f"right_open ({right_open}) must be True or False"
)

# Define useful helper function
def update_fraction(endpoint, endpoint_plus, endpoint_floor):
endpoint = (
1 / (endpoint - endpoint_floor)
if endpoint != endpoint_floor
else math.inf
)
endpoint_plus = not endpoint_plus
endpoint_floor = (
math.inf
if endpoint == math.inf
else math.floor(endpoint)
if endpoint_plus
else math.ceil(endpoint) - 1
)
return (endpoint, endpoint_plus, endpoint_floor)

# Is each endpoint effectively plus epsilon (as opposed to minus
# epsilon)?
left_plus = left_open
right_plus = not right_open

# To get to the next iteration of the continued fraction
# expansion, we need to know the floor of each endpoint.  Note
# that an exact integer has a "floor" that depends upon whether
# our value is implicitly +epsilon or -epsilon.
left_floor = (
math.floor(left) if left_plus else math.ceil(left) - 1
)
right_floor = (
math.floor(right) if right_plus else math.ceil(right) - 1
)

# The start up convergents for a continued fraction expansion
(prev_numer, prev_denom) = (0, 1)
(curr_numer, curr_denom) = (1, 0)

while left_floor == right_floor:
# Compute one more convergent and retain one previous
# convergent
(curr_numer, prev_numer) = (
left_floor * curr_numer + prev_numer,
curr_numer,
)
(curr_denom, prev_denom) = (
left_floor * curr_denom + prev_denom,
curr_denom,
)

# Update the values so that we can compute the next
# convergents
(left, left_plus, left_floor) = update_fraction(
left, left_plus, left_floor
)
(right, right_plus, right_floor) = update_fraction(
right, right_plus, right_floor
)

# We know the continued fraction so far, but we have reached the
# point where the continued fraction expanion for `left` and
# `right` are no longer the same.  We need to choose the last term
# within the interval and nearest the target.  In the general case
# there will be a nearest to the left and a nearest to the right.
best_floor_unrounded = Fraction(
prev_numer * target.denominator
- prev_denom * target.numerator,
curr_denom * target.numerator
- curr_numer * target.denominator,
)
best_floor_left = max(
math.floor(best_floor_unrounded),
min(left_floor, right_floor) + 1,
)
best_floor_right = min(
math.ceil(best_floor_unrounded), max(left_floor, right_floor)
)
best_floor_left * curr_numer + prev_numer,
best_floor_left * curr_denom + prev_denom,
)
best_floor_right * curr_numer + prev_numer,
best_floor_right * curr_denom + prev_denom,
)

``````

FWIW, there’s an efficient implementation of “simplest rational within an interval” here: simplefractions · PyPI

The Haskell standard library also has something along these lines: Data.Ratio

Those are both for the well-defined problem of finding the simplest fraction within an interval (small print: non-empty interval that already contains at least one fraction), though; what Lee is looking for is something more nuanced.

`simplefractions` is great in situtions where having the smallest denominator is more important than accuracy.

If you get a chance to try the code snippet and find a situation where `best_fraction(your_rounded_decimal_as_a_string)` does not return what you were hoping would happen for that rounded decimal, please let me know.

Thanks for the details! My uni days as a math theory major seem like
a lifetime away now, and I appear to have completely repressed all
memories of my numerical analysis courses, so didn’t even catch that
Continued Fraction Expansion was what I should have been searching

Looking around quickly, I find there are already a lot of articles
with example implementations in Python, applying a variety of
optimizations. It’s indeed useful for finding precise fractional
representations of infinitely repeating decimals which, while of
course an infinitesimal part of the real numbers, are still a very
interesting subset. I guess if the author knows what they want in a
particular instance will be better represented by this, then it
could be useful (even if inexact for many other situations).

The bigger question is, are program authors likely to need that
often enough that reimplementing it themselves or reusing an
available third-party module is a burden?

OK, that was fairly easy. “0.15” returns 2/13, when I’d expect 3/20. And worse still, “0.150” returns 3/20. I understand that the trailing zeroes signify the rounding accuracy, but even so, this seems wrong when 3/20 is exact. The same issue arises with “0.3” (expected 3/10, got 1/3) and 0.7 (expected 7/10, got 2/3).

Honestly, I think part of the problem is that what’s “best” is both subjective and dependent on the specific value.

I find it hard to understand exactly the use case for the proposal as stated but I can think of a common situation where something similar is wanted which is when converting a `float` to a `Fraction` but wanting to “undo” the rounding error e.g.:

``````In : fractions.Fraction(1/3)
Out: Fraction(6004799503160661, 18014398509481984)
``````

In SymPy there is a function `nsimplify` for this case so that you can do e.g.:

``````In : from sympy import nsimplify

In : n = 1/3

In : n
Out: 0.3333333333333333

In : nsimplify(n)
Out: 1/3
``````

The `nsimplify` function goes way beyond what could be wanted here though because e.g.:

``````In : from math import sqrt

In : e = 1 + sqrt(2)

In : e
Out: 2.414213562373095

In : nsimplify(e)
Out: 1 + √2
``````

I do think it would be useful to have a way of getting a float that should represent a simple rational number into a Fraction though. The obvious approach to this would be something based on continued fractions e.g. in this case you have:

``````In : from sympy import continued_fraction, Rational

In : n = Rational(1/3)

In : n
Out:
6004799503160661
─────────────────
18014398509481984

In : continued_fraction(n)
Out: [0, 3, 6004799503160661]
``````

Since the rounding error can be expected to be around 1 part in `2**53` it’s no surprise that the “erroneous” part of the continued fraction expansion is a number around that size. The idea is to have a heuristic threshold such that that term of the expansion is considered to be infinite and then the result is

``````0 + 1/(3 + 1/oo)) = 1/3
``````

To a human eye it’s obvious where the expansion goes wrong e.g.:

``````In : continued_fraction(Rational(1/7))
Out: [0, 7, 2573485501354569]

In : continued_fraction(Rational(311/11))
Out: [28, 3, 1, 1, 1, 12794317123211]
``````

I’m just not sure how you can reasonably choose the threshold. Probably the threshold should get smaller as you get further through the expansion but I haven’t thought too hard about it.

“0.15” returns 2/13, when I’d expect 3/20. And worse still, “0.150” returns 3/20.

I would expect `"0.15" -> 2/13` and `"0.150" -> 3/20` and `"0.3" -> 1/3` and `"0.7" -> 2/3`. In particular, in a situation where something is reported to the nearest tenth, my first assumption for “0.7” would be that it comes from 2/3.

Perhaps the fault lies in how I have described what is getting computed … and that better clarity there would put us back on the same page?

I am tempted to describe this function as something along the lines of “Sometimes a fraction will be presented as a decimal rounded to some number of digits. If the rounded decimal number has enough digits then `best_fraction` will recover the original fraction.”

Unfortunately, that is kind of a weaselly way of saying that if `best_fraction` didn’t give you what you want then it is your fault for not supplying enough digits. I find this weaselly approach to be less than satisfying … so back to the drawing board on how to word this. If anyone has better ideas …

No, I understand how what you describe matches to what’s getting produced, I just don’t see it as something I’d want in practice. The 0.3 and 0.7 cases are particularly jarring, as 3/10 and 7/10 are exact, and are sufficiently simple that I’d assume they are what the user meant. If the user had been after 1/3, IMO they would have entered 0.33333 (with some number of 3’s greater than 1).

I guess the question is, where are you expecting these input values to come from, and why do they need to be converted to fractions, rather than to Decimal or Float? I’m assuming that they would be useful in a situation where you want to do exact fractional calculations, but accept user input as “numbers” in a general sense. So you’re trying to infer “what the user meant” by a decimal. And I can’t imagine anyone entering a number with 1 decimal place and meaning anything other than the exact fraction n/10. With 2 or more decimals, I can imagine the imput being an approximation (.66 for 66% meaning 2/3, for example) but not for a single decimal place.

So overall, I think this code would be a nice PyPI library (where it can fit in its well-defined niche without needing to satisfy the sort of broad applicability expectations that a stdlib function does) but I doubt it’s a good fit for the stdlib.

@pf_moore Where I would do the opposite, I believe that you are saying that in each of the following you would value the first term differently from the others:
0.3, 0.33, 0.333, 0.3333
0.7, 0.67, 0.667, 0.6667

Do you think the same of?:
5.3, 5.33, 5.333, 5.3333
1000.3, 1000.33, 1000.333, 1000.3333

Sorry if that is a needling question – I am trying to understand your view. If there is a better question I should have asked, please answer that instead.