[issue37295] Possible optimizations for math.comb()

[Stefan Pochmann]

Stefan Pochmann <stefan.pochmann at gmail.com> added the comment:

And for Raymond's case 4), about running very long and not responding to SIGINT, with n=1_000_000 and k=500_000:

150.91 seconds  math.comb(n, k)
 39.11 seconds  factorial(n) // (factorial(k) * factorial(n-k))
  0.40 seconds  mycomb(n, k)
  0.14 seconds  *estimation* for mycomb if written in C

And for n=10_000_000 and k=5_000_000:

   ~4 hours    *estimation* for math.comb(n, k)
   ~1 hour     *estimation* for factorials solution
  8.3 seconds  mycomb(n, k)
  4.5 seconds  *estimation* for mycomb if written in C

----------

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