Does indirect addressing matter?
- PDF / 182,419 Bytes
- 7 Pages / 439.37 x 666.142 pts Page_size
- 67 Downloads / 265 Views
Does indirect addressing matter? A note Michael Brand
Received: 4 May 2012 / Accepted: 19 September 2012 / Published online: 27 October 2012 © Springer-Verlag Berlin Heidelberg 2012
Abstract In the study of random access machines (RAMs) and the complexities associated with their algorithms, the availability of indirect addressing often creates an analysis obstacle. We show that for RAMs equipped with a sufficiently rich set of basic operations, indirect addressing does not increase computational power, and can be simulated either in linear time or on-line in real time. These results pertain to the uniform cost model and, particularly, assume a unit cost variable shift.
1 Introduction The Turing machine, first introduced in [10], is undoubtedly the most familiar computational model. However, for algorithm analysis it often fails to adequately represent real-life complexities, for which reason the random access machine (RAM), closely resembling the intuitive notion of an idealized computer, has become the common choice in algorithm design. Quoting [3]: The random access machine (RAM) seems to be the computational model in widest use for algorithm design and analysis. The RAM is intended to model what we are used to in conventional programming, idealized in order to be better accessible for theoretical study. [It is] the standard platform for the study of algorithms. A full description of RAMs is given in [1]. We summarize here briefly. Computations on RAMs are described by programs. RAM programs are sets of commands, each given a label. Without loss of generality, labels are taken to be consecutive integers. The bulk of RAM commands belong to one of two types. One type is an assignment. It is described by a triplet containing a k-ary operation, k operands and a target register. The other type is a comparison. It is given two operands and a comparison operation, and is equipped with labels
M. Brand (B) Faculty of IT, Monash University, Clayton, VIC 3800, Australia e-mail: [email protected]
123
486
M. Brand
to proceed to if the comparison is evaluated as either true or false. Other command-types include unconditional jumps and execution halt commands. The execution model for RAM programs is as follows. The RAM is considered to have access to an infinite set of registers, each marked by a non-negative integer. The input to the program is given as the initial state of the first registers. The rest of the registers are initialized to 0. Program execution begins with the command labeled 1 and proceeds sequentially, except in comparisons (where execution proceeds according to the result of the comparison) and in jumps. When executing assignments, the k-ary operator is evaluated based on the values of the k operands and the result is placed in the target register. The output of the program is the state of the first registers at program termination. (Alternatively, and more resembling Turing machines, RAMs may be equipped with special halting instructions that either “accept” or do not.) For simplicit
Data Loading...
