Macaulay2 » Documentation
Packages » SLPexpressions :: measuring the size of circuits
next | previous | forward | backward | up | index | toc

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