[issue37295] Possible optimizations for math.comb()

[Serhiy Storchaka]

Serhiy Storchaka <storchaka+cpython at gmail.com> added the comment:

comb(n, k) can be computed as perm(n, k) // factorial(k).

$ ./python -m timeit -r1 -n1 -s 'from math import comb' "comb(1000000, 500000)"
recursive: 1 loop, best of 1: 9.16 sec per loop
iterative: 1 loop, best of 1: 164 sec per loop

$ ./python -m timeit -r1 -n1 -s 'from math import perm, factorial' "perm(1000000, 500000) // factorial(500000)"
recursive: 1 loop, best of 1: 19.8 sec per loop
iterative: 1 loop, best of 1: 137 sec per loop

It is slightly faster than division on every step if use the iterative algorithm, but still much slower than the recursive algorithm. And the latter if faster if perform many small divisions and keep intermediate results smaller.

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue37295>
_______________________________________