[issue37295] Possible optimizations for math.comb()

[Raymond Hettinger]

Raymond Hettinger <raymond.hettinger at gmail.com> added the comment:

FWIW, here's a rough implementation of (3).  It is limited to a specific range to avoid excess memory usage.  For comb(50_000, 25_000), it gives a three-fold speedup:

    if (k_long > 20 && k_long > n_long / 3 && n_long <= 100000) {
        PyObject *den = math_factorial(module, k);                 /* den = k! */
        temp = PyNumber_Subtract(n, k);
        Py_SETREF(temp, math_factorial(module, temp));
        Py_SETREF(den, PyNumber_Multiply(den, temp));              /* den *= (n - k)! */
        Py_DECREF(temp);
        Py_SETREF(result, math_factorial(module, n));              /* result = n! */
        Py_SETREF(result, PyNumber_FloorDivide(result, den));      /* result //= (n-k)! */
        Py_DECREF(den);
        return result;
    }

> Can the suggested performance improvements go into 3.8, or should they wait for 3.9?
> It's not clear to me whether a performance improvement after feature freeze is okay or not.

Historically, we've used the beta phase for optimizations, tweaking APIs, and improving docs.  However, I'm in no rush and this can easily wait for 3.9.

My only concern is that the other math functions, except for factorial(), have bounded running times and memory usage, so performance is more of a concern for this function which could end-up being an unexpected bottleneck or being a vector for a DOS attack.  That said, we haven't had any negative reports regarding factorial(), so this may be a low priority.

----------

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