math.isclose_example.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# `math.isclose()` example: Newton's method"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introducing `math.isclose()`\n",
    "\n",
    "The [`math.isclose()`](https://docs.python.org/3/library/math.html?highlight=isclose#math.isclose) function (new in Python 3.5) is *the one obvious way™* to solve a common problem in floating point math: how to safely compare two values when we can't get exact equality due to the [limitations of floating point arithmetic](https://docs.python.org/3/tutorial/floatingpoint.html).\n",
    "\n",
    "For example, consider this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.30000000000000004"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "three_tenths = .1 + .1 + .1\n",
    "three_tenths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "three_tenths == .3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The issue is the efficient but approximate binary representation of some numbers (like `.1`) in modern CPUs using the IEEE-754 floating point standard. There are several ways of making such a comparison with a practical tolerance, but since Python 3.5 the canonical way is to use [`math.isclose()`](https://docs.python.org/3/library/math.html?highlight=isclose#math.isclose), like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import math\n",
    "\n",
    "math.isclose(three_tenths, .3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The [`math.isclose()`](https://docs.python.org/3/library/math.html?highlight=isclose#math.isclose) function has two additional arguments to fine tune the tolerance, but I'll not cover them here.\n",
    "\n",
    "Now let's see a real example using `isclose()`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using `math.isclose()` with Newton's method\n",
    "\n",
    "Newton's method of succesive approximations can be used to compute the square root. \n",
    "\n",
    "> **How Newton's method works**\n",
    ">\n",
    "> To compute `sqrt(n)`, the algorithm starts with `guess=n/2` and computes a `better_guess`: the average of `guess` and `n/guess`. If those two guesses are equal or very close, the square root is the `better_guess`. If not, the `better_guess` is used as the `guess`, and a new `better_guess` is computed as the average of that and `n/guess`. This process quickly converges to a very good approximation of the square root.\n",
    "\n",
    "The implementation below uses `math.is_close()` to test whether the `better_guess` is close to the current one, which means further approximations will not be useful and the `better_guess` is an acceptable result."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "def newton_sqrt(n, verbose=False):\n",
    "    guess = n / 2\n",
    "    while True:\n",
    "        if verbose: print('guess ->', guess)\n",
    "        better_guess = (guess + n/guess) / 2\n",
    "        if math.isclose(guess, better_guess):\n",
    "            return better_guess\n",
    "        guess = better_guess"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sample use:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10.0"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "newton_sqrt(100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using `verbose=True`, we can see how quickly Newton's algorithm converges to the solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "guess -> 50.0\n",
      "guess -> 26.0\n",
      "guess -> 14.923076923076923\n",
      "guess -> 10.812053925455988\n",
      "guess -> 10.030495203889796\n",
      "guess -> 10.000046356507898\n",
      "guess -> 10.000000000107445\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "10.0"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "newton_sqrt(100, True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Applying `newton_sqrt()` to numbers from 9 to 16, we see that some results are a little different from those from `math.sqrt()`. However, the results are all considered close enough by `isclose()` with the default tolerance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "sqrt( 9): 3.00000000000000000000 3.00000000000000000000 True 0.00000000000000000000\n",
      "sqrt(10): 3.16227766016837907870 3.16227766016837952279 True -0.00000000000000044409\n",
      "sqrt(11): 3.31662479035539980998 3.31662479035539980998 True 0.00000000000000000000\n",
      "sqrt(12): 3.46410161513775438635 3.46410161513775438635 True 0.00000000000000000000\n",
      "sqrt(13): 3.60555127546398956895 3.60555127546398912486 True 0.00000000000000044409\n",
      "sqrt(14): 3.74165738677394132949 3.74165738677394132949 True 0.00000000000000000000\n",
      "sqrt(15): 3.87298334620741702139 3.87298334620741702139 True 0.00000000000000000000\n",
      "sqrt(16): 4.00000000000000000000 4.00000000000000000000 True 0.00000000000000000000\n"
     ]
    }
   ],
   "source": [
    "for n in range(9, 17):\n",
    "    computed = newton_sqrt(n)\n",
    "    expected = math.sqrt(n)\n",
    "    close = math.isclose(computed, expected)\n",
    "    delta = computed - expected\n",
    "    print('sqrt({:2d}): {:.20f} {:.20f} {} {:.20f}'.format(n, computed, expected, close, delta))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since Python already has a `math.sqrt()` function, our `newton_sqrt()` is only a didactic example. However, it is an elegant algorithm to know, and a fine example of the utility of `math.isclose()`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bonus topic: the `Decimal` type\n",
    "\n",
    "Another way of dealing with floating point issues is to completely avoid them by using the `decimal.Decimal` type, which can represent `0.1` with exact precision:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from decimal import Decimal\n",
    "\n",
    "one_tenth = Decimal('.1')\n",
    "three_tenths = one_tenth + one_tenth + one_tenth\n",
    "three_tenths == Decimal('.3')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note the use of string arguments in the `Decimal` constructors above. Using a `float` to build a `Decimal` is often a bad idea, because, the `Decimal` value will reflect the imprecision of the `float`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Decimal('0.1000000000000000055511151231257827021181583404541015625')"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Decimal(.1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Decimal(.1) == one_tenth"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Again, the `isclose` function can be helpful:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "math.isclose(Decimal(.1), one_tenth)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But if you need exact precision you should only use `Decimal` numbers built from strings or integers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Decimal('1.0')"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Decimal('.1') * 10"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " In general, calculations with money should use `Decimal` values to represent money amounts."
   ]
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}