computing Computing is any goal-oriented activity requiring, benefiting from, or creating computer, computing machinery. It includes the study and experimentation of algorithmic processes, and the development of both computer hardware, hardware and softw ...

, especially computational geometry, a real RAM (

random-access machine In computer science, random-access machine (RAM or RA-machine) is a model of computation that describes an abstract machine in the general class of register machines. The RA-machine is very similar to the counter machine but with the added capab ...

) is a mathematical model of a computer that can compute with exact

real number In mathematics, a real number is a number that can be used to measure a continuous one- dimensional quantity such as a duration or temperature. Here, ''continuous'' means that pairs of values can have arbitrarily small differences. Every re ...

s instead of the binary fixed-point or

floating-point In computing, floating-point arithmetic (FP) is arithmetic on subsets of real numbers formed by a ''significand'' (a Sign (mathematics), signed sequence of a fixed number of digits in some Radix, base) multiplied by an integer power of that ba ...

numbers used by most actual computers. The real RAM was formulated by Michael Ian Shamos in his 1978 Ph.D. dissertation.

Model

The "RAM" part of the real RAM model name stands for "

". This is a model of computing that resembles a simplified version of a standard computer architecture. It consists of a stored program, a

computer memory Computer memory stores information, such as data and programs, for immediate use in the computer. The term ''memory'' is often synonymous with the terms ''RAM,'' ''main memory,'' or ''primary storage.'' Archaic synonyms for main memory include ...

unit consisting of an array of cells, and a

central processing unit A central processing unit (CPU), also called a central processor, main processor, or just processor, is the primary Processor (computing), processor in a given computer. Its electronic circuitry executes Instruction (computing), instructions ...

with a bounded number of registers. Each memory cell or register can store a real number. Under the control of the program, the real RAM can transfer real numbers between memory and registers, and perform arithmetic operations on the values stored in the registers. The allowed operations typically include addition, subtraction, multiplication, and division, as well as comparisons, but not modulus or rounding to integers. The reason for avoiding integer rounding and modulus operations is that allowing these operations could give the real RAM unreasonable amounts of computational power, enabling it to solve

PSPACE-complete In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length (PSPACE, polynomial space) and if every other problem that can be solved in polynomial sp ...

problems in polynomial time. When analyzing algorithms for the real RAM, each allowed operation is typically assumed to take

constant time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

Implementation

Software libraries In computing, a library is a collection of resources that can be leveraged during software development to implement a computer program. Commonly, a library consists of executable code such as compiled functions and classes, or a library can ...

such as LEDA have been developed which allow programmers to write computer programs that work as if they were running on a real RAM. These libraries represent real values using

data structure In computer science, a data structure is a data organization and storage format that is usually chosen for Efficiency, efficient Data access, access to data. More precisely, a data structure is a collection of data values, the relationships amo ...

s which allow them to perform arithmetic and comparisons with the same results as a real RAM would produce. For example, In LEDA, real numbers are represented using the leda_real datatype, which supports ''k''-th roots for any natural number ''k'', rational operators, and comparison operators. The time analysis of the underlying real RAM algorithm using these real datatypes can be interpreted as counting the number of library calls needed by a given algorithm.

Comparison to other computational models

* In the

Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...

model, the basic unit of computation involves one bit. Therefore, the time and space complexity of numeric algorithms depends on the number of bits needed to represent the numbers. In contrast, in the Real RAM model, the basic unit of computation involves a real number, regardless of how many bits are required to represent it. This difference is important when analyzing algorithms such as

Gaussian elimination In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of row-wise operations performed on the corresponding matrix of coefficients. This method can a ...

: this algorithm requires a polynomial number of arithmetic operations on real numbers, so it is polynomial in the Real RAM model; however, the numbers used in the intermediate computations may (if implemented naively) grow exponentially large, so its run-time in the Turing Machine model is exponential. * The real RAM closely resembles the later Blum–Shub–Smale machine.. However, the real RAM is typically used for the analysis of concrete algorithms in computational geometry, while the Blum–Shub–Smale machine instead forms the basis for extensions of the theory of

NP-completeness In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

to real-number computation. * An alternative to the real RAM is the word RAM, in which both the inputs to a problem and the values stored in memory and registers are assumed to be integers with a fixed number of bits. The word RAM model can perform some operations more quickly than the real RAM; for instance, it allows fast integer sorting algorithms, while sorting on the real RAM must be done with slower comparison sorting algorithms. However, some computational geometry problems have inputs or outputs that cannot be represented exactly using integer coordinates; see for instance the Perles configuration, an arrangement of points and line segments that has no integer-coordinate representation.

References

{{reflist

External links

Feasible Real Random Access Machines ReferencesGeometric Computing The Science of Making Geometric Algorithms Work
Classes of computers Computational science Computational geometry