]> git.ipfire.org Git - thirdparty/Python/cpython.git/commit
bpo-43420: Simple optimizations for Fraction's arithmetics
authorSergey B Kirpichev <skirpichev@gmail.com>
Sun, 14 Mar 2021 03:39:21 +0000 (06:39 +0300)
committerSergey B Kirpichev <skirpichev@gmail.com>
Sun, 14 Mar 2021 05:26:56 +0000 (08:26 +0300)
commit430e4764cb554ab4c3fef16990dc55186a18b771
tree0e6055908c7f3529f08ffb7ee5640aea74b2ddb7
parent598b3c96307618abc71bfe984b1460aca3f51ecc
bpo-43420: Simple optimizations for Fraction's arithmetics

making Fraction class more usable for large arguments (>~ 10**6),
with cost 10-20% for small components case.

Before:
$ ./python -m timeit -s 'from fractions import Fraction as F' \
-s 'a=[F(1, _**3) for _ in range(1, 1000)]' 'sum(a)'
5 loops, best of 5: 81.2 msec per loop

After:
$ ./python -m timeit -s 'from fractions import Fraction as F' \
-s 'a=[F(1, _**3) for _ in range(1, 1000)]' 'sum(a)'
10 loops, best of 5: 23 msec per loop

References:
Knuth, TAOCP, Volume 2, 4.5.1,
https://www.eecis.udel.edu/~saunders/courses/822/98f/collins-notes/rnarith.ps,
https://gmplib.org/ (e.g. https://gmplib.org/repo/gmp/file/tip/mpq/aors.c)
Lib/fractions.py
Misc/NEWS.d/next/Library/2021-03-07-08-03-31.bpo-43420.cee_X5.rst [new file with mode: 0644]