birthday_paradox_hash_collision_probabilities.cc

// To run: `g++ -O3 calc.cc && ./a.out`.
// Example values to run on are commented out in lines 8..10.

#include <cmath>
#include <iostream>
#include <iomanip>

long double const range = std::pow(2.0, 64);  // std::pow(1.0, 32);  // 1e6;
long double const desired_p_of_collision = 0.01;  // 1e-5;  1e-2;  // 0.5;
long double const desired_log_p = logl(1.0 - desired_p_of_collision);

int main() {
  long double const log_range = logl(range);
  size_t total_drawn = 0u;
  long double log_p = 0.0;
  while (log_p > desired_log_p) {
    ++total_drawn;
    log_p += logl(static_cast<long double>(range - total_drawn)) - log_range;
  }
  std::cout
      << "For range = " << std::fixed << std::setprecision(0) << range << std::setprecision(1)
      << " (log_2(range) = " << logl(range) / logl(2.0) << ')'
      << ", the desired P of collision = " << std::setprecision(6) << desired_p_of_collision << std::setprecision(1)
      << " (-log_10(P of collision) = " << -logl(desired_p_of_collision) / logl(10.0) << ')'
      << ", need to draw " << total_drawn << " numbers." << std::endl;
  long double const actual_total_drawn = total_drawn;  // To use this as a `long double`.
  long double const approximate_total_drawn = sqrt(range * 2 * desired_p_of_collision);
  double const percentage_off = ((std::max(actual_total_drawn, approximate_total_drawn) /
                                  std::min(approximate_total_drawn, actual_total_drawn)) - 1.0) * 100;
  std::cout
      << "The approximation for the number to draw is " << approximate_total_drawn
      << ", and ths number is " << percentage_off << "% off the actual number." << std::endl;
}

For range = 18446744073709551616 (log_2(range) = 64.0), the desired P of collision = 0.010000 (-log_10(P of collision) = 2.0), need to draw 608926878 numbers.
The approximation for the number to draw is 607400100.0, and ths number is 0.3% off the actual number.