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 Stefan Pochmann PedanticHacker, Stefan Pochmann, mark.dickinson, mcognetta, pablogsal, rhettinger, serhiy.storchaka, tim.peters 2021-11-15.04:27:26 -1.0 Yes <1636950447.1.0.607446215499.issue37295@roundup.psfhosted.org>
Content
```I wrote a Python solution ("mycomb") that computes comb(100_000, 50_000) faster, maybe of interest:

1510.4 ms  math.comb(n, k)
460.8 ms  factorial(n) // (factorial(k) * factorial(n-k))
27.5 ms  mycomb(n, k)
6.7 ms  *estimation* for mycomb if written in C

The idea:

13 * 12 * 11 * 10 * 9 * 8
comb(13, 6)  =  -------------------------  =  13 * 1 * 11 * 1 * 3 * 4
1 * 2 * 3 * 4 * 5 * 6

It lists the numerator factors, then divides the denominator factors out of them (using primes), then just multiplies.

Preparing the factors for the final multiplication took most of the time, about 23.1 ms. That part only needs numbers <= n, so it could be done with C ints and be much faster. If it's ten times faster, then mycomb in C would take 23.1/10 + (27.5-23.1) = 6.71 ms.

See the comb_with_primes.py file.```
History
Date User Action Args
2021-11-15 04:27:27Stefan Pochmannsetrecipients: + Stefan Pochmann, tim.peters, rhettinger, mark.dickinson, serhiy.storchaka, PedanticHacker, mcognetta, pablogsal
2021-11-15 04:27:27Stefan Pochmannsetmessageid: <1636950447.1.0.607446215499.issue37295@roundup.psfhosted.org>