measuring the size of circuits

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, a hash table, 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

measuring the size of circuits

See also