Chapter 3: Defining computation

This notebook contains code related to Chapter 3: Defining Computation.

In [182]:
# utility code 
%run "Utilities.ipynb"
from IPython.display import clear_output
clear_output()
In [145]:
def AND(a,b): return a*b

def OR(a,b): return 1 if a+b else 0

def NOT(a): return 1-a
In [146]:
def EVAL(code,X):
    """Evaluate code on input X."""
    n,m = numinout(code) # helper function - get number of inputs and outputs
    
    vtable = { f"X[{i}]":int(X[i]) for i in range(n)}
    
    for line in code.split("\n"):
        if not line: continue
        foo,op,bar,blah = parseline(line,2) 
        # helper function - split "foo = OP(,blah)" to list ["foo","OP","bar","blah"]
        # 2 is num of arguments to expect: blah is empty if it's missing
        if op=="NOT": vtable[foo] = NOT(vtable[bar])
        if op=="AND": vtable[foo] = AND(vtable[bar],vtable[blah])
        if op=="OR": vtable[foo] =  OR(vtable[bar],vtable[blah])
    
    return [vtable[f"Y[{j}]"] for j in range(m)]            
In [147]:
majcode = r"""firstpair  = AND(X[0],X[1])
secondpair = AND(X[1],X[2])
thirdpair  = AND(X[0],X[2])
temp       = OR(secondpair,thirdpair)
Y[0] =  OR(firstpair,temp)
"""
In [150]:
C = prog2circuit(majcode)
schemdraw(C,filename="majaoncircuit.png")
In [113]:
code = r"""
t1      = AND(X[0],X[1])
notx0   = NOT(X[0])
t2      = AND(notx0,X[2])
Y[0]    = OR(t1,t2)
"""[1:]
In [114]:
EVAL(code,"010")
Out[114]:
[0]
In [115]:
prog2circuit(code)
Out[115]:
%3 input_0 X[0] gate_0 input_0->gate_0 gate_1 ¬ input_0->gate_1 input_1 X[1] input_1->gate_0 input_2 X[2] gate_2 input_2->gate_2 gate_3 →Y[0] gate_0->gate_3 gate_1->gate_2 gate_2->gate_3
In [153]:
C = prog2circuit(code)
schemdraw(C)
In [156]:
def XOR3(a,b,c):
    w1 = AND(a,b)
    w2 = NOT(w1)
    w3 = OR(a,b)
    w4 = AND(w2,w3)
    w5 = AND(w4,c)
    w6 = NOT(w5)
    w7 = OR(w4,c)
    return AND(w6,w7)

drawcirc(XOR3)
In [117]:
def AON2NAND(code):
    """Translate an AON-CIRC program to an equivalent NAND-CIRC program"""
    output = ""
    counter = 0
    for line in code.split("\n"):
        if not line: continue
        foo,op,bar,blah = parseline(line,2) 
        if op=="NOT":
            output += f"{foo} = NAND({bar},{bar})\n"
        if op=="AND": 
            output += f"temp_{counter} = NAND({bar},{blah})\n"
            output += f"{foo} = NAND(temp_{counter},temp_{counter})\n"
            counter +=1
        if op=="OR":
            output += f"temp_{counter} = NAND({bar},{bar})\n"
            output += f"temp_{counter+1} = NAND({blah},{blah})\n"
            output += f"{foo} = NAND(temp_{counter},temp_{counter+1})\n"
            counter +=2
    return output
In [119]:
C = prog2circuit(AON2NAND(code))
schemdraw(C)
In [120]:
def BIG1(a,b):
    t = NOT(b)
    return OR(a,t)

def BIG2(X):
    """Input is X[0]...X[3] which we consider as two three-bit numbers A and B. We return 1 iff A>B"""
    y1 = BIG1(X[0],X[2])
    n1 = BIG1(X[2],X[0])
    y2 = BIG1(X[1],X[3])
    t  = AND(y2,n1)
    return OR(y1,t)
