Efficient Binomial Coefficient calculation

[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 Expand


(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 Expand


(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">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.