Calculation of the probability of birth by large numbers

Question

The probability that two people have the same birthday in a room full of n , 1-p people . Where:

p = 365! / 365^n(365 - n)! 

Obviously the numbers will be too large to solve this equation, what is the creative way to do this?

I already solved it differently with the help of modeling, but I decided that the formula could be more elegant.

Answer 1

You can use 365! / (365-n)! = 365 * 364 * ... * (365- (n-1))

So, to calculate this member (let it be A = 365! / (365-n)!), You can simply do the following numbers:

 unsinged double A=1; // to make sure there is no overflow for(int i=0;i<n;i++) A*=365-i; 

Let's take one more step: p = A / 365 ^ n = (364 * 363 * ... * (365- (n-1))) / 365 ^ (n-1) = 364/365 * 363/365 *. .. (365- (n-1)) / 365.

therefore p can be calculated as follows:

 unsigned double p=1; for(int i=0;i<n;i++) p*= (365-i)/365.0; 

in linear time

I think this should work: P

Answer 2

Holly Macaroni! What a show!

In any case, the correct way to compute such things with large intermediate elements is log () them

 p = exp(log(p)) log(p) = log(365!) - n*log(365) - log((365 - n)!) 

For the factorial, use the Gamma function, G (n + 1) = n !, and the C-library has a very convenient function that calculates log (G (x)): lgamma (x)

More loops, long doubles, bignum libraries, overflows ...

code

 #include <math.h> #include <stdio.h> double b(int n) { double l = lgamma(365.0 + 1.0) - (double)n * log(365.0) - lgamma(365.0 - (double)n + 1.0); return exp(l); } int main() { double p = b(20); printf("%e %e\n", p, 1.0 - p); return 0; } 

Answer 3

You do not want to calculate the full factorial. Instead, calculate each term and multiply it by the result.

The likelihood that you do not share your birthday with:

• 1 person: 364/365
• 2 people: 364/365 * 363/365
• 3 people: 364/365 * 363/365 * 362/365
• ...

Given this, you compute p as follows.

 int n = 30; int i; double p = 1; for (i = 1; i < n; i++) { p *= (365 - i) / 365.0; printf("i=%d, p=%f\n", i, 1-p); } 

Answer 4

I would write a function that looks like this:

 double p(int n){ double res = 1; while (n>0){ res *= (365 - (n--))/365.0; } return res; } 

Answer 5

Another solution (approximation):

The probability that two people do not have the same birthday is 364/365. In a room containing n people, there are C (n, 2) = n (n - 1) / 2 pairs of people. So:

 p(n) = 364/365 ^ (n * (n-1)/2) 

And for values ​​greater than n = 100 , you can safely use the following table:

 np(n) 1 0.0% 5 2.7% 10 11.7% 20 41.1% 23 50.7% 30 70.6% 40 89.1% 50 97.0% 60 99.4% 70 99.9% 100 99.99997% 200 99.9999999999999999999999999998% 300 (100 − (6×10−80))% 350 (100 − (3×10−129))% 365 (100 − (1.45×10−155))% 366 100% 367 100% 

Answer 6

tgamma(n+1) very close to n! . There is no need to loop hundreds of times, which can reduce accuracy, since each * , / loses a fraction accurate to bits with each iteration.

 #include <stdio.h> #include <stdlib.h> #include <math.h> #include <float.h> long double fact(int n) { return roundl(tgammal(n + 1)); } double bd_prob(int n) { return fact(365)/(powl(365,n)*fact(365-n)); } int main(void){ // No problem with 365! printf("fact(365) %Le\n", fact(365)); // No problem with 365 to the 365 power printf("365^365 %Le\n", powl(365, 365)); printf("prob(22) %f\n", bd_prob(22)); exit(EXIT_SUCCESS); } 

Output

 fact(365) 2.510413e+778 365^365 1.725423e+935 prob(22) 0.524305