Upgrade to Python 3.9.1 [Windows]
http: //fusion/573206f1-ac79-4e82-b01b-dd1480498170
Change-Id: I13e6ff8bd8fe6073ebaadbf3f7c3f2967543d61b
diff --git a/Lib/fractions.py b/Lib/fractions.py
index e4fcc89..de3e23b 100644
--- a/Lib/fractions.py
+++ b/Lib/fractions.py
@@ -10,31 +10,9 @@
import re
import sys
-__all__ = ['Fraction', 'gcd']
+__all__ = ['Fraction']
-
-def gcd(a, b):
- """Calculate the Greatest Common Divisor of a and b.
-
- Unless b==0, the result will have the same sign as b (so that when
- b is divided by it, the result comes out positive).
- """
- import warnings
- warnings.warn('fractions.gcd() is deprecated. Use math.gcd() instead.',
- DeprecationWarning, 2)
- if type(a) is int is type(b):
- if (b or a) < 0:
- return -math.gcd(a, b)
- return math.gcd(a, b)
- return _gcd(a, b)
-
-def _gcd(a, b):
- # Supports non-integers for backward compatibility.
- while b:
- a, b = b, a%b
- return a
-
# Constants related to the hash implementation; hash(x) is based
# on the reduction of x modulo the prime _PyHASH_MODULUS.
_PyHASH_MODULUS = sys.hash_info.modulus
@@ -177,13 +155,9 @@
if denominator == 0:
raise ZeroDivisionError('Fraction(%s, 0)' % numerator)
if _normalize:
- if type(numerator) is int is type(denominator):
- # *very* normal case
- g = math.gcd(numerator, denominator)
- if denominator < 0:
- g = -g
- else:
- g = _gcd(numerator, denominator)
+ g = math.gcd(numerator, denominator)
+ if denominator < 0:
+ g = -g
numerator //= g
denominator //= g
self._numerator = numerator
@@ -556,23 +530,34 @@
def __hash__(self):
"""hash(self)"""
- # XXX since this method is expensive, consider caching the result
+ # To make sure that the hash of a Fraction agrees with the hash
+ # of a numerically equal integer, float or Decimal instance, we
+ # follow the rules for numeric hashes outlined in the
+ # documentation. (See library docs, 'Built-in Types').
- # In order to make sure that the hash of a Fraction agrees
- # with the hash of a numerically equal integer, float or
- # Decimal instance, we follow the rules for numeric hashes
- # outlined in the documentation. (See library docs, 'Built-in
- # Types').
-
- # dinv is the inverse of self._denominator modulo the prime
- # _PyHASH_MODULUS, or 0 if self._denominator is divisible by
- # _PyHASH_MODULUS.
- dinv = pow(self._denominator, _PyHASH_MODULUS - 2, _PyHASH_MODULUS)
- if not dinv:
+ try:
+ dinv = pow(self._denominator, -1, _PyHASH_MODULUS)
+ except ValueError:
+ # ValueError means there is no modular inverse.
hash_ = _PyHASH_INF
else:
- hash_ = abs(self._numerator) * dinv % _PyHASH_MODULUS
- result = hash_ if self >= 0 else -hash_
+ # 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
def __eq__(a, b):
