calculate size required for a random id to avoid collisions

random_id_size.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# collision chance for random id\n",
    "\n",
    "https://en.wikipedia.org/wiki/Birthday_problem#Approximations\n",
    "\n",
    "$p(n) \\approx 1 - e^{-n^{2}/2d}$\n",
    "\n",
    "Where $p(n)$ is the probability of a collision given n generated ids, and d is the number of possible ids.\n",
    "\n",
    "To calculate required d in terms of p(n) and n:\n",
    "\n",
    "$1 - p(n) \\approx e^{-n^{2}/2d}$\n",
    "\n",
    "$\\log(1 - p(n)) \\approx \\frac{-n^{2}}{2d}$\n",
    "\n",
    "$2d \\approx -n^{2}/\\log(1 - p(n))$\n",
    "\n",
    "$d \\approx -n^{2}/2\\log(1 - p(n))$\n",
    "\n",
    "To compute bit-length\n",
    "\n",
    "$\\log_2 d \\approx \\log_2(-n^{2}/2\\log[1 - p(n)])$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-04-19T18:56:07.997329",
     "start_time": "2017-04-19T18:56:07.984313"
    },
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def prob(n, d):\n",
    "    return 1 - math.exp(- n * n / (2 * d))\n",
    "\n",
    "def bit_len(n, p):\n",
    "    if p > 1:\n",
    "        p = 1.0 / p\n",
    "    return int(math.ceil(math.log(-n*n/(2*math.log(1 - p)), 2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2017-04-19T18:56:09.595066",
     "start_time": "2017-04-19T18:56:09.585117"
    },
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "83"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bit_len(100e6, 1e9)  # 100 million items, with collision rate of 1 in 1 billion"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "hide_input": false,
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}