Thread: Binomial coefficient - a lamer's question

  1. #1
    Enthusiastic Beginner balazsbotond's Avatar
    Join Date
    Mar 2007
    Location
    Érd, Hungary
    Posts
    20

    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)

  2. #2
    Enthusiastic Beginner balazsbotond's Avatar
    Join Date
    Mar 2007
    Location
    Érd, Hungary
    Posts
    20
    Ok, this was really lame. Product should be unsigned long int too. I've done that but it still doesn't work.

  3. #3
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.

  4. #4
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    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.

  5. #5
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    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.
    There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.

  6. #6
    Enthusiastic Beginner balazsbotond's Avatar
    Join Date
    Mar 2007
    Location
    Érd, Hungary
    Posts
    20

    Thx

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

    Thanks to the others too!

  7. #7
    Lean Mean Coding Machine KONI's Avatar
    Join Date
    Mar 2007
    Location
    Luxembourg, Europe
    Posts
    444
    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.

  8. #8
    Enthusiastic Beginner balazsbotond's Avatar
    Join Date
    Mar 2007
    Location
    Érd, Hungary
    Posts
    20
    I know, but it still radically reduces the bits I need to do the calculation.

  9. #9
    Enthusiastic Beginner balazsbotond's Avatar
    Join Date
    Mar 2007
    Location
    Érd, Hungary
    Posts
    20
    And I can simplify it even more because n choose k equals n choose n-k, so eg. 100 choose 97 = 100 choose 3.

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Alice....
    By Lurker in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 06-20-2005, 02:51 PM
  2. Debugging question
    By o_0 in forum C Programming
    Replies: 9
    Last Post: 10-10-2004, 05:51 PM
  3. Question about pointers #2
    By maxhavoc in forum C++ Programming
    Replies: 28
    Last Post: 06-21-2004, 12:52 PM
  4. A binomial queue (binomial tree) question.
    By NightWalker in forum C Programming
    Replies: 2
    Last Post: 10-27-2003, 08:25 AM
  5. Question...
    By TechWins in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 07-28-2003, 09:47 PM