Skip to content

Update fractions to CPython 3.11.5 #5072

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Oct 1, 2023
Merged

Update fractions to CPython 3.11.5 #5072

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
232 changes: 166 additions & 66 deletions Lib/fractions.py
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,7 +1,7 @@
# Originally contributed by Sjoerd Mullender.
# Significantly modified by Jeffrey Yasskin <jyasskin at gmail.com>.

"""Fraction, infinite-precision, real numbers."""
"""Fraction, infinite-precision, rational numbers."""

from decimal import Decimal
import math
Expand All @@ -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
Expand All @@ -43,17 +21,17 @@ def _gcd(a, b):
_PyHASH_INF = sys.hash_info.inf

_RATIONAL_FORMAT = re.compile(r"""
\A\s* # optional whitespace at the start, then
(?P<sign>[-+]?) # an optional sign, then
(?=\d|\.\d) # lookahead for digit or .digit
(?P<num>\d*) # numerator (possibly empty)
(?: # followed by
(?:/(?P<denom>\d+))? # an optional denominator
| # or
(?:\.(?P<decimal>\d*))? # an optional fractional part
(?:E(?P<exp>[-+]?\d+))? # and optional exponent
\A\s* # optional whitespace at the start,
(?P<sign>[-+]?) # an optional sign, then
(?=\d|\.\d) # lookahead for digit or .digit
(?P<num>\d*|\d+(_\d+)*) # numerator (possibly empty)
(?: # followed by
(?:/(?P<denom>\d+(_\d+)*))? # an optional denominator
| # or
(?:\.(?P<decimal>d*|\d+(_\d+)*))? # an optional fractional part
(?:E(?P<exp>[-+]?\d+(_\d+)*))? # and optional exponent
)
\s*\Z # and optional whitespace to finish
\s*\Z # and optional whitespace to finish
""", re.VERBOSE | re.IGNORECASE)


Expand Down Expand Up @@ -144,6 +122,7 @@ def __new__(cls, numerator=0, denominator=None, *, _normalize=True):
denominator = 1
decimal = m.group('decimal')
if decimal:
decimal = decimal.replace('_', '')
scale = 10**len(decimal)
numerator = numerator * scale + int(decimal)
denominator *= scale
Expand Down Expand Up @@ -177,13 +156,9 @@ def __new__(cls, numerator=0, denominator=None, *, _normalize=True):
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
Expand Down Expand Up @@ -406,32 +381,139 @@ def reverse(b, a):

return forward, reverse

# Rational arithmetic algorithms: Knuth, TAOCP, Volume 2, 4.5.1.
#
# Assume input fractions a and b are normalized.
#
# 1) Consider addition/subtraction.
#
# Let g = gcd(da, db). Then
#
# na nb na*db ± nb*da
# a ± b == -- ± -- == ------------- ==
# da db da*db
#
# na*(db//g) ± nb*(da//g) t
# == ----------------------- == -
# (da*db)//g d
#
# Now, if g > 1, we're working with smaller integers.
#
# Note, that t, (da//g) and (db//g) are pairwise coprime.
#
# Indeed, (da//g) and (db//g) share no common factors (they were
# removed) and da is coprime with na (since input fractions are
# normalized), hence (da//g) and na are coprime. By symmetry,
# (db//g) and nb are coprime too. Then,
#
# gcd(t, da//g) == gcd(na*(db//g), da//g) == 1
# gcd(t, db//g) == gcd(nb*(da//g), db//g) == 1
#
# Above allows us optimize reduction of the result to lowest
# terms. Indeed,
#
# g2 = gcd(t, d) == gcd(t, (da//g)*(db//g)*g) == gcd(t, g)
#
# t//g2 t//g2
# a ± b == ----------------------- == ----------------
# (da//g)*(db//g)*(g//g2) (da//g)*(db//g2)
#
# is a normalized fraction. This is useful because the unnormalized
# denominator d could be much larger than g.
#
# We should special-case g == 1 (and g2 == 1), since 60.8% of
# randomly-chosen integers are coprime:
# https://en.wikipedia.org/wiki/Coprime_integers#Probability_of_coprimality
# Note, that g2 == 1 always for fractions, obtained from floats: here
# g is a power of 2 and the unnormalized numerator t is an odd integer.
#
# 2) Consider multiplication
#
# Let g1 = gcd(na, db) and g2 = gcd(nb, da), then
#
# na*nb na*nb (na//g1)*(nb//g2)
# a*b == ----- == ----- == -----------------
# da*db db*da (db//g1)*(da//g2)
#
# Note, that after divisions we're multiplying smaller integers.
#
# Also, the resulting fraction is normalized, because each of
# two factors in the numerator is coprime to each of the two factors
# in the denominator.
#
# Indeed, pick (na//g1). It's coprime with (da//g2), because input
# fractions are normalized. It's also coprime with (db//g1), because
# common factors are removed by g1 == gcd(na, db).
#
# As for addition/subtraction, we should special-case g1 == 1
# and g2 == 1 for same reason. That happens also for multiplying
# rationals, obtained from floats.

