COMPLEXITY MEASURES IN SOFTWARE
Thomas W. Lynch
THS Corporation, 701 Brazos, Suite 500, Austin, Texas 78701
Nikos A. Salingaros
Division of Mathematics, University of Texas at San Antonio, San Antonio, Texas 78249.
ABSTRACT
New complexity measures relevant to computer science are introduced. Previous measures for measuring the complexity in buildings architecture are used to motivate these results. We combine complexity concepts from execution time, hardware, and software to give an overall measure. This measure can be applied to any situation, thus making it a practical estimation tool. A ripple carry adder is used to analyze a specific example of complexity, and illustrates the results obtainable by this method.
1. Introduction
In this paper we attempt to find quantitative measures that correspond to our intuitive sense for the meaning of complexity, as that term is applied to computer hardware. This paper is not the first forum where this has been attempted. Existing measures of complexity include fundamental component counts, connection architectures, and computation models. We show that the question of hardware complexity is related to that of software complexity in Section 2. We then take up the dual discussion for computer software complexity in Section 3. Section 4 introduces a program that illustrates the complexity measures developed in the preceding sections, and solves the problem of designing an efficient adder.
This work is motivated by new results in buildings architecture (not computer architecture) that defines quantitative measures of complexity. It is possible to use the insights obtained in that context to distinguish between organized and disorganized complexity. This distinction makes a great difference in how we can formulate complexity. Most important, it helps to establish a connection with human perception of complexity, a topic that has been rather elusive up until now. In particular, McCabe's cyclomatic complexity measure ties in with this perceptual complexity. This is discussed in Section 5.
2. Complexity of Computer Hardware
I. Component Counts
The number of components used in the most complex computers has increased exponentially since the creation of the first computational devices. The following table gives some approximate figures:
Table 1. Increase of number of compenents with time.
Date
No. Of Components
1900
210
1910
1920
1930
1940
212
1950
1960
1970
216
1980
1990
2 20
2000
224
Amazingly, this increase in the number of components has been accompanied by steady decrease in the physical size of the machines.
II. Connection Architectures
The count of the number of components as a complexity measure is somewhat lacking because it does not consider the connection models. For example, a mesh machine could have a very large number of identical processors repeated in an array. Even though this requires many components, intuitively we would consider this design to be simple. On the other hand a neural network may have a small number of identical components hacked up in a rat's nest of wire. Intuitively we would want to call this design complex. Therefore, the component count appears to be an indicator of the ultimate complexity measure, and not a base measure by itself.
Common computer architectures include neural networks, mesh networks, large grain parallel machines, fine grain parallel machines, CISC machines, and RISC machines, etc. These machines use various trade offs between connections and components. A quick indication of complexity is when the machine was invented, but that is not very useful. Possible measures of the complexity of these machines might include:
1) How understandable the architecture is.
2) How thick the specification is.
3) How big is a program which could draw the engineering diagrams.
The first measure is the most intuitive, and is connected to our own perceptive mechanisms. There is a link between artificial complexity and our mind, and it is an illuminating one. Nevertheless, discussion will be deferred to a later section, since its essential insight is into human nature, and the mathematics is not fully developed.
Measures two and three are essentially the same. They differ only in the level of formalism in which the specification is stated. These measures reduce the question of complexity of the hardware to complexity of the program used to describe the hardware at time of manufacture. All computers of importance have schematic diagrams, even the mechanical machines. Hence, the question would be, if we had an optimum hierarchical graphic database of the machine design, how many bits would take it to encode? This is essentially an extension of the modified Kolmogorov complexity described in the next section.
III. Computation models.
In studying the ability of machines to recognize simple languages presented serially on a tape it has been discovered that there are fundamental limitations to certain configurations. In fact, this discovery is one of the pillars of computation theory [1]. Accordingly computers fall into three basic categories based on the complexity of language which they can recognize:
1) Finite State Machines
2) Push down Automata
3) Turing Machines
The first machine type can only recognize what are called "regular" languages. Finite state machines are characterized by the fact that there is no external memory source. I.e. the machine's abilities are fixed by its configuration. An example of a finite state machine is a parity generator. This machine has two states: 'Odd' and 'Even'. It starts in the 'Even' state. Each time a '1' is placed on its input it moves to the next state. Hence when the input is terminated, the machine is in the Odd state if an odd number of ones were supplied, otherwise it is in the even state.
The second type of machine is the "push down automaton". These are finite state machines in that they may change state in reaction to receiving an input letter; however they may also place a letter on the top of a 'stac', or pull a letter off the top of a stack. These machines can recognize languages which do not have a nested context. These are called the context free languages. Most computer languages are nearly context free, including Fortran, Pascal, C, etc.
The third type, the Turing Machine, is a finite state machine which can write characters to tape. Machines in this class are equivalent to a push down automaton modified to include two stacks. (Two stacks put together is the same as a tape.) These machines have some very interesting characteristics. For example, no machine has ever been demonstrated that can recognize a language which cannot already be recognized by a Turing Machine. This is not to say that there are no languages which cannot be recognized by Turing machines - these do exist.
According to this scheme the complexity of a computer can range among three different types based on how it handles memory. Type 1 would be a finite state machine, and type 3 would be a Turing machine. However, this fails to be very practical for the following reason: in the limit all machines are finite state machines, as memory is always limited. There are no true stacks or tapes in our world. We can get around the finite tape problem by noting that if a machine did not run out of tape while running a program, then the machine was indistinguishable from a Turing machine. Hence, a real machine is a Turing machine relative to a set of programs. This then begs the question of how complex are the programs which do not break the model? And once again we are asking about the complexity of programs.
3. Complexity of Computer Programs
The dual arguments for measuring the complexity of hardware exist for measuring the complexity of programs: Kolmogorov complexity (the number of bits the program uses), program structure, and algorithmic complexity. However, unlike in the previous section where we considered hardware, these items correspond to mathematical objects such as graphs.
I. Kolmogorov Complexity.
The Kolmogorov complexity is simply a measure of the minimum number of bits needed to code the program. Longer programs are more complex. This measure has a nice cross over to information theory, as the bit is also the fundamental unit of information. Thus one could say that, if a large number of fundamental pieces of information must be placed together to describe a program, then the program must be complex. This idea gives the first and crudest measure of complexity of a piece of software as the LOC - lines of code.
II. Program Structure.
Program structure includes the subroutine call structure and structure of data. Kolmogorov complexity is believed to include this effect since it requires a minimum program (in one way of looking at this problem). In the previous section we pointed out that a mesh machine is large but not as complex as a smaller neural network, and it would seem that an analogous flaw would be found here. However, if there is a loop iterator in the computer language, a program with a repeated pattern of instructions could be reduced to a smaller program with a loop. Hence the program for the mesh design would become smaller than that for the neural network.
A disturbing thing here is that we have discovered a relationship between the instructions that are allowed (e.g. the loop operator) in a program and the Kolmogorov complexity. We could attempt to remove this feature by requiring that the computer be a Turing machine. However, this leads to another disturbing conclusion, and that is that the operations provided by the Turing machine are somehow the most fundamental. This thought is disturbing because the formation of computation theory is not unique - there exist isomorphic systems which lead to the equivalent of Turing machines that are based on other operators. For example VanDer Poel showed that the operations "reverse subtract and branch on carry" could be used as a basis for a machine.
In the next section we propose a modified complexity measure which is simply related to Kolmogorov measure, but does not have these problems.
III. Algorithmic Complexity.
The highest order term of the function which describes the number of steps a Turing machine takes, as a function of the length of the input tape, for the worst case, is called the Algorithmic complexity.
For example, it is possible to define an optimum Turing machine for incrementing Arabic coded numbers which finishes operation in Y steps, where
Y = a X + b
X is the number of input characters (the number of digits in the input number). This machine is said to be a "linear time" algorithm. Since this is an optimum implementation, the operation of incrementing Arabic coded numbers is said to be a "Linear Time Complexity" problem. In the literature there also exist log time, polynomial time, and exponential time algorithms. It is often not known if these algorithms are optimal; thus it is not known if the corresponding problems are of Linear time complexity etc.
This type of complexity measure is also used for program size, i.e. the order of increase in the size of the Turing machine controller against increase in length of the input tape. We suspect that this is also invariant with the way the universal machine is derived. Hence a two dimensional object is suggested for the complexity of a program:
<O(T),O(A))>
where the first component is the time complexity, and the second is the size complexity.
IV. Specific Algorithmic Complexity.
Given a fixed computation model other than a Turing machine, we can define a specialized complexity measure based on that given in section III.
< T, A>
Where T is the time to run a program as a function of some interesting variables, and A is the number of operator instantiations.
For example, consider a simple computer which has the following instruction:
add a,b,c ; c = a + b;
Say it takes one cycle to run the instruction Then a program which multiplies an input x by two is:
add x,x,y
Then running the program on n separate inputs would require it to have the complexity of:
< n,1>
Which shows linear execution time and a fixed sized program of length 1.
int i = 0
loop:
if( i >= N ) goto end
full_adder( A(i), B(i), C(i) ) -> (S(i),C(i+1)
goto loop
end:
where N is the size of the operands. Then, again according to the previous section, the specific form of the complexity measure is:
<3 + N, 5>
4. The Ripple Carry Adder
Actually when we look at a design (or rather a program to create it) and ask ourselves how "complex" it is, I consider how hard it would be to remember how, or to figure out how to generate the program, not the design. In the terminology of computer science, I ask the meta question: if I had to write a program to generate the program, how long would that program be? The material developed in the last section is now going to be applied to the program which generates the program that describes the design.
For example, say we have a computer which adds numbers by using a ripple carry adder, whose schematic would look something like this:
C4 | .------. B3 --------| |-------- S3 A3 --------| | \______/ | | C3 .------. B2 --------| |-------- S2 A2 --------| | \______/ | | C2 .------. B1 --------| |-------- S1 A1 --------| | \______/ | | C1 .------. B0 --------| |-------- S0 A0 --------| | \______/ | C0
The boxes are "full" adders, and the lines are wires. (Of course such patterns could describe a lot of "designs", not just computers). Thus, as described in the method proposed in the previous sections, I will consider the full adder, conditional goto, assignment, and integer comparison to be my "specific" operators. For this example, each operator will be considered to take the same amount of time. Then the shortest program which produces this design is:
int i = 0
if( i >= N ) goto end
full_adder( A(i), B(i), C(i) ) -> (S(i),C(i+1)
end:
where N is the size of the operands. Then, again according to the previous section, the specific form of the complexity measure is:
< 2 + N, 4>
Where the first term is evaluation size, and the second is program size. If we wanted the general form, <O(T),O(A)> then we would find
<linear, constant>
As the Turing machine would require a linear number of steps to perform the operation as a function of the input tape length (where the operands are placed). The second component is a constant, since the Turing machine controller encoding is always the same.
Notice that this second component will often be constant, in fact always in conventional computation theory. Also we had to arbitrarily insert the parameter "N" in order to capture the essence of the time complexity - even though the design stated "4". This insertion is justifiable as it stems from our assumption about "acting like a Turing machine for a set of inputs", as described in the previous section. Perhaps the second term of the complexity measure should have a similar parameter.
Let us consider the program which would generate the program given above, and include its complexity measure in order to generate a second order complexity measure:
<O(T,Design Program), <O(T,Meta Design Program), O(A,Meta Design Program)>
For specific operators for this program we will choose "write instruction", integer operations, and goto. Then the meta program looks like this:
write("int i = 0")
write("if( i >= N ) goto end")
write("full_adder( A(i), B(i), C(i) ) -> (S(i),C(i+1)")
write("end:")
Just four operator calls and no loops, and the measure now looks like this:
<linear, <constant, constant>>
which captures nicely the essential simplicity of the design under consideration.
However, we have now opened the possibility of an "Nth" order complexity measure - where this nesting of meta programs is continued until only "constant" order operations are found. In this Nth order measure the information about the complexity will be completely embedded in the structure (nesting of < >) and none will be the tokens (i.e. the word "constant"). Hence, I can now define the "ultimate" complexity measure as the size of the program which generates the Nth order complexity measure - where, as described, N is the smallest value which causes all "constant" tokens to appear in the complexity measure.
To apply this idea to the example, we first remove the leading "linear" term by noting that linear programs can be generated using a constant size program that runs in constant time, and we are left with:
<<constant,constant>, <constant, constant>>
The commas add nothing to the notation, so it can be reduced to:
<<constant constant> <constant constant>>
Now this expression can be generated from the specific operators:
operator 1:
print_token("constant")
operator 2:
print_pair( item1 item2)
And the final program is:
print_pair(
print_pair(print_token)
print_pair(print_token)
)
Which calls three operators, so the ultimate complexity of the adder design is:
3
This problem is now completely solved.
5. Perceptual complexity.
This research was originally motivated by results on the complexity of buildings architecture (as distinct from computer architecture). We derive a formula expressing the comprehensibility of architectural form in terms of a product [2]. One component is the degree of differentiations, and the other component is the degree of linkages between disparate forms. Experiments in visual perception show that the way forms are perceived correlates in large measure with the figures computed for this visual complexity. Further, we have distinguished between organized complexity, which is easily graspable, and disorganized complexity, which is not. Therefore, systems with a high degree of complexity are understandable in drastically different ways, depending on how their complexity is organized.
A similar general idea has been used to understand the complexity of a computer, either the hardware or the software. For both of these, the essential structure may be displayed in a graph showing nodes and links. This approach using graph theory has led to the classic result of McCabe on graph-theoretic complexity [3]. One can decompose the link structure into its different subgraphs, and compute what is known as the cyclomatic number. The complexity then corresponds directly to the number of linearly independent paths.
We will not review this work here. What is of essence is the connection between intuitive complexity (as perceived by the human mind) and the computed complexity from graph-theoretic methods. Both McCabe's work, and our own work on architectural complexity, establish this (even in a rough manner). The conclusion is that future work on complexity must also include this aspect of cognitive complexity, which has been neglected up until now.
6. Conclusion
Using only very simple concepts of complexity, we have developed a way of treating and solving complex design problems in software design. The method was illustrated by designing a ripple carry adder. These results should be developed further, and can be used for the optimization of computer programs of arbitrary complexity.
REFERENCES
1. Harry Lewis and Christos Papadimitriou, "Elements of the Theory of Computation".
2. Nikos A. Salingaros, "Life and Complexity in Architecture From a Thermodynamic Analogy" Physics Essays 10 (1997) 165-173.
3. Thomas McCabe, "A Complexity Measure", IEEE Transact. Software Eng. SE-2 (1976), 308-320.