Stefan Pochmann <[email protected]> added the comment:
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.
----------
nosy: +Stefan Pochmann
Added file: https://bugs.python.org/file50439/comb_with_primes.py
_______________________________________
Python tracker <[email protected]>
<https://bugs.python.org/issue37295>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
