5 \chapter{Fine Details of Computation}
7 \section{Models and machines}
9 Traditionally, computer scientists use a~variety of computational models
10 for a~formalism in which their algorithms are stated. If we were studying
11 NP-completeness, we could safely assume that all the models are equivalent,
12 possibly up to polynomial slowdown, which is negligible. In our case, the
13 differences between good and not-so-good algorithms are on a~much smaller
14 scale. In this chapter, we will replace our yardsticks by a~micrometer,
15 define our computation models carefully and develop a repertoire of basic
16 data structures taking advantage of the fine details of the models.
18 We would like to keep the formalism close enough to the reality of the contemporary
19 computers. This rules out Turing machines and similar sequentially addressed
20 models, but even the remaining models are subtly different. For example, some of them
21 allow indexing of arrays in constant time, while the others have no such operation
22 and arrays have to be emulated with pointer structures, requiring $\Omega(\log n)$
23 time to access a~single element of an~$n$-element array. It is hard to say which
24 way is superior --- most ``real'' computers have instructions for constant-time
25 indexing, but on the other hand it seems to be physically impossible to fulfil
26 this promise with an~arbitrary size of memory. Indeed, at the level of logical
27 gates, the depth of the actual indexing circuits is logarithmic.
29 In recent decades, most researchers in the area of combinatorial algorithms
30 were considering two computational models: the Random Access Machine and the Pointer
31 Machine. The former one is closer to the programmer's view of a~real computer,
32 the latter one is slightly more restricted and ``asymptotically safe.''
33 We will follow this practice and study our algorithms in both models.
36 The \df{Random Access Machine (RAM)} is not a~single model, but rather a~family
37 of closely related models, sharing the following properties.
38 (See Cook and Reckhow \cite{cook:ram} for one of the common formal definitions
39 and Hagerup \cite{hagerup:wordram} for a~thorough description of the differences
40 between the RAM variants.)
42 The \df{memory} of the model is represented by an~array of \df{memory cells}
43 addressed by non-negative integers, each of them containing a~single non-negative integer.
44 The \df{program} is a~sequence of \df{instructions} of two basic kinds: calculation
45 instructions and control instructions.
47 \df{Calculation instructions} have two source arguments and one destination
48 argument, each \df{argument} being either an~immediate constant (not available
49 as destination), a~directly addressed memory cell (specified by its number)
50 or an~indirectly addressed memory cell (its address is stored in a~directly
51 addressed memory cell).
53 \df{Control instructions} include branches (to a~specific instruction in
54 the program), conditional branches (e.g., jump if two arguments specified as
55 in the calculation instructions are equal) and an~instruction to halt the program.
57 At the beginning of the computation, the memory contains the input data
58 in specified memory cells and arbitrary values in all other cells.
59 Then the program is executed one instruction at a~time. When it halts,
60 specified memory cells are interpreted as the program's output.
63 In the description of the RAM family, we have omitted several properties
64 on~purpose, because different members of the family define them differently.
65 These are: the size of the available integers, the time complexity of a~single
66 instruction, the space complexity of a~single memory cell and the repertoire
67 of operations available in calculation instructions.
69 If we impose no limits on the magnitude of the numbers and we assume that
70 arithmetic and logical operations work on them in constant time, we get
71 a~very powerful parallel computer --- we can emulate an~exponential number
72 of parallel processors using arithmetics and suddenly almost everything can be
73 computed in constant time, modulo encoding and decoding of input and output.
74 Such models are unrealistic and there are two basic possibilities how to
78 \:Keep unbounded numbers, but increase costs of instructions: each instruction
79 consumes time proportional to the number of bits of the numbers it processes,
80 including memory addresses. Similarly, space usage is measured in bits,
81 counting not only the values, but also the addresses of the respective memory
83 \:Place a~limit on the size of the numbers ---define the \df{word size~$W$,}
84 the number of bits available in the memory cells--- and keep the cost of
85 of instructions and memory cells constant. The word size must not be constant,
86 since we can address only~$2^W$ cells of memory. If the input of the algorithm
87 is stored in~$N$ cells, we need~$W\ge\log N$ just to be able to read the input.
88 On the other hand, we are interested in polynomial-time algorithms only, so $\Theta(\log N)$-bit
89 numbers should be sufficient. In practice, we pick~$w$ to be the larger of
90 $\Theta(\log N)$ and the size of integers used in the algorithm's input and output.
93 Both restrictions easily avoid the problems of unbounded parallelism. The first
94 choice is theoretically cleaner and Cook et al.~show nice correspondences to the
95 standard complexity classes, but the calculations of time and space complexity tend
96 to be somewhat tedious. What more, when compared with the RAM with restricted
97 word size, the complexities are usually exactly $\Theta(w)$ times higher.
98 This does not hold in general (consider a~program which uses many small numbers
99 and $\O(1)$ large ones), but it is true for the algorithms we are interested in.
100 Therefore we will always assume that the operations have unit cost and we make
101 sure that all numbers are limited by the available word size.
104 As for the choice of RAM operations, the following three instruction sets are often used:
107 \:\df{Word-RAM} --- allows the ``C-language operators'', i.e., addition,
108 subtraction, multiplication, division, remainder, bitwise {\sc and,} {\sc or,} exclusive
109 {\sc or} ({\sc xor}), negation ({\sc not}) and bitwise shifts ($\ll$ and~$\gg$).
110 \:\df{${\rm AC}^0$-RAM} --- allows all operations from the class ${\rm AC}^0$, i.e.,
111 those computable by constant-depth polynomial-size boolean circuits with unlimited
112 fan-in and fan-out. This includes all operations of the Word-RAM except for multiplication,
113 division and remainders, and also many other operations like computing the Hamming
114 weight (number of bits set in a~given number).
115 \:Both restrictions at once.
118 Thorup discusses the usual techniques employed by RAM algorithms in~\cite{thorup:aczero}
119 and he shows that they work on both Word-RAM and ${\rm AC}^0$-RAM, but the combination
120 of the two restrictions is too weak. On the other hand, the intersection of~${\rm AC}^0$
121 with the instruction set of modern processors (e.g., adding some floating-point
122 operations and multimedia instructions present on the Intel's Pentium4) is
123 already strong enough.
125 \FIXME{References to CPU manuals}
127 We will therefore use the Word-RAM instruction set, mentioning differences from the
128 ${\rm AC}^0$-RAM where necessary.
131 When speaking of the \df{RAM,} we implicitly mean the version with numbers limited
132 by a~specified word size of $W$~bits, unit cost of operations and memory cells and the instruction
133 set of the Word-RAM. This corresponds to the usage in recent algorithmic literature,
134 although the authors rarely mention the details.
137 The \df{Pointer Machine (PM)} also does not have any well established definition. The
138 various kinds of pointer machines are mapped by Ben-Amram in~\cite{benamram:pm},
139 but unlike the RAM's they turn out to be equivalent up to constant slowdown.
140 Our definition will be closely related to the \em{linking automaton} proposed
141 by Knuth in~\cite{knuth:fundalg}, we will only adapt it to use RAM-like
142 instructions instead of an~opaque control unit.
144 The PM works with two different types of data: \df{symbols} from a~finite alphabet
145 and \df{pointers}. The memory of the machine consists of a~fixed amount of \df{registers}
146 (some of them capable of storing a~single symbol, each of the others holds a~single pointer)
147 and an~arbitrary amount of \df{cells}. The structure of all cells is the same: each of them
148 again contains a~fixed number of fields for symbols and pointers. Registers can be addressed
149 directly, the cells only via pointers --- either by using a~pointer stored in a~register,
150 or in a~cell pointed to by a~register (longer chains of pointers cannot be followed in
153 We can therefore view the whole memory as a~directed graph, whose vertices
154 correspond to the cells (the registers are stored in a~single special cell).
155 The outgoing edges of each vertex correspond to pointer fields and they are
156 labelled with distinct labels drawn from a~finite set. In addition to that,
157 each vertex contains a~fixed amount of symbols. The program can directly access
158 vertices within distance~2 from the register vertex.
160 The program is a~sequence of instructions of the following kinds:
163 \:\df{symbol instructions,} which read a~pair of symbols, apply an~arbitrary
164 function on them and write the result to a~symbol register or field;
165 \:\df{pointer instructions} for assignment of pointers to pointer registers/fields
166 and for creation of new memory cells (a~pointer to the new cell is assigned
168 \:\df{control instructions} --- similarly to the RAM; conditional jumps can decide
169 on~arbitrary unary relations on symbols and compare pointers for equality.
172 Time and space complexity are defined in the straightforward way: all instructions
173 have unit cost and so do all memory cells.
175 Both input and output of the machine are passed in the form of a~linked structure
176 pointed to by a~designated register. For example, we can pass graphs back and forth
177 without having to encode them as strings of numbers or symbols. This is important,
178 because with the finite alphabet of the~PM, all symbolic representations of graphs
179 require super-linear space and therefore also time.
182 Compared to the RAM, the PM lacks two important capabilities: indexing of arrays
183 and arithmetic instructions. We can emulate both with poly-logarithmic slowdown,
184 but it will turn out that they are rarely needed in graph algorithms. We are
185 also going to prove that the RAM is strictly stronger, so we will prefer to
186 formulate our algorithms in the PM model and use RAM only when necessary.
189 Every program for the Word-RAM with word size~$W$ can be translated to a~program
190 computing the same on the~PM with $\O(W^2)$ slowdown. If the RAM program does not
191 use multiplication, division and remainder operations, $\O(W)$~slowdown
195 Represent the memory of the RAM by a~balanced binary search tree or by a~radix
196 trie of depth~$\O(W)$. Values are encoded as~linked lists of symbols pointed
197 to by the nodes of the tree. Both direct and indirect accesses to the memory
198 can therefore be done in~$\O(W)$ time. Use standard algorithms for arithmetic
199 on big numbers: $\O(W)$ per operation except for multiplication, division and
200 remainders which take $\O(W^2)$.
204 Every program for the PM running in polynomial time can be translated to a~program
205 computing the same on the Word-RAM with only $\O(1)$ slowdown.
208 Encode each cell of the PM's memory to $\O(1)$ integers. Store the encoded cells to
209 memory of the RAM sequentially and use memory addresses as pointers. As the symbols
210 are finite and there is only a~polynomial number of cells allocated during execution
211 of the program, $\O(\log N)$-bit integers suffice.
216 \FIXME{Mention functional programming and immutable models}