math module's comb and perm could be faster
The following code improves the performance of math.comb and math.perm. For comb, we do occasional divisions to cancel the working fraction. This is faster than either always cancelling or never cancelling. For perm, we build the product using binary splitting like the code I wrote a long time ago for factorial. This makes multiplicands more equal in bitsize which is faster.
On my computer the performance of computing comb/perm with 0 <= k <= n <= 1000 is as follows (in seconds):
comb | perm | |
---|---|---|
cpython | 19 | 16 |
pypy old | 7 | 12 |
pypy patch | 6 | 6 |
I provide the following changes under the "MIT license".
def comb(n, k, /):
"""
Number of ways to choose k items from n items without repetition and without order.
Evaluates to n! / (k! * (n - k)!) when k <= n and evaluates
to zero when k > n.
Also called the binomial coefficient because it is equivalent
to the coefficient of k-th term in polynomial expansion of the
expression (1 + x)**n.
Raises TypeError if either of the arguments are not integers.
Raises ValueError if either of the arguments are negative.
"""
n = index(n)
k = index(k)
if n < 0:
raise ValueError("n must be a non-negative integer")
if k < 0:
raise ValueError("k must be a non-negative integer")
if k > n:
return 0
k = min(k, n-k)
if k == 0:
return 1
num, den = n, 1
for i in range(1, k):
num *= n - i
den *= i + 1
if i&15 == 0:
num //= den
den = 1
return num // den
def perm(n, k=None, /):
"""
Number of ways to choose k items from n items without repetition and with order.
Evaluates to n! / (n - k)! when k <= n and evaluates
to zero when k > n.
If k is not specified or is None, then k defaults to n
and the function returns n!.
Raises TypeError if either of the arguments are not integers.
Raises ValueError if either of the arguments are negative.
"""
n = index(n)
if k is None:
k = n
else:
k = index(k)
if n < 0:
raise ValueError("n must be a non-negative integer")
if k < 0:
raise ValueError("k must be a non-negative integer")
if k > n:
return 0
if k <= 100:
res = 1
for x in range(n, n - k, -1):
res *= x
return res
gap = max(100, k >> 7)
def _prod_range(low, high):
if low + gap >= high:
t = 1
for i in range(low, high):
t *= i
return t
mid = (low + high) >> 1
return _prod_range(low, mid) * _prod_range(mid, high)
return _prod_range(n - k + 1, n + 1)