Author Stefan Pochmann
Recipients PedanticHacker, Stefan Pochmann, mark.dickinson, mcognetta, pablogsal, rhettinger, serhiy.storchaka, tim.peters
Date 2021-11-15.04:27:26
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1636950447.1.0.607446215499.issue37295@roundup.psfhosted.org>
In-reply-to
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>
2021-11-15 04:27:27Stefan Pochmannlinkissue37295 messages
2021-11-15 04:27:26Stefan Pochmanncreate