10_alg_parity_max.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Foundations of Computational Economics #10\n",
    "\n",
    "by Fedor Iskhakov, ANU\n",
    "\n",
    "<img src=\"_static/img/dag3logo.png\" style=\"width:256px;\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "## Two simple algorithms: parity and max\n",
    "\n",
    "<img src=\"_static/img/lab.png\" style=\"width:64px;\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "<img src=\"_static/img/youtube.png\" style=\"width:65px;\">\n",
    "\n",
    "[https://youtu.be/fKFZZc77if0](https://youtu.be/fKFZZc77if0)\n",
    "\n",
    "Description: Parity of a number, bitwise operations in Python. Finding maximum in an array."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Divisibility by number base\n",
    "\n",
    "Whether a decimal number is divisible by 10 can be easily seen from its last digit.\n",
    "\n",
    "Similarly, whether a binary number is divisible by 2 can be easily seen from its last digit.\n",
    "\n",
    "**If last digit of a number is 0, it is divisible by its base!**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Parity of a number algorithm\n",
    "\n",
    "1. Convert the number to binary  \n",
    "1. Check if last digit is zero  \n",
    "\n",
    "\n",
    "- All integers already have a clear binary representation  \n",
    "\n",
    "\n",
    "*This algorithm only applies to integers*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Bitwise operations in Python\n",
    "\n",
    "- bitwise AND **&**  \n",
    "- bitwise OR **|**  \n",
    "- bitwise XOR **^**  \n",
    "- bitwise NOT **~** (including sign bit!)  \n",
    "- right shift **>>**  \n",
    "- left shift **<<** (without overflow!)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Bitwise AND, OR and XOR\n",
    "\n",
    "<img src=\"_static/img/bitwise.png\" style=\"width:600px;\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "hide-output": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  a = 3 (0011)\n",
      "  b = 5 (0101)\n",
      "a&b = 1 (0001)\n"
     ]
    }
   ],
   "source": [
    "# bitwise logic\n",
    "a,b = 3,5  # 3=0011, 5=0101\n",
    "print('  a = {0:d} ({0:04b})\\n  b = {1:d} ({1:04b})'.format(a,b))\n",
    "print('a&b = {0:d} ({0:04b})'.format(a&b))\n",
    "# print('a|b = {0:d} ({0:04b})'.format(a|b))\n",
    "# print('a^b = {0:d} ({0:04b})'.format(a^b))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Bit shifts in Python\n",
    "\n",
    "<img src=\"_static/img/bitshift.png\" style=\"width:600px;\">"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "#### Replacing arithmetic operations with bit operations\n",
    "\n",
    "Is it possible?\n",
    "Which operations can be done in this *geeky* way?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "hide-output": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  a =  227 (0000000011100011)\n",
      "  b =  113 (0000000001110001)\n",
      "\n",
      "  a =  227 (0000000011100011)\n",
      "  b =  908 (0000001110001100)\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# bit shifts\n",
    "a = 0b11100011\n",
    "b = a >> 1\n",
    "print('  a = {0:4d} ({0:016b})\\n  b = {1:4d} ({1:016b})\\n'.format(a,b))\n",
    "b = a << 2\n",
    "print('  a = {0:4d} ({0:016b})\\n  b = {1:4d} ({1:016b})\\n'.format(a,b))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "hide-output": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  a =  227 (0000000011100011)\n",
      "a//2 = 113, a>>1 = 113\n",
      "a//4 = 56, a>>2 = 56\n",
      "a//8 = 28, a>>3 = 28\n",
      "a//16 = 14, a>>4 = 14\n",
      "a//32 = 7, a>>5 = 7\n",
      "a//64 = 3, a>>6 = 3\n",
      "a//128 = 1, a>>7 = 1\n",
      "a//256 = 0, a>>8 = 0\n",
      "a//512 = 0, a>>9 = 0\n"
     ]
    }
   ],
   "source": [
    "# arythmetic operations with bit shifts\n",
    "a = 0b11100011\n",
    "print('  a = {0:4d} ({0:016b})'.format(a))\n",
    "\n",
    "for i in range(1,10):\n",
    "    x = 2**i\n",
    "    d = a//x\n",
    "    s = a>>i\n",
    "    print('a//%d = %d, a>>%d = %d' % (x,d,i,s))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Parity algorithm\n",
    "\n",
    "Run a single bitwise AND operation to\n",
    "compare against **0b0000001** which is simply 1 in decimal\n",
    "\n",
    "Complexity is constant because only one bit must be checked!\n",
    "\n",
    "*However, when running AND are all bits checked?*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "hide-output": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "# parity check\n",
    "def parity (n,verbose=False):\n",
    "    '''Returns 1 if passed integer number is odd\n",
    "    '''\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "hide-output": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n =     2 (00000010), parity=0\n",
      "n =     4 (00000100), parity=0\n",
      "n =     7 (00000111), parity=1\n",
      "n =    32 (00100000), parity=0\n",
      "n =   543 (1000011111), parity=1\n",
      "n =   671 (1010011111), parity=1\n",
      "n =   780 (1100001100), parity=0\n"
     ]
    }
   ],
   "source": [
    "# check parity of various numbers\n",
    "for n in [2,4,7,32,543,671,780]:\n",
    "    print('n = {0:5d} ({0:08b}), parity={1:d}'.format(n,parity(n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "hide-output": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def parity (n,verbose=False):\n",
    "    '''Returns 1 if passed integer number is odd\n",
    "    '''\n",
    "    if not isinstance(n, int): raise TypeError('Only integers in parity()')\n",
    "    if verbose: print('n = {:08b}'.format(n))  # print binary form of the number\n",
    "    return n & 1  # bitwise and operation returns the value of last bit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Finding max/min in a list\n",
    "\n",
    "- In the worst case, there is no way to avoid checking *all elements*  \n",
    "- Complexity is linear in the number of elements on the list  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "hide-output": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def maximum_from_list (vars):\n",
    "    '''Returns the maximum from a list of values\n",
    "    '''\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "hide-output": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Maximum in [40.36631825 33.1923305   4.85928511 31.26526949 38.56821075 92.47304391\n",
      " 61.57887596 12.81310827 92.20711143 45.12116267] is 92.47\n",
      "Maximum in [36.19221981 68.39217716 71.45549904 59.94828759 17.04806836 42.36644573\n",
      " 65.48883833 91.13163144 57.13898149 67.50339454] is 91.13\n",
      "Maximum in [75.48095297 70.96067478 15.19709572 94.50537863 79.74015518 99.65516414\n",
      " 88.51336519 38.89378926 22.89769873  4.56590212] is 99.66\n",
      "Maximum in [46.96531804 30.02051975 20.0643693  11.77139318 77.8880612   1.88485342\n",
      " 82.53652171 56.93653459 79.10377169 33.83294574] is 82.54\n",
      "Maximum in [ 3.46403787 25.77379166 79.32433345 96.9859477  41.5598842  17.76082696\n",
      " 34.37472047  2.59704741 71.6989639  43.67998844] is 96.99\n"
     ]
    }
   ],
   "source": [
    "# find maximum in some random lists\n",
    "import numpy as np\n",
    "for i in range(5):\n",
    "    list = np.random.uniform(low=0.0, high=100.0, size=10)\n",
    "    m = maximum_from_list(list)\n",
    "    print('Maximum in {} is {:.2f}'.format(list,m))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "hide-output": false,
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def maximum_from_list (vars):\n",
    "    '''Returns the maximum from a list of values\n",
    "    '''\n",
    "    m=float('-inf')  # init with the worst value\n",
    "    for v in vars:\n",
    "        if v > m: m = v\n",
    "    return m"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Further learning resources\n",
    "\n",
    "- Formatting strings\n",
    "  [https://www.digitalocean.com/community/tutorials/how-to-use-string-formatters-in-python-3](https://www.digitalocean.com/community/tutorials/how-to-use-string-formatters-in-python-3)  \n",
    "- Bitwise operations post on Geeksforgeeks\n",
    "  [https://www.geeksforgeeks.org/python-bitwise-operators/](https://www.geeksforgeeks.org/python-bitwise-operators/)  "
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "date": 1612589584.636859,
  "download_nb": false,
  "filename": "10_alg_parity_max.rst",
  "filename_with_path": "10_alg_parity_max",
  "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.6"
  },
  "title": "Foundations of Computational Economics #10"
 },
 "nbformat": 4,
 "nbformat_minor": 4
}