long double vs long int

I'm doing a program that calculates the probability of lotteries. Specification is choose 5 numbers out of 47 and 1 out of 27

So I did the following:

#include <iostream>

long int choose(unsigned n, unsigned k);
long int factorial(unsigned n);

int main(){
    using namespace std;
    long int regularProb, megaProb;
    regularProb = choose(47, 5);
    megaProb = choose(27, 1);
    cout << "The probability of the correct number is 1 out of " << (regularProb * megaProb) << endl;

    return 0;
}

long int choose(unsigned n, unsigned k){    
    return factorial(n) / (factorial(k) * factorial(n-k));
}

long int factorial(unsigned n){
    long int result = 1;
    for (int i=2;i<=n;i++) result *= i;
    return result;
}

However the program doesn't work. The program calculates for 30 seconds, then gives me Process 4 exited with code -1,073,741,676 I have to change all the long int to long double, but that loses precision. Is it because long int is too short for the big values? Though I thought long int nowadays are 6开发者_JS百科4bit? My compiler is g++ win32 (64bit host).

Whether long is 64-bit or not depends on the model. Windows uses a 32-bit long. Use int64_t from <stdint.h> if you need to ensure it is 64-bit.

But even if long is 64-bit it is still too small to hold factorial(47).

47!  == 2.58623242e+59
2^64 == 1.84467441e+19

although ₄₇C₅ is way smaller than that.

You should never use _nC_r == n!/(r! (n-r)!) directly do the calculation as it overflows easily. Instead, factor out the n!/(n-r)! to get:

       47 * 46 * 45 * 44 * 43
  C  = ----------------------
47 5    5 *  4 *  3 *  2 *  1

this can be managed even by a 32-bit integer.

BTW, for @Coffee's question: a double only has 53-bits of precision, where 47! requires 154 bits. 47! and 42! represented in double would be

47! = (0b10100100110011011110001010000100011110111001100100100 << 145) ± (1 << 144)
42! = (0b11110000010101100000011101010010010001101100101001000 << 117) ± (1 << 116)

so 47! / (42! × 5!)'s possible range of value will be

      0b101110110011111110011 = 1533939                       53 bits
                                                              v
max = 0b101110110011111110011.000000000000000000000000000000001001111...
val = 0b101110110011111110010.111111111111111111111111111111111010100...
min = 0b101110110011111110010.111111111111111111111111111111101011010...

that's enough to get the exact value ₄₇C₅.

to use 64bit long, you should use long long. (as mentioned here)

KennyTM has it right, you're going to overflow no matter what type you use. You need to approach the problem more smartly and factor out lots of work. If you're ok with an approximate answer, then take a look at Stirling's approximation:

Ln(n!) ~ n Ln(n) - n

So if you have

n!/(k!*(n-k)!)

You could say that's

e(ln(n!/(k!*(n-k)!)))

which after some math (double check to make sure I got it right) is

e(n*ln(n)-k*ln(k)-(n-k)*ln(n-k))

And that shouldn't overflow (but it's an approximate answer)

It's easy to calculate binomial coefficients up to 47C5 and beyond without overflow, using standard unsigned long 32-bit arithmetic. See my response to this question: https://math.stackexchange.com/questions/34518/are-there-examples-where-mathematicians-needs-to-calculate-big-combinations/34530#comment-76389