Complexity of scipy.special.binom?

Question

According to this answer, there are two functions to calculate the binomial coefficient, also known as "N choose K". One of them is scipy.special.binom().

Where is this function implemented? All I know is that it is a ufunc.

Furthermore, what is the time complexity of scipy.special.binom()?

Answer 1

The source can be found on Github in orthogonal_eval.pxd.

In the integer case, the complexity is O(k).

kx = floor(k)
if k == kx and (fabs(n) > 1e-8 or n == 0):
    # Integer case: use multiplication formula for less rounding error
    # for cases where the result is an integer.
    #
    # This cannot be used for small nonzero n due to loss of
    # precision.

    nx = floor(n)
    if nx == n and kx > nx/2 and nx > 0:
        # Reduce kx by symmetry
        kx = nx - kx

    if kx >= 0 and kx < 20:
        num = 1.0
        den = 1.0
        for i in range(1, 1 + <int>kx):
            num *= i + n - kx
            den *= i
            if fabs(num) > 1e50:
                num /= den
                den = 1.0
        return num/den