[Python-checkins] bpo-35588: Speed up mod, divmod and floordiv operations for Fraction type (#11322)
Serhiy Storchaka
webhook-mailer at python.org
Wed Jan 2 07:22:09 EST 2019
https://github.com/python/cpython/commit/3a374e0c5abe805667b71ffaaa7614781101ff4c
commit: 3a374e0c5abe805667b71ffaaa7614781101ff4c
branch: master
author: Stefan Behnel <stefan_ml at behnel.de>
committer: Serhiy Storchaka <storchaka at gmail.com>
date: 2019-01-02T14:22:06+02:00
summary:
bpo-35588: Speed up mod, divmod and floordiv operations for Fraction type (#11322)
* bpo-35588: Implement mod and divmod operations for Fraction type by spelling out the numerator/denominator calculation, instead of instantiating and normalising Fractions along the way. This speeds up '%' and divmod() by 2-3x.
* bpo-35588: Also reimplement Fraction.__floordiv__() using integer operations to make it ~4x faster.
* Improve code formatting.
Co-Authored-By: scoder <stefan_ml at behnel.de>
* bpo-35588: Fix return type of divmod(): the result of the integer division should be an integer.
* bpo-35588: Further specialise __mod__() and inline the original helper function _flat_divmod() since it's no longer reused.
* bpo-35588: Add some tests with large numerators and/or denominators.
* bpo-35588: Use builtin "divmod()" function for implementing __divmod__() in order to simplify the implementation, even though performance results are mixed.
* Rremove accidentally added empty line.
* bpo-35588: Try to provide more informative output on test failures.
* bpo-35588: Improve wording in News entry.
Co-Authored-By: scoder <stefan_ml at behnel.de>
* Remove stray space.
files:
A Misc/NEWS.d/next/Library/2018-12-26-10-55-59.bpo-35588.PSR6Ez.rst
M Lib/fractions.py
M Lib/test/test_fractions.py
diff --git a/Lib/fractions.py b/Lib/fractions.py
index e0a024a03b14..4bbfc434f7d1 100644
--- a/Lib/fractions.py
+++ b/Lib/fractions.py
@@ -429,14 +429,22 @@ def _div(a, b):
def _floordiv(a, b):
"""a // b"""
- return math.floor(a / b)
+ return (a.numerator * b.denominator) // (a.denominator * b.numerator)
__floordiv__, __rfloordiv__ = _operator_fallbacks(_floordiv, operator.floordiv)
+ def _divmod(a, b):
+ """(a // b, a % b)"""
+ da, db = a.denominator, b.denominator
+ div, n_mod = divmod(a.numerator * db, da * b.numerator)
+ return div, Fraction(n_mod, da * db)
+
+ __divmod__, __rdivmod__ = _operator_fallbacks(_divmod, divmod)
+
def _mod(a, b):
"""a % b"""
- div = a // b
- return a - b * div
+ da, db = a.denominator, b.denominator
+ return Fraction((a.numerator * db) % (b.numerator * da), da * db)
__mod__, __rmod__ = _operator_fallbacks(_mod, operator.mod)
diff --git a/Lib/test/test_fractions.py b/Lib/test/test_fractions.py
index 452f18126de9..277916220051 100644
--- a/Lib/test/test_fractions.py
+++ b/Lib/test/test_fractions.py
@@ -117,6 +117,11 @@ def assertTypedEquals(self, expected, actual):
self.assertEqual(type(expected), type(actual))
self.assertEqual(expected, actual)
+ def assertTypedTupleEquals(self, expected, actual):
+ """Asserts that both the types and values in the tuples are the same."""
+ self.assertTupleEqual(expected, actual)
+ self.assertListEqual(list(map(type, expected)), list(map(type, actual)))
+
def assertRaisesMessage(self, exc_type, message,
callable, *args, **kwargs):
"""Asserts that callable(*args, **kwargs) raises exc_type(message)."""
@@ -349,7 +354,10 @@ def testArithmetic(self):
self.assertEqual(F(1, 4), F(1, 10) / F(2, 5))
self.assertTypedEquals(2, F(9, 10) // F(2, 5))
self.assertTypedEquals(10**23, F(10**23, 1) // F(1))
+ self.assertEqual(F(5, 6), F(7, 3) % F(3, 2))
self.assertEqual(F(2, 3), F(-7, 3) % F(3, 2))
+ self.assertEqual((F(1), F(5, 6)), divmod(F(7, 3), F(3, 2)))
+ self.assertEqual((F(-2), F(2, 3)), divmod(F(-7, 3), F(3, 2)))
self.assertEqual(F(8, 27), F(2, 3) ** F(3))
self.assertEqual(F(27, 8), F(2, 3) ** F(-3))
self.assertTypedEquals(2.0, F(4) ** F(1, 2))
@@ -371,6 +379,40 @@ def testArithmetic(self):
self.assertEqual(p.numerator, 4)
self.assertEqual(p.denominator, 1)
+ def testLargeArithmetic(self):
+ self.assertTypedEquals(
+ F(10101010100808080808080808101010101010000000000000000,
+ 1010101010101010101010101011111111101010101010101010101010101),
+ F(10**35+1, 10**27+1) % F(10**27+1, 10**35-1)
+ )
+ self.assertTypedEquals(
+ F(7, 1901475900342344102245054808064),
+ F(-2**100, 3) % F(5, 2**100)
+ )
+ self.assertTypedTupleEquals(
+ (9999999999999999,
+ F(10101010100808080808080808101010101010000000000000000,
+ 1010101010101010101010101011111111101010101010101010101010101)),
+ divmod(F(10**35+1, 10**27+1), F(10**27+1, 10**35-1))
+ )
+ self.assertTypedEquals(
+ -2 ** 200 // 15,
+ F(-2**100, 3) // F(5, 2**100)
+ )
+ self.assertTypedEquals(
+ 1,
+ F(5, 2**100) // F(3, 2**100)
+ )
+ self.assertTypedEquals(
+ (1, F(2, 2**100)),
+ divmod(F(5, 2**100), F(3, 2**100))
+ )
+ self.assertTypedTupleEquals(
+ (-2 ** 200 // 15,
+ F(7, 1901475900342344102245054808064)),
+ divmod(F(-2**100, 3), F(5, 2**100))
+ )
+
def testMixedArithmetic(self):
self.assertTypedEquals(F(11, 10), F(1, 10) + 1)
self.assertTypedEquals(1.1, F(1, 10) + 1.0)
@@ -415,7 +457,14 @@ def testMixedArithmetic(self):
self.assertTypedEquals(float('inf'), F(-1, 10) % float('inf'))
self.assertTypedEquals(-0.1, F(-1, 10) % float('-inf'))
- # No need for divmod since we don't override it.
+ self.assertTypedTupleEquals((0, F(1, 10)), divmod(F(1, 10), 1))
+ self.assertTypedTupleEquals(divmod(0.1, 1.0), divmod(F(1, 10), 1.0))
+ self.assertTypedTupleEquals((10, F(0)), divmod(1, F(1, 10)))
+ self.assertTypedTupleEquals(divmod(1.0, 0.1), divmod(1.0, F(1, 10)))
+ self.assertTypedTupleEquals(divmod(0.1, float('inf')), divmod(F(1, 10), float('inf')))
+ self.assertTypedTupleEquals(divmod(0.1, float('-inf')), divmod(F(1, 10), float('-inf')))
+ self.assertTypedTupleEquals(divmod(-0.1, float('inf')), divmod(F(-1, 10), float('inf')))
+ self.assertTypedTupleEquals(divmod(-0.1, float('-inf')), divmod(F(-1, 10), float('-inf')))
# ** has more interesting conversion rules.
self.assertTypedEquals(F(100, 1), F(1, 10) ** -2)
diff --git a/Misc/NEWS.d/next/Library/2018-12-26-10-55-59.bpo-35588.PSR6Ez.rst b/Misc/NEWS.d/next/Library/2018-12-26-10-55-59.bpo-35588.PSR6Ez.rst
new file mode 100644
index 000000000000..270f556e76b2
--- /dev/null
+++ b/Misc/NEWS.d/next/Library/2018-12-26-10-55-59.bpo-35588.PSR6Ez.rst
@@ -0,0 +1,2 @@
+The floor division and modulo operations and the :func:`divmod` function on :class:`fractions.Fraction` types are 2--4x faster.
+Patch by Stefan Behnel.
More information about the Python-checkins
mailing list