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)

Ok, this was really lame. Product should be unsigned long int too. I've done that but it still doesn't work.

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.

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.

Start with 1
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.

Rashakil Fol,
thanks. That's a really cool solution.

Thanks to the others too!

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.

I know, but it still radically reduces the bits I need to do the calculation.

And I can simplify it even more because n choose k equals n choose n-k, so eg. 100 choose 97 = 100 choose 3.

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