Allow Fractions to return 1/6 for "0.17", "0.167", "0.1667", etc.

[cc8f830a-c37e-4d94-953a-fef1e98763c9]

BPO	46780
Nosy	@rhettinger, @mdickinson, @zware, @serhiy-storchaka, @Leengit
Files	best_fraction.py: Python code to find the best fraction in a specified interval

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields: ```python assignee = None closed_at = created_at = labels = ['type-feature', 'library', '3.11'] title = 'Allow Fractions to return 1/6 for "0.17", "0.167", "0.1667", etc.' updated_at = user = 'https://github.com/Leengit' ``` bugs.python.org fields: ```python activity = actor = 'Leengit' assignee = 'none' closed = True closed_date = closer = 'mark.dickinson' components = ['Library (Lib)'] creation = creator = 'Leengit' dependencies = [] files = ['50627'] hgrepos = [] issue_num = 46780 keywords = [] message_count = 27.0 messages = ['413418', '413419', '413420', '413423', '413426', '413427', '413430', '413433', '413434', '413435', '413436', '413437', '413439', '413440', '413441', '413442', '413443', '413453', '413455', '413459', '413463', '413471', '413482', '413483', '413487', '413488', '413492'] nosy_count = 5.0 nosy_names = ['rhettinger', 'mark.dickinson', 'zach.ware', 'serhiy.storchaka', 'Leengit'] pr_nums = [] priority = 'normal' resolution = 'rejected' stage = 'resolved' status = 'closed' superseder = None type = 'enhancement' url = 'https://bugs.python.org/issue46780' versions = ['Python 3.11'] ```

[cc8f830a-c37e-4d94-953a-fef1e98763c9]

For example, a string such as "0.167" could be rounded from anything in [0.1665, 0.1675). Within that interval, the fraction with the lowest numerator and denominator is 1/6.

Here it is proposed that we add a new flag to the Fractions constructor, perhaps called _assume_rounded, which defaults to False and then yields no change from current behavior. However, when it is True, the constructed Fraction first computes the range of the values that the input string could have been rounded from, and then computes the fraction in that half-open interval with the lowest numerator and denominator. This is described at https://en.wikipedia.org/wiki/Continued_fraction#Best_rational_within_an_interval, which uses continued fractions to arrive at the answer.

For extra bells and whistles, we'd support strings like "0x0.2AAB" which is hexadecimal for 1/6 rounded to that many places. In this case, we'd find 1/6 as the fraction with lowest numerator and denominator in the interval [0x0.2AAA8, 0x0.2AAB8). Likewise for binary, octal, and any other formats supported by Python.

[zware]

This sounds interesting, but also rather similar to what the limit_denominator method can get you. Can you provide examples that can't be handled nicely by limit_denominator to strengthen your case?

[serhiy-storchaka]

It would return 1/7 for "0.1" and 1/4 for "0.2". Is it what you expected?

[mdickinson]

the constructed Fraction first computes the range of the values that the input string could have been rounded from

There's too much magic and guesswork here for my liking; I don't really see this as feasible. Moreover, depending on which rounding mode was used (round-ties-to-even, round-ties-to-away), the interval may be half-open, open or closed.

For another problematic example, suppose the string supplied is "0.10". How are we to guess whether this was the result of rounding to two decimal places after the point (in which case the interval we need is [0.095, 0.105]), or whether it's the result of rounding to two significant figures (in which case the interval we need is [0.095, 0.15])?

and then computes the fraction in that half-open interval with the lowest numerator and denominator

This part, however, is well-defined and can be done efficiently. You may be interested in the "simplefractions" module on PyPI, which solves the exact task "find the simplest fraction in a given interval".

[mdickinson]

in which case the interval we need is [0.095, 0.15]

Whoops, sorry; brain fail. If we're rounding to two sig figs, the next representable value up from 0.01 is 0.011, while the next one down is 0.099, so the interval we'd be interested in would be [0.0995, 0.105].

[mdickinson]

Sigh:

the next representable value up from 0.01 is 0.011

should say:

the next representable value up from 0.10 is 0.11

I think I'll duck out and give my brain a rest before commenting further.

[cc8f830a-c37e-4d94-953a-fef1e98763c9]

This sounds interesting, but also rather similar to what the limit_denominator method can get you.