In [121]:
    
In [134]:
code = aon2code(BIG2,4)
print(code)
temp_1 = NOT(X[2])
temp_2 = OR(X[0],temp_1)
temp_3 = NOT(X[0])
temp_4 = OR(X[2],temp_3)
temp_5 = NOT(X[3])
temp_6 = OR(X[1],temp_5)
temp_7 = AND(temp_6,temp_4)
Y[0] = OR(temp_2,temp_7)
In [135]:
C = prog2circuit(code)
schemdraw(C)
In [136]:
BIG2([1,0,0,1])
Out[136]:
1
In [137]:
BIG1(1,0)
Out[137]:
1
In [138]:
C = prog2circuit(code)
C
Out[138]:
%3 input_0 X[0] gate_1 input_0->gate_1 gate_2 ¬ input_0->gate_2 input_1 X[1] gate_5 input_1->gate_5 input_2 X[2] gate_0 ¬ input_2->gate_0 gate_3 input_2->gate_3 input_3 X[3] gate_4 ¬ input_3->gate_4 gate_0->gate_1 gate_7 →Y[0] gate_1->gate_7 gate_2->gate_3 gate_6 gate_3->gate_6 gate_4->gate_5 gate_5->gate_6 gate_6->gate_7
In [139]:
C.render_eval(1,1,1,0)
Out[139]:
%3 input_0 X[0] 1 gate_1 1 input_0->gate_1 gate_2 ¬ 0 input_0->gate_2 input_1 X[1] 1 gate_5 1 input_1->gate_5 input_2 X[2] 1 gate_0 ¬ 0 input_2->gate_0 gate_3 1 input_2->gate_3 input_3 X[3] 0 gate_4 ¬ 1 input_3->gate_4 gate_0->gate_1 gate_7 →Y[0] 1 gate_1->gate_7 gate_2->gate_3 gate_6 1 gate_3->gate_6 gate_4->gate_5 gate_5->gate_6 gate_6->gate_7
In [140]:
schemdraw(C)
In [141]:
schemdraw(C,[1,1,1,0])
In [151]:
xorcode = r'''notx0 = NOT(X[0])
notx1 = NOT(X[1])
a = AND(X[1],notx0)
b = AND(X[0],notx1)
Y[0] = OR(a,b)
'''
prog2circuit(xorcode)
Out[151]:
%3 input_0 X[0] gate_0 ¬ input_0->gate_0 gate_3 input_0->gate_3 input_1 X[1] gate_1 ¬ input_1->gate_1 gate_2 input_1->gate_2 gate_0->gate_2 gate_1->gate_3 gate_4 →Y[0] gate_2->gate_4 gate_3->gate_4
In [157]:
C = prog2circuit(xorcode)
schemdraw(C) 
In [159]:
schemdraw(C,[1,0])
In [160]:
def ALLEQ(a,b,c,d):
    t = AND(AND(AND(a,b),c),d)
    u = AND(AND(AND(NOT(a),NOT(b)),NOT(c)),NOT(d))
    return OR(t,u)
In [162]:
drawcirc(ALLEQ)
In [165]:
CMPcode = r'''temp_1 = NOT(X[2])
temp_2 = OR(X[0],temp_1)
temp_3 = NOT(X[0])
temp_4 = OR(X[2],temp_3)
temp_5 = NOT(X[3])
temp_6 = OR(X[1],temp_5)
temp_7 = AND(temp_6,temp_4)
Y[0] = OR(temp_2,temp_7)
'''
schemdraw(prog2circuit(CMPcode),[1,1,1,0])
In [171]:
print(function2code(XOR3))
temp_1 = AND(X[0],X[1])
temp_2 = NOT(temp_1)
temp_3 = OR(X[0],X[1])
temp_4 = AND(temp_2,temp_3)
temp_5 = AND(temp_4,X[2])
temp_6 = NOT(temp_5)
temp_7 = OR(temp_4,X[2])
Y[0] = AND(temp_6,temp_7)
In [ ]:
temp_1 = AND(X[0],X[1])
temp_2 = NOT(temp_1)
temp_3 = OR(X[0],X[1])
temp_4 = AND(temp_2,temp_3)
temp_5 = AND(temp_4,X[2])
temp_6 = NOT(temp_5)
temp_7 = OR(temp_4,X[2])
Y[0] = AND(temp_6,temp_7)
In [172]:
drawcirc(XOR3)

