diff options
| author | Mark Dickinson <dickinsm@gmail.com> | 2010-05-15 17:02:38 (GMT) |
|---|---|---|
| committer | Mark Dickinson <dickinsm@gmail.com> | 2010-05-15 17:02:38 (GMT) |
| commit | 4c8a9a2df3c31b1c29d0b3cf74523e3c8b3dae72 (patch) | |
| tree | f28718e84ae7a59ec3ec6780fa5fa2328362edf2 /Misc/NEWS | |
| parent | ae6265f8d06dbec7d08c73ca23dad0f040d09b8e (diff) | |
| download | cpython-4c8a9a2df3c31b1c29d0b3cf74523e3c8b3dae72.zip cpython-4c8a9a2df3c31b1c29d0b3cf74523e3c8b3dae72.tar.gz cpython-4c8a9a2df3c31b1c29d0b3cf74523e3c8b3dae72.tar.bz2 | |
Issue #8692: Improve performance of math.factorial:
(1) use a different algorithm that roughly halves the total number of
multiplications required and results in more balanced multiplications
(2) use a lookup table for small arguments
(3) fast accumulation of products in C integer arithmetic rather than
PyLong arithmetic when possible.
Typical speedup, from unscientific testing on a 64-bit laptop, is 4.5x
to 6.5x for arguments in the range 100 - 10000.
Patch by Daniel Stutzbach; extensive reviews by Alexander Belopolsky.
Diffstat (limited to 'Misc/NEWS')
| -rw-r--r-- | Misc/NEWS | 6 |
1 files changed, 6 insertions, 0 deletions
@@ -1132,6 +1132,12 @@ Library Extension Modules ----------------- +- Issue #8692: Optimize math.factorial: replace the previous naive + algorithm with an improved 'binary-split' algorithm that uses fewer + multiplications and allows many of the multiplications to be + performed using plain C integer arithmetic instead of PyLong + arithmetic. Also uses a lookup table for small arguments. + - Issue #8674: Fixed a number of incorrect or undefined-behaviour-inducing overflow checks in the audioop module. |