from timeit import repeat from math import comb, factorial from operator import mul def factorials(n, k): return factorial(n) // (factorial(k) * factorial(n-k)) def mycomb(n, k): k = min(k, n-k) if k < 0: return 0 if k == 0: return 1 return myprod(factors(n, k)) def myprod(xs): # Just a fast way in Python, would do it differently in C. it = iter(xs) xs += map(mul, it, it) return xs[-1] def factors(n, k): factors = list(range(n, n - k, -1)) prime = bytearray([1]) * (k + 1) for p in range(2, k + 1): if not prime[p]: continue for m in range(p*p, k+1, p): prime[m] = 0 e = k // p P = p while e: for i in range(n % P, e * P, P): factors[i] //= p e //= p P *= p return factors def test(func): for n in range(201): for k in range(n+1): expect = comb(n, k) result = func(n, k) assert result == expect, (n, k, expect, result) test(mycomb) n = 100_000 k = n // 2 funcs = [ comb, factorials, mycomb, factors, ] for _ in range(3): expect = None for func in funcs: def run(): global result result = func(n, k) t = min(repeat(run, number=1)) if expect is None: expect = result print('%6.1f ms ' % (t * 1e3), func.__name__, result == expect) print()