Chris's Wiki :: blog/programming/BcForBirthdayParadox Commentshttps://utcc.utoronto.ca/~cks/space/blog/programming/BcForBirthdayParadox?atomcommentsDWiki2006-02-15T04:42:07ZRecent comments in Chris's Wiki :: blog/programming/BcForBirthdayParadox.By DanielMartin on /blog/programming/BcForBirthdayParadoxtag:CSpace:blog/programming/BcForBirthdayParadox:02abe4468051cff042557309fdf085dcc6bf1210DanielMartin<div class="wikitext"><p>Incidentally, a rough estimate of the error in the approximation I gave is that if the approximation yields <code>x</code>, then the error is less than <code>x^2</code>. Essentially all of this error is coming from the approximation <code>-ln(x) ~=~ 1-x</code>; Stirling's approximation holds to within 1% in the numbers we're dealing with.</p>
<p>If we remove that bit of approximating, we get:</p>
<pre>
perl -le 'use bignum;sub xe{$_[0]*log($_[0])+log(atan2(1,1)*8*$_[0])/2
+ log(1+1/(12*$_[0]));} my($m,$n,$r)=map {eval "use bignum;$_"}
@ARGV;print 1-exp(xe($m-$n)+xe($m-$r)-xe($m)-xe($m-$n-$r))'
'2**64' '3*(10**6)' '1*(10**6)'
</pre>
<p>Which works well over the range of your chart. Of course, there's still a range where it stops working - try 128 bit session ids with the same 3 million and 1 million numbers, and you get a probability of guessing a valid session id of -29.</p>
</div>2006-02-15T04:42:07Z