# Binomial coefficient - a lamer's question

• 03-26-2007
balazsbotond
Binomial coefficient - a lamer's question
Hi all,

I'm quite new to programming, and trying to write a c++ program that calculates the binomial coefficient of two numbers. This can be used for calculating the probability of, for example, winning a lottery game. The formula is as follows:
Code:

```  n! -------- (n-k)!k!```
Where ! means the factorial of the number. My problem is that if I want to calculate, say, the number of possible combinations in the state lottery game in my country where you can select 5 numbers out of 90, the program has to deal with VERY large numbers, like 90! which is 1 x 2 x ... x 89 x 90. My idea was that n! is divisible by (n-k)!, so our example then looks like:
Code:

```  90!      1 x 2 x ... x 85 x ... x 90  86 x 87 x 88 x 90 --------- = --------------------------- = ----------------- (90-5)!5!  1 x 2 x ... x 85 x 1 x...x5    1 x 2 x ... x 5```
So I've written a function that returns the product of a number series, like 86-90. It works with smaller numbers but it seems that 86 x ... x 90 is too large for it, even if I set the data type to unsigned long int. The function is:
Code:

```  unsigned long int multiply_from_to (int From, int To) {       int i, Product=1;       for (i=0;i<=To-From;i++) {         Product*=From+i;       }       return Product;   }```
What's wrong? (and sorry for the long post)
• 03-26-2007
balazsbotond
Ok, this was really lame. Product should be unsigned long int too. I've done that but it still doesn't work.
• 03-26-2007
VirtualAce
You are overflowing your data type. You will either have to use a thirdy party library that supports big integers or you will have to use floating point and suffer inaccuracies.
• 03-26-2007
MacGyver
Borland's compiler supports a datatype named __int64. You might find other compilers support long long, or some other way to "fake" a 64-bit number on a 32-bit system.
• 03-26-2007
Rashakil Fol
divide by 1, multiply by 90;
divide by 2, multiply by 89;
divide by 3, multiply by 88;
divide by 4, multiply by 87;
divide by 5, multiply by 86.

This method starts with 90 choose 0 and then transforms it into 90 choose 1, 90 choose 2, ..., 90 choose 5.

Include a check so that coefficients like 90 choose 85 get computed as 90 choose 5, and that way you'll get most out of fixed-with integers.
• 03-26-2007
balazsbotond
Thx
Rashakil Fol,
thanks. That's a really cool solution.

Thanks to the others too!
• 03-26-2007
KONI
Quote:

Originally Posted by balazsbotond
Rashakil Fol,
thanks. That's a really cool solution.

Thanks to the others too!

Be aware that this is only a partial solution though, since you still risk to exceed the maximum integer capacity when dealing with large numbers, since it's takes a while for the divisions to catch up with the multiplications.
• 03-26-2007
balazsbotond
I know, but it still radically reduces the bits I need to do the calculation.
• 03-26-2007
balazsbotond
And I can simplify it even more because n choose k equals n choose n-k, so eg. 100 choose 97 = 100 choose 3.
• 03-26-2007
robatino
If you're willing to compute all the binomial coefficients (n k) for 0 <= k <= n instead of just one, you can do it with Pascal's triangle:

http://en.wikipedia.org/wiki/Pascal's_triangle