Fractions("0.17").limit_denominator() and Fractions("0.17").limit_denominator(n) for n > 28 do not give 1/6. So, I'd have to guess at n until I get 1/6. Instead, I'd like to have the digits actually presented "0.17" determine the interval [0.165, 0.175) which then determines the fraction.

In particular, "0.170" would give a different answer ... a fraction within [0.1695, 0.1705).

[cc8f830a-c37e-4d94-953a-fef1e98763c9]

It would return 1/7 for "0.1" and 1/4 for "0.2". Is it what you expected?

Yes. Or putting it another way, if that's not the right answer then whoever rounded the number should have retained more digits.

[cc8f830a-c37e-4d94-953a-fef1e98763c9]

depending on which rounding mode was used (round-ties-to-even, round-ties-to-away), the interval may be half-open, open or closed.

I think we will get the majority of the use cases if we pick one rounding strategy and stick with it. In later version we could support more if we found the demand: in addition to assume_rounded=True we could allow assume_rounded="round_towards_zero", etc.

[cc8f830a-c37e-4d94-953a-fef1e98763c9]

For another problematic example, suppose the string supplied is "0.10"

We would treat "0.1", "0.10", "0.100", etc. all differently. In all cases we would assume rounding to compute the last digit. Similarly for "3e-10", "3.0e-10" == "30e-11", "3.00e-11", etc.

[mdickinson]

One more example: what interval is implied by an input string of "1600"? Is it (1550, 1650)? Or (1595, 1605)? Or even (1599.5, 1600.5).

Sorry, I just don't see this working - there are two many arbitrary choices involved in guessing what interval the user intended. Much better to require the user to give that interval directly.

[cc8f830a-c37e-4d94-953a-fef1e98763c9]

You may be interested in the "simplefractions" module on PyPI, which solves the exact task "find the simplest fraction in a given interval".

I haven't seen that code and I am interested; I will take a look. Perhaps code from there can be imported / incorporated in our implementation here.

[cc8f830a-c37e-4d94-953a-fef1e98763c9]

One more example: what interval is implied by an input string of "1600"? Is it (1550, 1650)? Or (1595, 1605)? Or even (1599.5, 1600.5).

The rule would be to look at the last digit supplied and assume that the rounding is there. So "1600" gives [1599.5, 1600.5) and "16e2" gives [1550, 1650).

[cc8f830a-c37e-4d94-953a-fef1e98763c9]

The example of "16e2" would yield the interval [1550, 1650). The smallest denominator possible is 1. The smallest numerator that works with that denominator is 1550, but I don't like 1550/1 as the answer.

To cover these edge cases, I'd modify the optimization to be that we continue to seek the smallest denominator, but in the case that multiple numerators would give ratios within the computed interval then we choose the numerator among these that gives the ratio closest to the input value.

[cc8f830a-c37e-4d94-953a-fef1e98763c9]

It would return 1/7 for "0.1" and 1/4 for "0.2". Is it what you expected?

I answered "yes" before, but I am now thinking "no". In the case of "0.1", the smallest numerator achievable is 1, but there are multiple denominators that would give a value within [0.05, 0.15). So, I'd choose the denominator that gives the ratio that is closet to the input value.

This is similar to the "16e2" example but with the roles of numerator and denominator reversed.

[mdickinson]

I'd modify the optimization to be that we continue to seek the smallest denominator, but in the case that multiple numerators would give ratios within the computed interval then we choose the numerator among these that gives the ratio closest to the input value.

Hmm. This is getting more DWIM-like (Do What I Mean) by the minute. :-)

What about for an input of "0.001"? Your current specification would give 1/667, but I'm betting that you'd actually prefer 1/1000.

[cc8f830a-c37e-4d94-953a-fef1e98763c9]

What about for an input of "0.001"? Your current specification would give 1/667, but I'm betting that you'd actually prefer 1/1000.

You would win that bet.

[rhettinger]

I don't think the standard library should go down this path.

Mark's disinclinations all make sense to me, but I'm also concerned that the API would be almost unusable in practical situations. Users would tend to know their input fraction and that they have a desire for "simplification", but it would be challenging for them to come with a surrounding interval that made sense. We could attempt to infer an interval from the input, but a user is likely to have a poorly specified idea of what they actually want. The operating principle here is, "refuse the temptation to guess".

