probablity.py

#!/usr/bin/python3
from math import sqrt, log as ln, exp
d, n = 2**32, 1000000
k = sqrt(2*d*ln(2)) + (3-2*ln(2))/6 + (9-4*ln(2)**2) / (72*sqrt(2*d*ln(2))) - 2*(ln(2)**2)/(135*d)
p = 1 - exp(-0.5 * k * (k - 1) / d)
q = n * (n - 1.0) / 2.0 * (1.0 / d)
print('hash bits: %d, samples: %d' % (ln(d)/ln(2), n))
print('precise 0.5 collision probability at %d' % k)
print('checking exponential formula (should be ~ 0.5): %f' % p)
print('square root approximation: %d (%.2f%% precise)' % (sqrt(d), sqrt(d)*100/k) )
print('expected number of collisions: %f' % q)

'''
hash bits: 32, samples: 1000000
precise 0.5 collision probability at 77163
checking exponential formula (should be ~ 0.5): 0.499998
square root approximation: 65536 (84.93% precise)
expected number of collisions: 116.415205
'''