Speed up `Fraction.__round__` for large negative `ndigits`

[devdanzin]

Feature or enhancement

Proposal:

Rounding a Fraction to a large negative ndigits takes a long time, only to return Fraction(0, 1):

>>> from fractions import Fraction
>>> large_negative_number = -2**31
>>> d = Fraction(17, 33)
>>> d.__round__(large_negative_number)  # Takes forever, calculating `10**abs(ndigits)`

Using the check below, the code above returns almost instantly:

if ndigits < 0 and int(math.log10(self)) < abs(ndigits):
    return Fraction(0, 1)

I realize there may not be a real use case for this enhancement. OTOH, it's such a simple code change that it might make sense. If it's considered worthy of implementing, I can submit a PR (which also speeds up _round_to_exponent in a similar way).

cc @JelleZijlstra

Has this already been discussed elsewhere?

This is a minor feature, which does not need previous discussion elsewhere

Links to previous discussion of this feature:

It was very briefly discussed on Discord.

[sobolevn]

Please, provide a benchmark for before and after. You can use pyperf, for example.

[skirpichev]

Same remark as for integer case (and same example "works"), but here we also have implicit self->float conversion.

[devdanzin]

Please, provide a benchmark for before and after.

Here's one showing the improvements as ndigits grows. Unfortunately, the code has the issues @skirpichev pointed, so numbers might look worse with corrected code.

+----------------------------+-----------------------+----------------------------+
| Benchmark                  | fraction_round_before | fraction_round_after       |
+============================+=======================+============================+
| Fraction.__round__(-2**1)  | 7.17 us               | 2.93 us: 2.45x faster      |
+----------------------------+-----------------------+----------------------------+
| Fraction.__round__(-2**7)  | 9.36 us               | 2.94 us: 3.18x faster      |
+----------------------------+-----------------------+----------------------------+
| Fraction.__round__(-2**14) | 809 us                | 2.99 us: 270.81x faster    |
+----------------------------+-----------------------+----------------------------+
| Fraction.__round__(-2**21) | 1.45 sec              | 2.96 us: 490332.01x faster |
+----------------------------+-----------------------+----------------------------+
| Geometric mean             | (ref)                 | 179.26x faster             |
+----------------------------+-----------------------+----------------------------+

[devdanzin]

Same remark as for integer case (and same example "works"), but here we also have implicit self->float conversion.

Bummer. Unfortunately I don't have the maths or programming chops to correct the code, so I'm withdrawing my offer of a PR.

For reference, here's the incorrect diff to show the attempted improvement to _round_to_exponent :

diff --git a/Lib/fractions.py b/Lib/fractions.py
index f0cbc8c2e6c..32b63e59899 100644
--- a/Lib/fractions.py
+++ b/Lib/fractions.py
@@ -84,6 +84,15 @@ def _round_to_exponent(n, d, exponent, no_neg_zero=False):

     d must be positive, but n and d need not be relatively prime.
     """
+    if n == 0 or exponent > math.log10(abs(n)):
+        sign = False
+        if not no_neg_zero:
+            if n == 0:
+                sign = math.copysign(1.0, n) > 0
+            elif (n < 0 and d < 0) or (n > 0 and d > 0) :
+                sign = True
+        return sign,  0
+
     if exponent >= 0:
         d *= 10**exponent
     else:
@@ -971,6 +980,8 @@ def __round__(self, ndigits=None):
                 return floor
             else:
                 return floor + 1
+        if ndigits < 0 and int(math.log10(self)) < abs(ndigits):
+            return Fraction(0, 1)
         shift = 10**abs(ndigits)
         # See _operator_fallbacks.forward to check that the results of
         # these operations will always be Fraction and therefore have

[skirpichev]

numbers might look worse with corrected code

No, I don't expect that.

Yet your benchmark results seems cryptic for me. I guess @sobolevn asked you to measure performance in case you hit negative test (i.e. int(math.log10(self)) < abs(ndigits) is False). In your results you show big improvements, so I suspect you did measurements only for some fixed self and increasing abs(ndigits).

Unfortunately I don't have the maths or programming chops to correct the code, so I'm withdrawing my offer of a PR.

I think it's not too hard, especially for integers. But if you aren't interested, I'll take over it.

CC @mdickinson

PS: Unfortunately, gmpy2's version (quoted in the #132474) seems buggy:

>>> import gmpy2
>>> round(gmpy2.mpz(501), gmpy2.mpz(-3))
mpz(0)
>>> round(int(gmpy2.mpz(501)), int(gmpy2.mpz(-3)))
1000

[devdanzin]

I suspect you did measurements only for some fixed self and increasing abs(ndigits).

Correct, I didn't think of negative cases.

I think it's not too hard, especially for integers. But if you aren't interested, I'll take over it.

Oh, I don't know C either. Please take it over, glad to have found something interesting :)

[skirpichev]

I think this can be postponed, until we decide with more basic case: #132474