[RC5] Birthday Paradox

Remi Guyomarch rguyom at mail.dotcom.fr
Tue Mar 24 21:10:27 EST 1998


Greg Hewgill wrote:
> 
> >From Tim Charron:
> >There are 2^30 DPs, however, there are actually 2^97 different points
> >possible.
> 
> Thanks, I see now. Unfortunately, my perl program ran into, uh, precision
> problems when I tried to make it calculate the 50% crossover point with N =
> 2^97 ... it tried to tell me there was no chance of duplicates, ever! :)
> 
> >There's a shortcut to calculate the 50% mark.  When there are "n"
> >possible values, then once k=sqrt(n*pi/2) points are encountered, the
> >chances of a duplicate are 50%.
> 
> What is the derivation for this shortcut? This works for N = 365:
> floor(sqrt(N*pi/2)) = 23, but for N = 2^30, floor(sqrt(N*pi/2)) = 41068,
> which doesn't agree with my perl program's result of 38582. Now, I suspect
> my perl program is affected by accumulated roundoff error for N = 2^30,
> perhaps I'll dig up an arbitrary precision math library to satisfy my
> curiosity.

I've used "bc" with a precision of one hundred digits after decimal
point. Here's the program :

scale = 100;
n = 2^30;
p = 1;
for (i=1; p>0.5; i++) {
  p *= (n-(i-1))/n;
  /* print i,"\t",p,"\n"; */
}
print "\n\n",i,"\t",p,"\n";
quit;

This program outputs :

38583   .49999354249129372190975158091158792424464083210879977911311617\
37925368086956280841106433600859396262

I've tried with n=2^97 and scale=100 but after 7564833 iterations, I've
got this value for "p" :
0.9999999999999998194244514597671235557725989245065327669039649014008026096538155536796292206705437161

-- 
Rémi		Don't waste your computer's time. Distribute it!
			http://www.distributed.net/
	    RC5 cores source code : http://wwwperso.hol.fr/~guyom001/
--
To unsubscribe, send 'unsubscribe rc5' to majordomo at lists.distributed.net
rc5-digest subscribers replace rc5 with rc5-digest



More information about the rc5 mailing list