Here's a little exercise for the API. The 12 semitones in an octave are separated by a frequency ratio of 2(1/12). For example, if A is 440 Hz, then A# is 440*2(1/12) = 466.16 Hz. Note pairs sound the most harmonious when the ratio of their frequencies is a "near" a small fraction. Determine the small fraction for each of the twelve notes. For example, a perfect fifth has the frequency ratio of 2**(7/12) -> 1.498307 — it it "perfect" because it "close-enough" to the small integer ratio of 3 : 2. Notice the vague requirements of "near", "close-enough" and "small integer ratio".

[rhettinger]

Also note for the music example that the notion of "near enough" isn't equidistant about the "simple fraction". The sense of nearness is logarithmic and is measured in "cents" which are hundredths of an equal-tempered semitone (i.e a one octave consists of 1200 cents).

[cc8f830a-c37e-4d94-953a-fef1e98763c9]

The 12 semitones in an octave are separated ...

Right, this functionality would not solve the semitones / cents problem. Nor will it achieve world peace. But if it solves enough use cases then it is worth discussing, yes?

I haven't written the string parsing, but once we know that "0.001" means to look in [0.0005, 0.0015) then we can invoke the attached as best_fraction(Fraction("0.001"), Fraction("0.0005"), Fraction("0.0015")) to get the output Fraction(1, 1000).

[rhettinger]

Nor will it achieve world peace.

Please watch the tone. It is borderline abusive and dismissive.

we can invoke the attached as best_fraction(Fraction("0.001"), Fraction("0.0005"), Fraction("0.0015")) to get the output Fraction(1, 1000).

-1 I am solidly against this. The other inputs to Fraction() are exact conversions. The proposal works against a core concept behind the fraction module.

Also, my expectation for Fraction("0.0015") would be to give Fraction(3, 2000), the same as would be given by Fraction(Decimal("0.0015")).

But if it solves enough use cases then it is worth discussing, yes?

Perhaps this tracker issue should be closed and moved to python-ideas. The notions are currently too immature to warrant more core developer time.

Also, it would be nice to have research into what other languages and libraries do for fractional approximations of decimal strings.

[mdickinson]

Okay, let's close here; as Raymond says, that doesn't prevent further discussion on python-ideas.

The notions are currently too immature to warrant more core developer time.

Agreed. It seems that what Lee wants is some kind of blend between the simplest fraction and the closest fraction, and it's not clear exactly how that blend would work.

[cc8f830a-c37e-4d94-953a-fef1e98763c9]

Please watch the tone. It is borderline abusive and dismissive.

I apologize for the adverse impact there. I will be more careful.

Also, my expectation for Fraction("0.0015") would be to give Fraction(3, 2000), the same as would be given by Fraction(Decimal("0.0015")).

Yes, 0.0015 would be 3/2000. However, in my example "0.0015" is the right endpoint of [0.0005, 0.0015), not the value "0.001" that we are seeking the fraction for.

Perhaps this tracker issue should be closed and moved to python-ideas. The notions are currently too immature to warrant more core developer time.

You have more experience with this than I. I defer to you.

Agreed. It seems that what Lee wants is some kind of blend between the simplest fraction and the closest fraction, and it's not clear exactly how that blend would work.

Drat. I gave the code example in order to make that clear. I guess we can continue to discuss this at "python-ideas". My quick web search for that turns up a lot of things. If you could give me a lead -- is there a web URL for that, is it an e-mail list, etc.?

Thank you all for your valuable comments.

[cc8f830a-c37e-4d94-953a-fef1e98763c9]

In case there are others who are unsure about "python-ideas" ... I believe the discussion page https://discuss.python.org/c/ideas is what was meant.

[mdickinson]

Re python-ideas: there's a mailing list:

https://mail.python.org/archives/list/python-ideas@python.org/

But the https://discuss.python.org/c/ideas/ category also works for this.

[mdickinson]

I gave the code example in order to make that clear.

Yep, that didn't help: reverse engineering the intended behaviour from a complicated piece of code isn't easy. An up-front description of the intended behaviour would be better.

[cc8f830a-c37e-4d94-953a-fef1e98763c9]

I have started a discussion at https://discuss.python.org/t/allow-fractions-fraction-to-return-1-6-for-0-17-0-167-0-1667-etc . Your feedback there would be much appreciated.