CODEWITHSUNDEEP
pythonnumpydynamic-programming
GARVIT TYAGI
GARVIT TYAGI

Reputation: 25

printing binomial coefficient using numpy

Binomial coefficient for given value of n and k(nCk) using numpy to multiply the results of a for loop but numpy method is returning the memory location not the result pls provide better solution in terms of time complexity if possible. or any other suggestions. 

import time
import numpy
def binomialc(n,k):
    return 1 if k==0 or k==n else numpy.prod((n+1-i)/i for i in range(1,k+1))
starttime=time.perf_counter()
print(binomialc(600,298))
print(time.perf_counter()-starttime)

Upvotes: 0

Views: 5568

Answers (1)

norok2
norok2

Reputation: 26886

You may want to use: scipy.special.binom()

or, since Python 3.8: math.comb()

EDIT

I am not quite sure why you would not want to use SciPy but you are OK with NumPy, as SciPy is a well-established library from essentially the same folks developing NumPy.

Anyway, here a couple of other methods:

  • using math.factorial:
import math


def binom(n, k):
    return math.factorial(n) // math.factorial(k) // math.factorial(n - k)
  • using prod() and math.factorial() (theoretically more efficient, but not in practice):
def prod(items, start=1):
    for item in items:
        start *= item
    return start


def binom_simplified(n, k):
    if k > n - k:
        return prod(range(k + 1, n + 1)) // math.factorial(n - k)
    else:
        return prod(range(n - k + 1, n + 1)) // math.factorial(k)
  • using numpy.prod():
import numpy as np


def binom_np(n, k):
    return 1 if k == 0 or k == n else np.prod([(n + 1 - i) / i for i in range(1, k + 1)])

Speed-wise, scipy.special.binom() is the fastest by far and large, but if you need the exact value also for very large numbers, you may prefer binom() (somewhat surprisingly even over math.comb()).

%timeit scipy.special.binom(600, 298)
# 1000000 loops, best of 3: 1.56 µs per loop
print(scipy.special.binom(600, 298))
# 1.3332140543730587e+179

%timeit math.comb(600, 298)
# 10000 loops, best of 3: 75.6 µs per loop
print(math.binom(600, 298))
# 133321405437268991724586879878020905773601074858558174180536459530557427686938822154484588609548964189291743543415057988154692680263088796451884071926401665548516571367537285901600

%timeit binom(600, 298)
# 10000 loops, best of 3: 36.5 µs per loop
print(binom(600, 298))
# 133321405437268991724586879878020905773601074858558174180536459530557427686938822154484588609548964189291743543415057988154692680263088796451884071926401665548516571367537285901600

%timeit binom_np(600, 298)
# 10000 loops, best of 3: 45.8 µs per loop
print(binom_np(600, 298))
# 1.3332140543726893e+179

%timeit binom_simplified(600, 298)
# 10000 loops, best of 3: 41.9 µs per loop
print(binom_simplified(600, 298))
# 133321405437268991724586879878020905773601074858558174180536459530557427686938822154484588609548964189291743543415057988154692680263088796451884071926401665548516571367537285901600

Upvotes: 4

Related Questions