Estimate the collision rate of k keys in space n

birthday.rb

# Approximates the chance of at least one collision in a random
# distribution of k items across n possible IDs.  Adapted from 
# Karsten's approximate calculator at http://tinyurl.com/5zt6ol
def collision_probability( k, n )
  1 - Math.exp((-k ** 2) / ( 2.0 * n).to_f)
end

# The odds of two people having the same birthday are slightly
# greater than 50% if you have 23 or more people.
puts collision_probability( 23, 365 ) # => 0.515509538061517

# The 0.1% column from http://en.wikipedia.org/wiki/Birthday_attack
puts collision_probability( 2.9 * (10**3), 2**32 ) # => 0.000978573740689215
puts collision_probability( 1.9 * (10**8), 2**64 ) # => 0.000978013893024765
puts collision_probability( 8.3 * (10**17), 2**128 ) # => 0.00101173542309951
puts collision_probability( 1.5 * (10**37), 2**256 ) # => 0.000971097142138055
puts collision_probability( 2.8 * (10**56), 2**384 ) # => 0.000994378477961022
puts collision_probability( 5.2 * (10**75), 2**512 ) # => 0.00100785943502502