def _add(a, b):
"""a + b"""
da, db = a.denominator, b.denominator
return Fraction(a.numerator * db + b.numerator * da,
da * db)
na, da = a.numerator, a.denominator
nb, db = b.numerator, b.denominator
g = math.gcd(da, db)
if g == 1:
return Fraction(na * db + da * nb, da * db, _normalize=False)
s = da // g
t = na * (db // g) + nb * s
g2 = math.gcd(t, g)
if g2 == 1:
return Fraction(t, s * db, _normalize=False)
return Fraction(t // g2, s * (db // g2), _normalize=False)

__add__, __radd__ = _operator_fallbacks(_add, operator.add)

def _sub(a, b):
"""a - b"""
da, db = a.denominator, b.denominator
return Fraction(a.numerator * db - b.numerator * da,
da * db)
na, da = a.numerator, a.denominator
nb, db = b.numerator, b.denominator
g = math.gcd(da, db)
if g == 1:
return Fraction(na * db - da * nb, da * db, _normalize=False)
s = da // g
t = na * (db // g) - nb * s
g2 = math.gcd(t, g)
if g2 == 1:
return Fraction(t, s * db, _normalize=False)
return Fraction(t // g2, s * (db // g2), _normalize=False)

__sub__, __rsub__ = _operator_fallbacks(_sub, operator.sub)

def _mul(a, b):
"""a * b"""
return Fraction(a.numerator * b.numerator, a.denominator * b.denominator)
na, da = a.numerator, a.denominator
nb, db = b.numerator, b.denominator
g1 = math.gcd(na, db)
if g1 > 1:
na //= g1
db //= g1
g2 = math.gcd(nb, da)
if g2 > 1:
nb //= g2
da //= g2
return Fraction(na * nb, db * da, _normalize=False)

__mul__, __rmul__ = _operator_fallbacks(_mul, operator.mul)

def _div(a, b):
"""a / b"""
return Fraction(a.numerator * b.denominator,
a.denominator * b.numerator)
# Same as _mul(), with inversed b.
na, da = a.numerator, a.denominator
nb, db = b.numerator, b.denominator
g1 = math.gcd(na, nb)
if g1 > 1:
na //= g1
nb //= g1
g2 = math.gcd(db, da)
if g2 > 1:
da //= g2
db //= g2
n, d = na * db, nb * da
if d < 0:
n, d = -n, -d
return Fraction(n, d, _normalize=False)

__truediv__, __rtruediv__ = _operator_fallbacks(_div, operator.truediv)

Expand Down Expand Up @@ -512,8 +594,15 @@ def __abs__(a):
"""abs(a)"""
return Fraction(abs(a._numerator), a._denominator, _normalize=False)

def __int__(a, _index=operator.index):
"""int(a)"""
if a._numerator < 0:
return _index(-(-a._numerator // a._denominator))
else:
return _index(a._numerator // a._denominator)

def __trunc__(a):
"""trunc(a)"""
"""math.trunc(a)"""
if a._numerator < 0:
return -(-a._numerator // a._denominator)
else:
Expand Down Expand Up @@ -556,23 +645,34 @@ def __round__(self, ndigits=None):
def __hash__(self):
"""hash(self)"""

# XXX since this method is expensive, consider caching the result

# 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').
# 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):
Expand Down Expand Up @@ -643,7 +743,7 @@ def __bool__(a):
# support for pickling, copy, and deepcopy

def __reduce__(self):
return (self.__class__, (str(self),))
return (self.__class__, (self._numerator, self._denominator))

def __copy__(self):
if type(self) == Fraction:
Expand Down
Loading