next | previous | forward | backward | up | top | index | toc | Macaulay2 website
SLPexpressions :: measuring the size of circuits

measuring the size of circuits

Synopsis

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

See also