[RC5] Birthday Paradox

Greg Hewgill gregh at lightspeed.net
Sat Mar 21 23:03:15 EST 1998


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