{
"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
}