Issue31978

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) * | 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) * | 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) * | 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) * | 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) * | 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) * | 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:06 | wolma | set | messages: + msg305944 |

2017-11-09 08:36:19 | serhiy.storchaka | set | messages: + msg305943 |

2017-11-09 08:22:48 | wolma | set | messages: + msg305942 |

2017-11-09 08:21:08 | wolma | set | messages: + msg305941 |

2017-11-08 16:37:53 | mark.dickinson | set | messages: + msg305879 |

2017-11-08 14:36:09 | serhiy.storchaka | set | messages: + msg305851 |

2017-11-08 14:08:12 | wolma | set | messages: + msg305846 |

2017-11-08 14:04:26 | mark.dickinson | set | messages: + msg305844 |

2017-11-08 13:56:47 | mark.dickinson | set | messages: + msg305843 |

2017-11-08 10:37:50 | serhiy.storchaka | set | nosy:
+ rhettinger, skrah, stutzbach, facundobatista, belopolsky, serhiy.storchaka messages: + msg305818 versions: - Python 3.8 |

2017-11-08 10:13:02 | wolma | create |