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()