This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author serhiy.storchaka
Recipients PedanticHacker, Stefan Pochmann, mark.dickinson, mcognetta, rhettinger, serhiy.storchaka, tim.peters
Date 2022-01-19.10:16:01
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1642587361.28.0.571309674684.issue37295@roundup.psfhosted.org>
In-reply-to
Content
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.
History
Date User Action Args
2022-01-19 10:16:01serhiy.storchakasetrecipients: + serhiy.storchaka, tim.peters, rhettinger, mark.dickinson, PedanticHacker, mcognetta, Stefan Pochmann
2022-01-19 10:16:01serhiy.storchakasetmessageid: <1642587361.28.0.571309674684.issue37295@roundup.psfhosted.org>
2022-01-19 10:16:01serhiy.storchakalinkissue37295 messages
2022-01-19 10:16:01serhiy.storchakacreate