| 22 | |
| 23 | @functools.lru_cache(maxsize = 1 << 14) |
| 24 | def _hash_algorithm(numerator, denominator): |
| 25 | |
| 26 | # To make sure that the hash of a Fraction agrees with the hash |
| 27 | # of a numerically equal integer, float or Decimal instance, we |
| 28 | # follow the rules for numeric hashes outlined in the |
| 29 | # documentation. (See library docs, 'Built-in Types'). |
| 30 | |
| 31 | try: |
| 32 | dinv = pow(denominator, -1, _PyHASH_MODULUS) |
| 33 | except ValueError: |
| 34 | # ValueError means there is no modular inverse. |
| 35 | hash_ = _PyHASH_INF |
| 36 | else: |
| 37 | # The general algorithm now specifies that the absolute value of |
| 38 | # the hash is |
| 39 | # (|N| * dinv) % P |
| 40 | # where N is self._numerator and P is _PyHASH_MODULUS. That's |
| 41 | # optimized here in two ways: first, for a non-negative int i, |
| 42 | # hash(i) == i % P, but the int hash implementation doesn't need |
| 43 | # to divide, and is faster than doing % P explicitly. So we do |
| 44 | # hash(|N| * dinv) |
| 45 | # instead. Second, N is unbounded, so its product with dinv may |
| 46 | # be arbitrarily expensive to compute. The final answer is the |
| 47 | # same if we use the bounded |N| % P instead, which can again |
| 48 | # be done with an int hash() call. If 0 <= i < P, hash(i) == i, |
| 49 | # so this nested hash() call wastes a bit of time making a |
| 50 | # redundant copy when |N| < P, but can save an arbitrarily large |
| 51 | # amount of computation for large |N|. |
| 52 | hash_ = hash(hash(abs(numerator)) * dinv) |
| 53 | result = hash_ if numerator >= 0 else -hash_ |
| 54 | return -2 if result == -1 else result |
| 55 | |
| 56 | _RATIONAL_FORMAT = re.compile(r""" |
| 57 | \A\s* # optional whitespace at the start, |