[issue37295] Possible optimizations for math.comb()

[Tim Peters]

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

A feature of the current code is that, while the recursion tree can be very wide, it's not tall, with max depth proportional to the log of k. But it's proportional to k in the proposal (the C(n-j, k-j) term's second argument goes down by at most 20 per recursion level).

So, e.g., C(1000000, 500000) dies with RecursionError in Python; in C, whatever platform-specific weird things can happen when the C stack is blown.

The width of the recursion tree could be slashed in any case by "just dealing with" (say) k <= 20 directly, no matter how large n is. Do the obvious loop with k-1 multiplies, and k-1 divides by the tiny ints in range(2, k+1). Note that "almost all" the calls in your "trace for the old code" listing are due to recurring for k <= 20.  Or use Stefan's method: if limited to k <= 20, it only requires a tiny precomputed table of the 8 primes <= 20, and a stack array to hold range(n, n-k, -1); that can be arranged to keep Karatsuba in play if n is large.

An irony is that the primary point of the recurrence is to get Karatsuba multiplication into play, but the ints involved in computing C(240, 112) are nowhere near big enough to trigger that.

To limit recursion depth, I think you have to change your approach to decide in advance the deepest you're willing to risk letting it go, and keep the current j = k // 2 whenever repeatedly subtracting 20 could exceed that.

----------

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