next | previous | forward | backward | up | index | toc

# measuring the size of circuits

## Synopsis

• Usage:
d = depth g
d = depth G
H = countGates g
H = countGates G
• Inputs:
• g, an instance of the type Gate,
• G, an instance of the type GateMatrix,
• Outputs:
• d, an integer, circuit depth
• H, , total number of gates of each type

The depth of an algebraic circuit is the length of the longest path of evaluations from any input gate to any output gate.

 i1 : declareVariable x o1 = x o1 : InputGate i2 : f = x + 1 o2 = (x + 1) o2 : SumGate i3 : n = 12; i4 : for i from 1 to n do f = f*f -- f = (x+1)^(2^n) i5 : depth f o5 = 13

depth is not the sole indicator of circuit complexity. For instance, the total number of gates in a circuit (sometimes referred to as its "size") also plays a role. "countGates" returns the number of constituent Gates according to their type.

 i6 : x = symbol x o6 = x o6 : Symbol i7 : n = 8 o7 = 8 i8 : varGates = declareVariable \ for i from 1 to n list x_i o8 = {x , x , x , x , x , x , x , x } 1 2 3 4 5 6 7 8 o8 : List i9 : G1 = gateMatrix{{x_1+x_2+x_3+x_4+x_5+x_6+x_7+x_8}} o9 = {{(((((((x + x ) + x ) + x ) + x ) + x ) + x ) + x )}} 1 2 3 4 5 6 7 8 o9 : GateMatrix i10 : G2 = gateMatrix{{((x_1+x_2)+(x_3+x_4))+((x_5+x_6)+(x_7+x_8))}} o10 = {{(((x + x ) + (x + x )) + ((x + x ) + (x + x )))}} 1 2 3 4 5 6 7 8 o10 : GateMatrix i11 : depth G1 o11 = 7 i12 : depth G2 o12 = 3 i13 : countGates G1 o13 = HashTable{cache => CacheTable{...15...}} InputGate => 8 SumGate => 7 o13 : HashTable i14 : countGates G2 o14 = HashTable{cache => CacheTable{...15...}} InputGate => 8 SumGate => 7 o14 : HashTable