[issue37295] Possible optimizations for math.comb()

[Mark Dickinson]

Mark Dickinson <dickinsm at gmail.com> added the comment:

That computation of the shift can be simplified to require only one popcount operation. With F and Finv as before:


def comb_small(n, k):
    assert 0 <= k <= n <= Nmax
    return (F[n] * Finv[k] * Finv[n-k] % 2**64) << (k ^ n ^ (n-k)).bit_count()

----------

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