NAND circuits

In [186]:
code = r'''u = NAND(X[0],X[1])
v = NAND(X[0],u)
w = NAND(X[1],u) 
Y[0] = NAND(v,w)
'''
In [183]:
def XORN(a,b):
    u = NAND(a,b)
    v = NAND(a,u)
    w = NAND(b,u)
    return NAND(v,w)

def XOR3(a,b,c):
    return XORN(XORN(a,b),c)

print(function2code(XOR3))
drawcirc(XOR3)
temp_1 = NAND(X[0],X[1])
temp_2 = NAND(X[0],temp_1)
temp_3 = NAND(X[1],temp_1)
temp_4 = NAND(temp_2,temp_3)
temp_5 = NAND(temp_4,X[2])
temp_6 = NAND(temp_4,temp_5)
temp_7 = NAND(X[2],temp_5)
Y[0] = NAND(temp_6,temp_7)
In [187]:
drawcirc(XORN)
In [181]:
temp_1 = NAND(X[0],X[1])
temp_2 = NAND(X[0],temp_1)
temp_3 = NAND(X[1],temp_1)
temp_4 = NAND(temp_2,temp_3)
temp_5 = NAND(temp_4,X[2])
temp_6 = NAND(temp_4,temp_5)
temp_7 = NAND(X[2],temp_5)
Y[0] = NAND(temp_6,temp_7)
Out[181]:
%3 input_0 X[0] gate_0 ¬∧ input_0->gate_0 gate_1 ¬∧ input_0->gate_1 input_1 X[1] input_1->gate_0 gate_2 ¬∧ input_1->gate_2 gate_0->gate_1 gate_0->gate_2 gate_3 ¬∧ →Y[0] gate_1->gate_3 gate_2->gate_3
In [188]:
def MAJ3(a,b,c):
    return OR(OR(AND(a,b),AND(b,c)),AND(a,c))

drawcirc(MAJ3,NANDONLY=True)

Increment

In [198]:
def one(a):
    return NAND(a,NAND(a,a))

def INC(X):
    n = len(X)
    Y=[0]*(n+1)
    c = one(X[0])
    for i in range(n):
        Y[i] = XORN(c,X[i])
        c = AND(X[i],c)
    Y[n] = c
    return Y
    
In [201]:
drawcirc(INC,4,NANDONLY=True)

Neural net activation functions

In [ ]:
 
In [13]:
import numpy as np
import matplotlib.pylab as plt


def step(x):
    return np.array(x > 0, dtype=np.int)

def sigmoid(x):
    return 1 / (1 + np.exp(-x))

def relu(x):
    return np.maximum(0, 0.2*x)

def mytanh(x):
    return 0.5*np.tanh(x)+0.5

x = np.arange(-5.0, 5.0, 0.1)
y_step = step(x)
y_sigmoid = sigmoid(x)
y_relu = relu(x)
y_tanh = mytanh(x)

plt.plot(x, y_step, label='Step', color='r', lw=1, linestyle=None)
plt.plot(x, y_sigmoid, label='Sigmoid', color='g', lw=1, ls='--')
plt.plot(x, y_relu, label='ReLU(0.2x)', color='b', lw=1, linestyle='-.')
plt.plot(x, y_tanh, label='0.5tanh+0.5',color='y',lw=1,linestyle=':')
plt.ylim(-0.1, 1.1)
plt.legend()
plt.show()
In [ ]: