long double vs long int

Question

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 64bit? My compiler is g++ win32 (64bit host).

The cause is : data overflowwww... – Nawaz May 10 '11 at 15:55 — Nawaz, May 10 '11 at 15:55

kennytm · Accepted Answer · 2011-05-10T16:46:17.220

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₅.

Insightful question for ultimatebuster: what is the magnitude of the error you introduce if you switch to double? — Coffee on Mars, May 10 '11 at 16:01
This is true, you will need to do some simplification math to calculate the probabilities rather than doing the full factorial calculation, since this will overflow just about anything — Dan F, May 10 '11 at 16:02
+1 Why throw more and more bits at a problem when a modicum of intelligence mixed with a smattering of maths gets the job done. — David Heffernan, May 10 '11 at 16:06

score 3 · Answer 2 · edited May 23 '17 at 12:25

3

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

edited May 23 '17 at 12:25

Community

1
1

answered May 10 '11 at 15:54

Cédric Julien

78,516
15
127
132

3

Indeed -- `long` is platform-dependent and always 32-bit on Windows. `long long` will work in this case but it's preferred to use `std::int64_t` from ``/`` – Cory Nelson May 10 '11 at 15:58

score 0 · Answer 3 · answered May 10 '11 at 19:14

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)

score 0 · Answer 4 · edited Apr 13 '17 at 12:19

0

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

edited Apr 13 '17 at 12:19

Community

1
1

answered May 10 '11 at 19:38

TonyK

16,761
4
37
72

long double vs long int

4 Answers4