classification
Title: make it simpler to round fractions
Type: enhancement Stage:
Components: Library (Lib) Versions: Python 3.7
process
Status: open Resolution:
Dependencies: Superseder:
Assigned To: Nosy List: belopolsky, facundobatista, mark.dickinson, rhettinger, serhiy.storchaka, skrah, stutzbach, wolma
Priority: normal Keywords: patch

Created on 2017-11-08 10:13 by wolma, last changed 2017-11-09 08:45 by wolma.

Files
File name Uploaded Description Edit
fractions_divround.patch wolma, 2017-11-08 10:13 review
Messages (11)
msg305817 - (view) Author: Wolfgang Maier (wolma) * Date: 2017-11-08 10:13
Hi,

because of floating point inaccuracies it is suboptimal to use round(int1/int2) for rounding of a fraction.
fractions.Fraction, OTOH, offers exact rounding through its implementation of __round__, but using it requires users to create a fractions.Fraction instance from two ints first.
The algorithm used by Fraction.__round__ is, essentially, the same as the one used in the pure-Python version of the datetime._divide_and_round module (which, in turn, is taken from a comment by Mark Dickinson in Objects/longobject.c).

My suggestion is to promote this algorithm to an exposed function in the fractions module (actually, it may make sense to have it in the math module instead - compare the case of the gcd function, which started out in fractions, but is now in transition to math) so that it can be used by Fraction.__round__, but also any other code.

Attached is a patch demonstrating the idea. In addition, to the above benefit, it turns out to actually speed up Fraction.__round__ substantially, when ndigits is not None because it then avoids the generation of temporary Fraction instances, and, in my hands at least, it even makes the general (ndigits=None) case slightly faster (apparently the copied datetime._divide_and_round code is more efficient than the original in Fraction.__round__).

There is one slight additional tweak in the patch: in the case of ndigits < 0, it returns an int, not a Fraction (see test_fractions modification to make it pass).
I think this is actually a mistake in the current Fraction.__round__, which already promotes the result to int in the general case. This change speeds up round to the next ndigits power of ten by ~ a factor of 5 in my hands because no new Fraction needs to be instantiated anymore.

A full PR could include having pure-Python datetime import the function from fractions instead of rolling its own, but I'd first like to hear whether you think this should go into math instead.
msg305818 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-11-08 10:37
See also _divide_and_round() in Lib/datetime.py, _div_nearest() in Lib/_pydecimal.py and _PyLong_DivmodNear() in Objects/longobject.c.
msg305843 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2017-11-08 13:56
> There is one slight additional tweak in the patch: in the case of ndigits < 0, it returns an int, not a Fraction (see test_fractions modification to make it pass).

This would be a backwards incompatible change, potentially breaking existing code, so we'd need to think carefully before making it. It's definitely not a "slight tweak" :-).

I'd prefer that this change is not made at all: in general, it's not a great idea to have a return _type_ that changes depending on the _values_ of an argument (though as always, there are exceptions). The general rule is that two-argument `round` returns something of the same type as its first argument: I don't think there's a really compelling reason to change this for the Fraction type. So -1 on this change from me.
msg305844 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2017-11-08 14:04
On the main proposal: rounding an integer division to the nearest integer does seem to be a somewhat common need, and one that's not entirely trivial to code up and get right first time. (Unlike floor or ceiling of a quotient, which can be simply spelled as `n // d` or `-(-n // d)` respectively.) As Serhiy points out, it already turns up in multiple guises in the C source. The questions for me would be:

