Technical interview: Estimating the number pi

estimating_pi.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "π is 😋\n",
    "----\n",
    "<br>\n",
    "<center><img src=\"http://weknowmemes.com/wp-content/uploads/2014/03/pi-meme-1.jpg\" width=\"400\"/></center>\n",
    "<br>\n",
    "The number π is the ratio of a circle's circumference to its diameter.\n",
    "<br>\n",
    "<center><img src=\"https://upload.wikimedia.org/wikipedia/commons/thumb/3/36/Pi_eq_C_over_d.svg/220px-Pi_eq_C_over_d.svg.png\" width=\"300\"/></center>\n",
    "\n",
    "Being an irrational number, π cannot be expressed exactly as a fraction.\n",
    "\n",
    "It is can be approximated as:\n",
    "\n",
    "- 3\n",
    "- 3.14\n",
    "- 3.14159\n",
    "- 22/7\n",
    "- 333/106"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "### How can we estimate π if the only tool we have at disposal is a good random number generator?\n",
    "\n",
    "\n",
    "1. First, whiteboard a complete solution.\n",
    "2. Then, code your solution to see if it works."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "<details><summary>\n",
    "Click here for a small hint…\n",
    "</summary>\n",
    "<br>\n",
    "Create a space that contains a unit circle and sample uniformally from it\n",
    "</details>\n",
    "\n",
    "<br>\n",
    "<details><summary>\n",
    "Click here for (another) small hint…\n",
    "</summary>\n",
    "<br>\n",
    "The area of that unit circle is πr<sup>2</sup>=π/4. \n",
    "</details>\n",
    "\n",
    "<br>\n",
    "<details><summary>\n",
    "Click here for (yet another) small hint…\n",
    "</summary>\n",
    "<br>\n",
    "The area of the square is 1.<br> If we divide the area of the circle, by the area of the square we get π/4.\n",
    "</details>\n",
    "\n",
    "<br>\n",
    "<details><summary>\n",
    "Click here for (the last) small hint…\n",
    "</summary>\n",
    "<br>\n",
    "The equation of that cirle is x<sup>2</sup> + y<sup>2</sup> = 1</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is a gif to break the delicious tension:\n",
    "\n",
    "__My approach to algorithm questions during a technical interview:__\n",
    "![](http://ljdchost.com/4R0LT8c.gif)\n",
    "\n",
    "Keep scrolling for solutions...\n",
    "<br>\n",
    "<br> \n",
    "<br>\n",
    "<br>\n",
    "<br> \n",
    "<br>\n",
    "<br>\n",
    "<br> \n",
    "<br>\n",
    "<br>\n",
    "<br> \n",
    "<br>\n",
    "<br>\n",
    "<br> \n",
    "<br>\n",
    "<br>\n",
    "<br> \n",
    "<br>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "Solutions\n",
    "-----\n",
    "\n",
    "Use Monte Carlo method to estimate π!\n",
    "\n",
    "[Demo of the solution](https://academo.org/demos/estimating-pi-monte-carlo/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Brian Spiering's solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from random import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def pi(n_samples=100):\n",
    "    n_successes = 0\n",
    "    for _ in range(n_samples):\n",
    "        x, y = random(), random()\n",
    "        n_successes += ((x*x) + (y*y) <= 1)   # Inside of the circle\n",
    "    pi_estimate = 4 * n_successes / n_samples # From the ratio of unit square to unit circle; if r=.5, then π*r^2 = π/4\n",
    "    return pi_estimate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2.96"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pi()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4.0\n",
      "3.6\n",
      "3.16\n",
      "3.08\n",
      "3.1636\n",
      "3.13844\n",
      "3.144012\n",
      "3.1424072\n"
     ]
    }
   ],
   "source": [
    "# Explore how increasing the number of samples improves our estimates\n",
    "for orders in range(0, 8):\n",
    "    print(pi(n_samples=10**orders))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "-----\n",
    "\n",
    "Another solution from Tomáš Bouda is [here](https://medium.com/100-days-of-algorithms/day-9-monte-carlo-%CF%80-7ae010743bde)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def pi(n, batch=1000):\n",
    "    t = 0\n",
    "    for i in range(n // batch):\n",
    "        p = np.random.rand(batch, 2)\n",
    "        p = (p * p).sum(axis=1)\n",
    "        t += (p <= 1).sum()\n",
    "    return 4 * t / n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pi(n=100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.092\n",
      "3.118\n",
      "3.14056\n",
      "3.138284\n",
      "3.1412388\n"
     ]
    }
   ],
   "source": [
    "# Explore how increasing the number of samples improves our estimates\n",
    "for orders in range(3, 8):\n",
    "    print(pi(n=10**orders))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "Challenge Activity\n",
    "------\n",
    "\n",
    "Estimate pi from scratch using only functional tools\n",
    "\n",
    "HT: [Raymond Hettinger](https://twitter.com/raymondh/status/722451698552147968)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.1425916543395442"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from itertools import accumulate, count, cycle, islice\n",
    "import operator\n",
    "\n",
    "n = 1000\n",
    "pi = next(islice(accumulate(map(operator.truediv, cycle([4, -4]), count(1, 2))), n, None))\n",
    "pi # NOTE: This π is not a function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.666666666666667\n",
      "3.232315809405594\n",
      "3.1514934010709914\n",
      "3.1425916543395442\n",
      "3.1416926435905346\n",
      "3.1416026534897203\n",
      "3.1415936535887745\n",
      "3.1415927535897814\n",
      "3.141592663589326\n"
     ]
    }
   ],
   "source": [
    "# The functional approach should scale better, let's check informally...\n",
    "for orders in range(0, 9):\n",
    "    n = 10**orders\n",
    "    pi = next(islice(accumulate(map(operator.truediv, cycle([4, -4]), count(1, 2))), n, None))\n",
    "    print(pi)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Challenge Question\n",
    "-----\n",
    "\n",
    "MathOps (Mathematical Operations) is the practice of implementing Math concepts on actual computers. MathOps is where the elegant field of Math has to \"soils its hands\" with limitations with this corporeal world. It is important but often thankless work.\n",
    "\n",
    "<br>\n",
    "<details><summary>\n",
    "In the field of MathOps, is `math.pi` a constant?\n",
    "</summary>\n",
    "<br>\n",
    "No. It is a variable that doesn't change! <br>\n",
    "<br>\n",
    "Pi can be different for different software. \n",
    "</details>\n",
    "\n",
    "<br>\n",
    "<br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.14159265359\n"
     ]
    }
   ],
   "source": [
    "%%python2\n",
    "\n",
    "from math import pi as pi2\n",
    "print(pi2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3.141592653589793\n"
     ]
    }
   ],
   "source": [
    "%%python3\n",
    "\n",
    "from math import pi as pi3\n",
    "print(pi3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "No, really, pi is wrong…\n",
    "-----\n",
    "\n",
    "[The Tau Manifesto](https://tauday.com/tau-manifesto)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6.283185307179586\n"
     ]
    }
   ],
   "source": [
    "from math import tau\n",
    "\n",
    "print(tau)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br>\n",
    "<br> \n",
    "<br>\n",
    "\n",
    "----"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}