Author rhettinger
Recipients PedanticHacker, Stefan Pochmann, mark.dickinson, mcognetta, rhettinger, serhiy.storchaka, tim.peters
Date 2022-01-13.03:42:10
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1642045330.14.0.612366836289.issue37295@roundup.psfhosted.org>
In-reply-to
Content
def comb64(n, k):
    'comb(n, k) in multiplicative group modulo 64-bits'
    return (F[n] * Finv[k] * Finv[n-k] & (2**64-1)) << (S[n] - S[k] - S[n - k])

def comb_iterative(n, k):
    'Straight multiply and divide when k is small.'
    result = 1
    for r in range(1, k+1):
        result *= n - r + 1
        result //= r
    return result

def C(n, k):
    k = min(k, n - k)
    if k == 0: return 1
    if k == 1: return n
    if k < len(k2n) and n <= k2n[k]:  return comb64(n, k) # 64-bit fast case
    if k == FixedJ and n <= Jlim:  return KnownComb[n]    # Precomputed diagonal
    if k < 10: return comb_iterative(n, k)                # Non-recursive for small k  
    j = FixedJ if k > FixedJ and n <= Jlim else k // 2
    return C(n, j) * C(n-j, k-j) // C(k, j)               # Recursive case
History
Date User Action Args
2022-01-13 03:42:10rhettingersetrecipients: + rhettinger, tim.peters, mark.dickinson, serhiy.storchaka, PedanticHacker, mcognetta, Stefan Pochmann
2022-01-13 03:42:10rhettingersetmessageid: <1642045330.14.0.612366836289.issue37295@roundup.psfhosted.org>
2022-01-13 03:42:10rhettingerlinkissue37295 messages
2022-01-13 03:42:10rhettingercreate