diff options
Diffstat (limited to 'Lib/fractions.py')
| -rw-r--r-- | Lib/fractions.py | 19 |
1 files changed, 17 insertions, 2 deletions
diff --git a/Lib/fractions.py b/Lib/fractions.py index c922c38..2e7047a 100644 --- a/Lib/fractions.py +++ b/Lib/fractions.py @@ -564,10 +564,25 @@ class Fraction(numbers.Rational): try: dinv = pow(self._denominator, -1, _PyHASH_MODULUS) except ValueError: - # ValueError means there is no modular inverse + # ValueError means there is no modular inverse. hash_ = _PyHASH_INF else: - hash_ = hash(abs(self._numerator)) * dinv % _PyHASH_MODULUS + # The general algorithm now specifies that the absolute value of + # the hash is + # (|N| * dinv) % P + # where N is self._numerator and P is _PyHASH_MODULUS. That's + # optimized here in two ways: first, for a non-negative int i, + # hash(i) == i % P, but the int hash implementation doesn't need + # to divide, and is faster than doing % P explicitly. So we do + # hash(|N| * dinv) + # instead. Second, N is unbounded, so its product with dinv may + # be arbitrarily expensive to compute. The final answer is the + # same if we use the bounded |N| % P instead, which can again + # be done with an int hash() call. If 0 <= i < P, hash(i) == i, + # so this nested hash() call wastes a bit of time making a + # redundant copy when |N| < P, but can save an arbitrarily large + # amount of computation for large |N|. + hash_ = hash(hash(abs(self._numerator)) * dinv) result = hash_ if self._numerator >= 0 else -hash_ return -2 if result == -1 else result |