Efficient Binomial Coefficient calculation

Featuring the Dragonfly web framework
Locked
TedWalther
Posts: 608
Joined: Mon Feb 05, 2007 1:04 am
Location: Abbotsford, BC
Contact:

Efficient Binomial Coefficient calculation

Post by TedWalther »

I propose this for addition to the Code Snippets or Code Patterns document.

The binomial coefficient shows you how many unique combinations of k objects you can derive from a set containing n objects.

The standard way to calculate the binomial is like this: n!/k!(n-k)!
The implementation looks like this:

Code: Select all

(define (binomial-coefficient n k)
  (/ (factorial n) (* (factorial k) (factorial (- n k))))
Implementing that in the straightforward way quickly makes you run out of stack space. This implementation is 7 times faster:

Code: Select all

(define (binomial-coefficient n k)
  (if (> k n)
    0
    (let (r 1L)
      (for (d 1 k)
        (setq r (/ (* r n) d)) (-- n))
      r)))
It is also bignum friendly; you aren't limited by the size of integer, even if you put integers in as arguments; the function auto-converts to bignum for you.

This faster algorithm was translated from C code found here:

http://blog.plover.com/math/choose.html

It is based on algorithm found in "Lilavati", a treatise on arithmetic written about 850 years ago in India. The algorithm also appears in the article on "Algebra" from the first edition of the Encyclopaedia Britannica, published in 1768.
Cavemen in bearskins invaded the ivory towers of Artificial Intelligence. Nine months later, they left with a baby named newLISP. The women of the ivory towers wept and wailed. "Abomination!" they cried.

Locked