]> git.ipfire.org Git - thirdparty/Python/cpython.git/commit
Issue #8692: Improve performance of math.factorial:
authorMark Dickinson <dickinsm@gmail.com>
Sat, 15 May 2010 17:02:38 +0000 (17:02 +0000)
committerMark Dickinson <dickinsm@gmail.com>
Sat, 15 May 2010 17:02:38 +0000 (17:02 +0000)
commit4c8a9a2df3c31b1c29d0b3cf74523e3c8b3dae72
treef28718e84ae7a59ec3ec6780fa5fa2328362edf2
parentae6265f8d06dbec7d08c73ca23dad0f040d09b8e
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.
Lib/test/test_math.py
Misc/NEWS
Modules/mathmodule.c