Message406337
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. |
|
Date |
User |
Action |
Args |
2021-11-15 04:27:27 | Stefan Pochmann | set | recipients:
+ Stefan Pochmann, tim.peters, rhettinger, mark.dickinson, serhiy.storchaka, PedanticHacker, mcognetta, pablogsal |
2021-11-15 04:27:27 | Stefan Pochmann | set | messageid: <1636950447.1.0.607446215499.issue37295@roundup.psfhosted.org> |
2021-11-15 04:27:27 | Stefan Pochmann | link | issue37295 messages |
2021-11-15 04:27:26 | Stefan Pochmann | create | |
|