Skip to content

Instantly share code, notes, and snippets.

@zadam
Created October 28, 2017 15:25
Show Gist options
  • Save zadam/6474221007e27705b3bde0a3a9323a84 to your computer and use it in GitHub Desktop.
Save zadam/6474221007e27705b3bde0a3a9323a84 to your computer and use it in GitHub Desktop.
Calculate birthday paradox (chance of collision) for very large numbers
#!/usr/bin/python
# This is used for calculating of birthday paradox for large values
# We're using approximation explained here: http://preshing.com/20110504/hash-collision-probabilities/
# Beware that approximation isn't very precise at smaller params N and K, but gets more precise with large numbers
# see https://docs.python.org/3/library/decimal.html#module-decimal
from decimal import *
# setting decimal precision
getcontext().prec = 30
# this example setup should give roughly 1 in 100 000 000 chance of collision
N = Decimal(2 ** 64) # number of possible values (number of days in birthday paradox)
K = Decimal(607401) # number of chosen values (number of people in birthday paradox)
exponent = (-K * (K - 1) / (2 * N))
unique_probability = exponent.exp(); # Return the value of the (natural) exponential function e**x at the given number.
collision_probability = 1 - unique_probability
print('Probability of having a collision in {0} hashes in the space of {1} possible hashes is {2}'.format(K, N, collision_probability));
@arieroos
Copy link

Thanks

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment