<?xml version="1.0" encoding="windows-1252"?>
<node id="962888" title="Re^3: [OT] The statistics of hashing." created="2012-04-01 11:31:52" updated="2012-04-01 11:31:52">
<type id="11">
note</type>
<author id="616540">
moritz</author>
<data>
<field name="doctext">
&lt;p&gt;You'd need a floating-point number with a mantissa of about 128 bits to hold the value of (1-1/2**128)&lt;/p&gt;

&lt;p&gt;Luckily there are other ways to evaluate the expression. If we set &lt;c&gt;x = 1/2**128&lt;/c&gt;, we can do a [http://www.wolframalpha.com/input/?i=Series%5b%281-x%29^n%2C+{x%2C+0%2C+3}%5d|taylor series] to evaluate &lt;c&gt;(1-x)**n&lt;/c&gt; around x = 0 (and since x is very small, it's a good approximation:

&lt;code&gt;
(1 - x)^n = 1 - n * x + 1 / 2 * n * (n - 1) * x ** 2 + ...
&lt;/code&gt;

&lt;p&gt;Where higher orders can be neglected. If you chose an &lt;c&gt;n&lt;/c&gt; that is high enough, you can get non-1 values as the result.

&lt;p&gt;Though I'm not sure if that's really helpful. What you'd really need is the expectation value of the number of collisions (the lambda symbol in [wp://Poisson Distribution], then you could easily calculate everything you wanted. 

&lt;!-- Node text goes above. Div tags should contain sig only --&gt;
&lt;div class="pmsig"&gt;&lt;div class="pmsig-616540"&gt;
[http://perl6.org/|Perl 6 - second systems done right]
&lt;/div&gt;&lt;/div&gt;</field>
<field name="root_node">
962802</field>
<field name="parent_node">
962876</field>
</data>
</node>
