[issue37295] Possible optimizations for math.comb()

[Tim Peters]

Tim Peters <tim at python.org> added the comment:

In real life, I expect 99.999%+ of calls will be made with small arguments, so (1) is worth it.  I like Mark's suggestion to use uint64_t so the acceptable range doesn't depend on platform.  At least in the world I live in, 32-bit boxes are all but extinct anyway.

I honestly wouldn't bother with more than that.  It's fun to optimize giant-integer algorithms with an ever-ballooning number of different clever approaches, but Python is an odd place for that.  People looking for blazing fast giant-int facilities generally want lots & lots of them, so are better steered toward, e.g., gmp.  That's its reason for existing.

For example, their implementation of binomial coefficients uses special division algorithms exploiting that the quotient is exact (no remainder):

https://gmplib.org/manual/Exact-Division.html#Exact-Division

There's just no end to potential speedups.  But in Python, I expect a vast majority of users will be happy if they get the right answer for the number of possible poker hands ;-)

Oh ya - some smart kid will file a bug report about the inability to interrupt the calculation of a billion-bit result, so (4) is inevitable.  Me, I'd wait for them to complain, and encourage _them_ to learn something useful by writing a patch to fix it :-)

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue37295>
_______________________________________