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
|