Calculating cumulative binomial distribution probability

by kiteason13. October 2013 08:15

On my current project, we recently came across the problem of calculating cumulative binomial distribution probability. The formula for this is relatively straightforward:


Any decent programmer could code this up in short order.  In fact we used the function provided by Math.Net.

But there's a problem. Although the final results are modest numbers, some of the intermediate results are... well the term 'astronomical' is too small a word. Our failing case involved calculating 12798! (12798 factorial) - which in case you didn't know is 12798 * 12797 * 12796 ... * 2.  Yeah, that's a big number. According to Wolfram Alpha it works out at


Compare that to the estimated number of protons in the universe, which is a mere 10^80.

I had a think about this, and I wondered: how is Excel doing this?  Excel has a BINOM.DIST function which calculates for large inputs fine – and fairly quickly.  As luck would have it, Microsoft have actually published the logic they use, here:

Kudos to them for both developing this algorithm, and publishing it.

I was able to re-implement this in F# relatively easily, and our binomial statistical tests now work just fine.  I didn’t bother to switch to the special algorithm only for large inputs (as Excel does) as for our purposes the results don’t appear to be affected by the different approaches.

Since then I’ve refined the code a bit to make it less repetitive (and not proprietary!).  Here is the entire function.

(Full project with units tests here:

If anyone fancies adding a more comprehensive set of tests, and incorporating the code into Math.Net, please feel free.

Tags: , ,

You're looking a little flushed

by kiteason8. October 2013 12:52

Recently someone raised the issue of how you might use active patterns to represent the various named Poker hands.  You can’t do it directly, as there are - depending on exactly how you count them - ten named hands.  You can only have 7 tags in a ‘complete’ active pattern.

I decided to experiment with partial active patterns to represent the hand types.  It didn’t end up as the snappy, fssnip-able example I was hoping for.  (Full code here.)  But it was very instructive.

The named poker hands are, in descending order of winning-power:

  • Royal Flush
  • Straight Flush
  • Four of a Kind
  • Full House
  • Flush
  • Straight
  • Three of a Kind
  • Two Pair
  • One Pair
  • High Card

The definitions I’ve used – and many of the test cases – are here:

So – let the cards speak!  First, discriminated unions (DUs) to represent a suit:

…and a ‘rank’ (e.g. Ace, 10 of…):

(By the way I’ve been told off by @lu_a_jalla for using unicode characters.  Sorry, but they’re just so cute - I couldn’t resist it.)

Types to represent a card and a hand of cards:

And we’ll also need some utility functions which summarise the contents of a set of cards in various ways.  I won’t list them all but you’ll get the idea from these:

Now we can write some partial active patterns to work out the type of a hand.  Each partial active pattern either returns some specific tag (e.g. RoyalFlush), or 'None’. 

Here’s the one for Royal Flush:

…and for Straight Flush:

(Actually I suspect you could get away with not distinguishing between those two as ‘Royal’ is a special case of ‘Straight’.  But we’ll ignore that.)

Here’s the one for Four of a Kind:

You get the idea.  It’s worth saying that these partial active patterns need to be matched in order, because some of the higher hands would also be matched by lower hands’ active patterns.

Now we can get to the real business of Poker: deciding which of two hands wins.  Let’s have yet another DU to represent that:

You’ll see that this DU has a static member which can determine the outcome of comparing two card ranks.  (I initially started off by implementing IComparable, but that took me down the rabbit-hole of having to implement IEquatable and various operators.  So I backed out of that one!)  This member is used when we can determine a winner based on one card from each hands.  Hand-level comparisons are handled like this:

It’s a long gist, but worth it to see how this approach plays out.  You’ll see that I work down the named hands, in descending order of ‘power’.  For each hand I deal with the cases where a hand is pitted against a hand of same type (e.g. Flush with Flush), because for this case we need to go into detail about the cards within the hand.  Then I deal with the cases where we know a hand wins because it is pitted against an inferior hand.

One other subtlety: if you’re eagle eyed you might question why CompareHands takes arguments of Hand rather than arrays of cards.  The reason is because in lines like this:

…if we pass in Hand (whose constructor mandates there there are five cards in the hand) we know we are not going to hit an out of range index looking at the 0th card.

If you look at the source in GitHub you’ll see that I’ve also implemented a ‘showdown’ – in other words comparing a number of hands to determine an overall winner.  But that’s something for another post.

I was impressed by the ability of DUs and partial active patterns to model cards, hands, and the interactions between them.  But I’d be interested to hear if anyone has a more concise solution.

Tags: , , ,

About the author

F# bore

Month List

Page List