0
$\begingroup$

With the knowledge that the probability of a hash collision is (see: Hash Collision Probabilities):

1 - e^((-k * (k - 1)) / (2 * n))

Where k is the number of input values and n is the number of possible hash values. I want to find the solution for n, given the probability of collisions is z:

1 - e^((-k * (k - 1)) / (2 * n)) - z = 0

Utilizing Mathematica, I entered:

Reduce[1 - e^((-k*(k-1))/(2*n)) - z == 0, n]

Output:

C[1] \[Element] Integers
&& -1 + z != 0
&& ((n != 0 && (k == 0 || k == 1) && z == 0)
    || (2 I \[Pi] C[1] + Log[1/(1 - z)] != 0 && (-1 + k) k != 0
        && n == ((-1 + k) k)/(2 (2 I \[Pi] C[1] + Log[1/(1 - z)]))))

Now, I'm not sure what value to use for C[1] and the meaning of 'I'. I need to translate the equation into C code.

$\endgroup$
0
$\begingroup$

I wonder if $e$ should not be $E$. In any manner, if you type

    Solve[1 - E^((-k*(k-1))/(2*n)) - z == 0, n]

you should get $$n=-\frac{(k-1) k}{2 \log (1-z)}$$ which is a real number. Round it the way you want.

$\endgroup$
  • $\begingroup$ I must be entering 'E' incorrectly as it always results in a complex number for me. How do I enter 'E' in mathematica? $\endgroup$ – Coder Oct 17 '15 at 4:20
  • $\begingroup$ I even tried: Solve[1 - Exp[(-k * (k - 1)) / (2*n)] - z == 0, n] and get: {{n -> ConditionalExpression[((-1 + k) k)/( 2 (2 I [Pi] C[1] + Log[1/(1 - z)])), C[1] [Element] Integers]}} $\endgroup$ – Coder Oct 17 '15 at 4:27
  • $\begingroup$ I cannot tell you more since I do not have Mathematica (even if I know a little). Did you put somewhere restrictions on $k,n,z$ prior to the Solve command ? I suggest you close your session and just type the command. Please, let me know. $\endgroup$ – Claude Leibovici Oct 17 '15 at 4:37
0
$\begingroup$

If I instead use Solve and limit the domain to Reals:

Solve[1-Exp[-k(k-1)/(2n)]-z==0, n, Reals]

I get:

$$n = \frac{-k + k^2}{2log(\frac{1}{1 - z})}$$

Where (0 < k < 1 && 0 < z < 1) || (0 < k < 1 && z < 0) || (k > 1 && 0 < z < 1) || (k > 1 && z < 0) || (k < 0 && 0 < z < 1) || (k < 0 && z < 0)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.