1. Is it actually a common enough need that we should add it?
2. If answer to (1) is yes, where should we add it? A method on the `int` type is one possible option, beyond the ones already mentioned.
3. There are actually three related operations here: (a) round a quotient to the nearest integer; (b) get the remainder of that rounding (the integer version of math.remainder), and (c) both (a) and (b) together. Which of those three should be implemented? (i.e., do we want the round-to-nearest analogs of div, mod, divmod, all three, or some nontrivial subset)?
msg305846 - (view) Author: Wolfgang Maier (wolma) * Date: 2017-11-08 14:08
ok, I agree with you that the returned type should not change with the value of an argument. I simply didn't think one vs two argument versions here, but in terms of three different code branches where one returns int already.
Maybe 'slight' was the wrong wording - think of it as 'easy to revert' then :)
msg305851 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-11-08 14:36
I thought about adding a public function in the math module when worked on one of that functions. But there are not many cases for it in the stdlib (datetime, fractions, decimal, and maybe it's all). I don't know whether there is a common enough need in third-party code. But there is a parallel with math.remainder().

If add this function, I would implement it in C and add in the math module. It already contains integer specific functions factorial() and gcd(). There was a proposition to add as_integer_ratio() (which will work with arbitrary rationals). All together they will create a small integer mathematics domain in the math module. Or can be extracted in a special module. Later it can be extended by adding functions for binomial coefficients and the number of permutations and generators of prime and Fibonacci numbers.
msg305879 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2017-11-08 16:37
> I don't know whether there is a common enough need in third-party code.

Me neither. But one thing to look for would be people doing `round(a / b)`, which is almost certainly giving the wrong result in corner cases. OTOH, even those uses may well be in code that doesn't actually care about getting the wrong result in those corner cases, or that doesn't exercise the corner cases. (E.g., if both `a` and `b` are not-too-large integers, `round(a / b)` is still "safe" in that it will give the same result as if a non-lossy integer division is used.)
msg305941 - (view) Author: Wolfgang Maier (wolma) * Date: 2017-11-09 08:21
> (E.g., if both `a` and `b` are not-too-large integers, `round(a / b)` is still "safe" in that it will give the same result as if a non-lossy integer division is used.)

Well, it does not take particularly large a and b to break round's tie-breaking through rounding-to-even though:

>>> for x in range(1,501):
        for y in range(1,501):
            if round(x/y, 1) != float(round(F(x,y), 1)):
                print(x,y)

1 20
2 40
3 20
3 60
4 80
5 100
6 40
6 120
7 20
7 140
8 160
9 20
9 60
9 180
10 200
11 220
12 80
12 240
13 20
13 260
14 40
14 280
15 100
15 300
16 320
17 340
18 40
18 120
18 360
19 20
19 380
20 400
21 20
21 60
21 140
21 420
22 440
23 20
23 460
24 160
24 480
25 500

...
msg305942 - (view) Author: Wolfgang Maier (wolma) * Date: 2017-11-09 08:22
>>> for x in range(1,501):
        for y in range(1,501):
            if round(x/y, 1) != float(round(F(x,y), 1)):
                print(x,y)

where F is fractions.Fraction
Sorry!
msg305943 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2017-11-09 08:36
Mark said about round(x/y), not round(x/y, 1). Do you propose to add a three argument divide_and_round(x, y, ndigits)?
msg305944 - (view) Author: Wolfgang Maier (wolma) * Date: 2017-11-09 08:45
That, of course, wasn't my original suggestion, but since Mark started discussing other possible forms this could take, like round-to-nearest analogs of mod and divmod, I thought maybe it's worth pointing out this aspect and, yes, maybe the three-argument form would be nice. Essentially, this would be fractions.Fraction.__round__ then.
History
Date User Action Args
2017-11-09 08:45:06wolmasetmessages: + msg305944
2017-11-09 08:36:19serhiy.storchakasetmessages: + msg305943
2017-11-09 08:22:48wolmasetmessages: + msg305942
2017-11-09 08:21:08wolmasetmessages: + msg305941
2017-11-08 16:37:53mark.dickinsonsetmessages: + msg305879
2017-11-08 14:36:09serhiy.storchakasetmessages: + msg305851
2017-11-08 14:08:12wolmasetmessages: + msg305846
2017-11-08 14:04:26mark.dickinsonsetmessages: + msg305844
2017-11-08 13:56:47mark.dickinsonsetmessages: + msg305843
2017-11-08 10:37:50serhiy.storchakasetnosy: + rhettinger, skrah, stutzbach, facundobatista, belopolsky, serhiy.storchaka

messages: + msg305818
versions: - Python 3.8
2017-11-08 10:13:02wolmacreate