labs/sqrt.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Approximating square root iteratively\n",
    "\n",
    "There are a lot of useful functions that have no closed form solution, meaning we can't just do a computation and return the value. Instead, we need to use an iterative method to approximate the function value. It's an extremely useful pattern that will come in handy later in this program and in your professional life. We can use iterative computing to approximate sine (with Taylor series expansion), approximate square root (as we'll do in this lecture), or optimize a cost or error function (gradient descent in the introduction to machine learning course).\n",
    "\n",
    "The goal of this lab is to translate a recurrence relation, that yields a sequence of values, to Python.  Instead of computing and returning a single value, we will look for **convergence of the series**. In other words, if we run the series out far enough, $x_{i+1}$ will be close to $x_i$ leaving $x_i$ as  a very accurate approximation of square root. This will teach us the basics of iterative computing and prepare us for  more complicated function optimization material needed later."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Babylonian method\n",
    "\n",
    "To approximate square root, the idea is to pick an initial estimate, $x_0$, and then iterate with better and better estimates, $x_i$, using the ([Babylonian method](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method)) recurrence relation:\n",
    "\n",
    "$x_{i+1} = \\frac{1}{2}(x_i + \\frac{n}{x_i})$\n",
    "\n",
    "There’s a great deal on the web you can read to learn more about why this process works but it relies on the average (midpoint) of $x_i$ and $n/x_i$ getting us closer to the square root of n. The cool thing is that the iteration converges quickly.\n",
    "\n",
    "Our goal is to write a function that takes a single number and returns its square root. What do we know about this function before even beginning to code? Well, we have a clear description of the problem per the recurrence relation, and we also have the function signature we want:\n",
    "\n",
    "```python\n",
    "def sqrt(n):\n",
    "```\n",
    "\n",
    "Because we are implementing a recurrence relation, we know that we will have a loop that computes $x_{i+1}$ from $x_{i}$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Convergence\n",
    "\n",
    "The terminating condition of the loop is when we have reached convergence or close to it. Convergence just means that $x_{i+1}$ is pretty close to $x_i$. Because we can never compare to real numbers for equality, we have to check for the difference being smaller than some precision like 0.00000001."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Iterative method outline\n",
    "\n",
    "Just as we have an outline for a data science program, iterative methods all share the same basic outline. (I'm assuming here that $x_{i+1}$ depends only on a single previous value and that $i$ implicitly increments as the loop goes around.)\n",
    "\n",
    "*set $x_0$ to initial value*<br>\n",
    "*repeat:*<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;$x_{i+1} =$ function-giving-next-value$(x_i)$<br>\n",
    "*until $abs(x_{i+1} - x_i) \\lt precision$<br>\n",
    "return $x_{i+1}$*<br>\n",
    "\n",
    "Because Python does not have a repeat-until loop, we fake it with an infinite loop containing a conditional that breaks us out upon convergence:\n",
    "\n",
    "*set $x_0$ to initial value*<br>\n",
    "*while True:*<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;$x_{i+1} =$ function-giving-next-value$(x_i)$<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;*if $abs(x_{i+1} - x_i) \\lt precision$<br>\n",
    "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return $x_{i+1}$*<br>\n",
    "\n",
    "That is a fairly straightforward implementation of the recurrence relation, but you will notice that we don't actually need to keep all previous $x_i$ around except for the new value and the previous value. Here is a Python implementation that tracks only two values and follows the infinite loop pattern:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sqrt(n):\n",
    "    \"compute square root of n\"\n",
    "    PRECISION = 0.00000001 # stop iterating when we converge with this delta\n",
    "    x_0 = 1.0 # pick any old initial value\n",
    "    x_prev = x_0\n",
    "    while True: # Python doesn't have repeat-until loop so fake it\n",
    "        #print(x_prev)\n",
    "        x_new = 0.5 * (x_prev + n/x_prev)\n",
    "        if abs(x_new - x_prev) < PRECISION:\n",
    "            return x_new\n",
    "        x_prev = x_new # x_i+1 becomes x_i (previous value)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10.0"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sqrt(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To test our square root approximation, we can compare it to `math.sqrt()` and use numpy's `isclose` to do the comparison."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def check(n):\n",
    "    assert np.isclose(sqrt(n), np.sqrt(n))\n",
    "\n",
    "def test_big():\n",
    "    check(125348)\n",
    "\n",
    "def test_medium():\n",
    "    check(89.2342)\n",
    "\n",
    "def test_100():\n",
    "    check(100)\n",
    "\n",
    "def test_1():\n",
    "    check(1)\n",
    "\n",
    "def test_0():\n",
    "    check(0)\n",
    "\n",
    "test_big()\n",
    "test_medium()\n",
    "test_100()\n",
    "test_1()\n",
    "test_0()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Type in (don't cut/paste) the `sqrt(n)` function and test with, for example, `sqrt(125348.0)`. Make sure you get the right answer (354.045195) and then add print statements so that you can see the sequence of $x_{i}$ values. I get:\n",
    "\n",
    "```\n",
    "1.0\n",
    "62674.5\n",
    "31338.249992\n",
    "15671.1249162\n",
    "7839.56178812\n",
    "3927.77547356\n",
    "1979.84435152\n",
    "1021.5781996\n",
    "572.139273508\n",
    "395.612894667\n",
    "356.228988269\n",
    "354.051888518\n",
    "354.045194918\n",
    "354.045194855\n",
    "```\n",
    "\n",
    "Notice how quickly it converges!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.0\n",
      "62674.5\n",
      "31338.249992022273\n",
      "15671.12491623693\n",
      "7839.561788117747\n",
      "3927.7754735639414\n",
      "1979.844351517673\n",
      "1021.5781996033152\n",
      "572.1392735077299\n",
      "395.612894666841\n",
      "356.2289882689982\n",
      "354.0518885182295\n",
      "354.04519491839494\n",
      "354.04519485512014\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "354.04519485512014"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def sqrt_with_trace(n):\n",
    "    \"compute square root of n\"\n",
    "    PRECISION = 0.00000001 # stop iterating when we converge with this delta\n",
    "    x_0 = 1.0 # pick any old initial value\n",
    "    x_prev = x_0\n",
    "    while True: # Python doesn't have repeat-until loop so fake it\n",
    "        print(x_prev)\n",
    "        x_new = 0.5 * (x_prev + n/x_prev)\n",
    "        if abs(x_new - x_prev) < PRECISION:\n",
    "            return x_new\n",
    "        x_prev = x_new\n",
    "\n",
    "sqrt_with_trace(125348.000000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise: Testing with pytest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " To run with the unit tester pytest, save the `sqrt()` function in a file called `sqrt.py` and then put the test code into a file called `test_sqrt.py`.  That test file will also need to import the square root code so add\n",
    " \n",
    "```\n",
    "from sqrt import *\n",
    "```\n",
    "\n",
    "to the top of the test file. To run the tests from the command line, you can do the following:\n",
    "\n",
    "```bash\n",
    "$ python test_sqrt.py \n",
    "$\n",
    "```\n",
    "\n",
    "which prints nothing because there are no errors (hopefully).\n",
    "\n",
    "A better way is to use `pytest` which executes all functions that start with prefix `test_`:\n",
    "\n",
    "```bash\n",
    "$ pip install pytest\n",
    "$ pytest -v test_sqrt.py \n",
    "============================= test session starts ==============================\n",
    "platform darwin -- Python 3.8.8, pytest-6.2.3, py-1.10.0, pluggy-0.13.1 -- /Users/parrt/opt/anaconda3/bin/python\n",
    "cachedir: .pytest_cache\n",
    "rootdir: /private/tmp\n",
    "plugins: anyio-2.2.0\n",
    "collected 5 items                                                              \n",
    "\n",
    "test_sqrt.py::test_big PASSED                                            [ 20%]\n",
    "test_sqrt.py::test_medium PASSED                                         [ 40%]\n",
    "test_sqrt.py::test_100 PASSED                                            [ 60%]\n",
    "test_sqrt.py::test_1 PASSED                                              [ 80%]\n",
    "test_sqrt.py::test_0 PASSED                                              [100%]\n",
    "\n",
    "============================== 5 passed in 0.07s ===============================\n",
    "```\n",
    "\n",
    "The other benefit is that we don't need the explicit calls so you can delete this part and it still works with pytest:\n",
    " \n",
    "```python\n",
    "test_big()\n",
    "test_medium()\n",
    "test_100()\n",
    "test_1()\n",
    "test_0()\n",
    "```"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.7.3"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "navigate_num": "#000000",
    "navigate_text": "#333333",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700",
    "sidebar_border": "#EEEEEE",
    "wrapper_background": "#FFFFFF"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "102px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": false,
   "widenNotebook": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}