{ "cells": [ { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "# Foundations of Computational Economics #10\n", "\n", "by Fedor Iskhakov, ANU\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "## Two simple algorithms: parity and max\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "subslide" } }, "source": [ "\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", "" ] }, { "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", "" ] }, { "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 }