Binomial Coefficient - Binomial Coefficient in Programming Languages

Binomial Coefficient in Programming Languages

The notation is convenient in handwriting but inconvenient for typewriters and computer terminals. Many programming languages do not offer a standard subroutine for computing the binomial coefficient, but for example the J programming language uses the exclamation mark: k ! n .

Naive implementations of the factorial formula, such as the following snippet in Python:

def binomialCoefficient(n, k): from math import factorial return factorial(n) // (factorial(k) * factorial(n - k))

are very slow and are useless for calculating factorials of very high numbers (in languages as C or Java they suffer from overflow errors because of this reason). A direct implementation of the multiplicative formula works well:

def binomialCoefficient(n, k): if k < 0 or k > n: return 0 if k > n - k: # take advantage of symmetry k = n - k c = 1 for i in range(1,k+1): c = c * (n - (k - i)) c = c // i return c

(In Python, range(1,k) produces a list from 1 to k-1 and so we need to use k+1 instead.) The example mentioned above can be also written in functional style. The following Scheme example uses recursive definition

Rational arithmetic can be easily avoided using integer division

The following implementation uses all these ideas

(define (binomial n k) ;; Helper function to compute C(n,k) via forward recursion (define (binomial-iter n k i prev) (if (>= i k) prev (binomial-iter n k (+ i 1) (/ (* (- n i) prev) (+ i 1))))) ;; Use symmetry property C(n,k)=C(n, n-k) (if (< k (- n k)) (binomial-iter n k 0 1) (binomial-iter n (- n k) 0 1)))

Another way to compute the binomial coefficient when using large numbers is to recognize that

{n \choose k} = \frac{n!}{k!\,(n-k)!} = \frac{\Gamma(n+1)}{\Gamma(k+1)\,\Gamma(n-k+1)} = \exp(\ln\Gamma(n+1)-\ln\Gamma(k+1)-\ln\Gamma(n-k+1)),

where   denotes the natural logarithm of the gamma function at . It is a special function that is easily computed and is standard in some programming languages such as using log_gamma in Maxima, LogGamma in Mathematica, or gammaln in MATLAB. Roundoff error may cause the returned value to not be an integer.

Read more about this topic:  Binomial Coefficient

Famous quotes containing the words programming and/or languages:

    “If there is a price to pay for the privilege of spending the early years of child rearing in the driver’s seat, it is our reluctance, our inability, to tolerate being demoted to the backseat. Spurred by our success in programming our children during the preschool years, we may find it difficult to forgo in later states the level of control that once afforded us so much satisfaction.”
    —Melinda M. Marshall (20th century)

    “No doubt, to a man of sense, travel offers advantages. As many languages as he has, as many friends, as many arts and trades, so many times is he a man. A foreign country is a point of comparison, wherefrom to judge his own.”
    —Ralph Waldo Emerson (1803–1882)