# 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]:
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]:
In [139]:
C.render_eval(1,1,1,0)

Out[139]:
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]:
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]:
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 [ ]: