Foundations of Computational Economics #10¶

by Fedor Iskhakov, ANU

Two simple algorithms: parity and max¶

https://youtu.be/fKFZZc77if0

Description: Parity of a number, bitwise operations in Python. Finding maximum in an array.

Divisibility by number base¶

Whether a decimal number is divisible by 10 can be easily seen from its last digit.

Similarly, whether a binary number is divisible by 2 can be easily seen from its last digit.

If last digit of a number is 0, it is divisible by its base!

Parity of a number algorithm¶

Convert the number to binary
Check if last digit is zero

All integers already have a clear binary representation

This algorithm only applies to integers

Bitwise operations in Python¶

bitwise AND &
bitwise OR |
bitwise XOR ^
bitwise NOT ~ (including sign bit!)
right shift >>
left shift << (without overflow!)

Bitwise AND, OR and XOR¶

In [1]:

# bitwise logic
a,b = 3,5  # 3=0011, 5=0101
print('  a = {0:d} ({0:04b})\n  b = {1:d} ({1:04b})'.format(a,b))
print('a&b = {0:d} ({0:04b})'.format(a&b))
# print('a|b = {0:d} ({0:04b})'.format(a|b))
# print('a^b = {0:d} ({0:04b})'.format(a^b))

  a = 3 (0011)
  b = 5 (0101)
a&b = 1 (0001)

Bit shifts in Python¶

Replacing arithmetic operations with bit operations¶

Is it possible? Which operations can be done in this geeky way?

In [2]:

# bit shifts
a = 0b11100011
b = a >> 1
print('  a = {0:4d} ({0:016b})\n  b = {1:4d} ({1:016b})\n'.format(a,b))
b = a << 2
print('  a = {0:4d} ({0:016b})\n  b = {1:4d} ({1:016b})\n'.format(a,b))

  a =  227 (0000000011100011)
  b =  113 (0000000001110001)

  a =  227 (0000000011100011)
  b =  908 (0000001110001100)

In [3]:

# arythmetic operations with bit shifts
a = 0b11100011
print('  a = {0:4d} ({0:016b})'.format(a))

for i in range(1,10):
    x = 2**i
    d = a//x
    s = a>>i
    print('a//%d = %d, a>>%d = %d' % (x,d,i,s))

  a =  227 (0000000011100011)
a//2 = 113, a>>1 = 113
a//4 = 56, a>>2 = 56
a//8 = 28, a>>3 = 28
a//16 = 14, a>>4 = 14
a//32 = 7, a>>5 = 7
a//64 = 3, a>>6 = 3
a//128 = 1, a>>7 = 1
a//256 = 0, a>>8 = 0
a//512 = 0, a>>9 = 0

Parity algorithm¶

Run a single bitwise AND operation to compare against 0b0000001 which is simply 1 in decimal

Complexity is constant because only one bit must be checked!

However, when running AND are all bits checked?

In [4]:

# parity check
def parity (n,verbose=False):
    '''Returns 1 if passed integer number is odd
    '''
    pass

In [7]:

# check parity of various numbers
for n in [2,4,7,32,543,671,780]:
    print('n = {0:5d} ({0:08b}), parity={1:d}'.format(n,parity(n)))

n =     2 (00000010), parity=0
n =     4 (00000100), parity=0
n =     7 (00000111), parity=1
n =    32 (00100000), parity=0
n =   543 (1000011111), parity=1
n =   671 (1010011111), parity=1
n =   780 (1100001100), parity=0

In [8]:

def parity (n,verbose=False):
    '''Returns 1 if passed integer number is odd
    '''
    if not isinstance(n, int): raise TypeError('Only integers in parity()')
    if verbose: print('n = {:08b}'.format(n))  # print binary form of the number
    return n & 1  # bitwise and operation returns the value of last bit

Finding max/min in a list¶

In the worst case, there is no way to avoid checking all elements
Complexity is linear in the number of elements on the list

In [7]:

def maximum_from_list (vars):
    '''Returns the maximum from a list of values
    '''
    pass

In [10]:

# find maximum in some random lists
import numpy as np
for i in range(5):
    list = np.random.uniform(low=0.0, high=100.0, size=10)
    m = maximum_from_list(list)
    print('Maximum in {} is {:.2f}'.format(list,m))

Maximum in [40.36631825 33.1923305   4.85928511 31.26526949 38.56821075 92.47304391
 61.57887596 12.81310827 92.20711143 45.12116267] is 92.47
Maximum in [36.19221981 68.39217716 71.45549904 59.94828759 17.04806836 42.36644573
 65.48883833 91.13163144 57.13898149 67.50339454] is 91.13
Maximum in [75.48095297 70.96067478 15.19709572 94.50537863 79.74015518 99.65516414
 88.51336519 38.89378926 22.89769873  4.56590212] is 99.66
Maximum in [46.96531804 30.02051975 20.0643693  11.77139318 77.8880612   1.88485342
 82.53652171 56.93653459 79.10377169 33.83294574] is 82.54
Maximum in [ 3.46403787 25.77379166 79.32433345 96.9859477  41.5598842  17.76082696
 34.37472047  2.59704741 71.6989639  43.67998844] is 96.99

In [9]:

def maximum_from_list (vars):
    '''Returns the maximum from a list of values
    '''
    m=float('-inf')  # init with the worst value
    for v in vars:
        if v > m: m = v
    return m

Further learning resources¶

Formatting strings https://www.digitalocean.com/community/tutorials/how-to-use-string-formatters-in-python-3
Bitwise operations post on Geeksforgeeks https://www.geeksforgeeks.org/python-bitwise-operators/