Efficient Binomial Coefficient calculation

Featuring the Dragonfly web framework

Efficient Binomial Coefficient calculation

Postby TedWalther » Fri Jun 06, 2014 10:22 pm

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.
TedWalther
 
Posts: 602
Joined: Mon Feb 05, 2007 1:04 am
Location: Abbotsford, BC

Return to So, what can you actually DO with newLISP?

Who is online

Users browsing this forum: No registered users and 1 guest

cron