[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