Message410931
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. |
|
Date |
User |
Action |
Args |
2022-01-19 10:16:01 | serhiy.storchaka | set | recipients:
+ serhiy.storchaka, tim.peters, rhettinger, mark.dickinson, PedanticHacker, mcognetta, Stefan Pochmann |
2022-01-19 10:16:01 | serhiy.storchaka | set | messageid: <1642587361.28.0.571309674684.issue37295@roundup.psfhosted.org> |
2022-01-19 10:16:01 | serhiy.storchaka | link | issue37295 messages |
2022-01-19 10:16:01 | serhiy.storchaka | create | |
|