Efficient Binomial Coefficient calculation
Posted: 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:
Implementing that in the straightforward way quickly makes you run out of stack space. This implementation is 7 times faster:
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.
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))))
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)))
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.