In computing, especially computational geometry, a real RAM (random-access machine) is a mathematical model of a computer that can compute with exact real numbers instead of the binary fixed point or floating point numbers used by most actual computers. The real RAM was formulated by Michael Ian Shamos in his 1978 Ph.D. dissertation.[1]

Model

The "RAM" part of the real RAM model name stands for "random-access machine". 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 unit consisting of an array of cells, and a central processing unit 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 problems in polynomial time.[2]

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

Implementation

Software libraries 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 structures 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.[3] 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.[4]

Comparison to other computational models

References

  1. ^ Shamos, Michael Ian (1978), Computational Geometry, Ph.D. dissertation, Yale University.
  2. ^ Schönhage, Arnold (1979), "On the power of random access machines", Proceedings of the Sixth International Colloquium on Automata, Languages and Programming (ICALP '79), Lecture Notes in Computer Science, vol. 71, Springer, pp. 520–529, doi:10.1007/3-540-09510-1_42, ISBN 978-3-540-09510-1, MR 0573259.
  3. ^ Melhorn, Kurt; Näher, Stefan (1999). The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press. Retrieved 12 November 2019.
  4. ^ Mehlhorn, Kurt; Schirra, Stefan (2001), "Exact computation with leda_real—theory and geometric applications" (PDF), Symbolic Algebraic Methods and Verification Methods (Dagstuhl, 1999), Springer, pp. 163–172, doi:10.1007/978-3-7091-6280-4_16, ISBN 978-3-211-83593-7, MR 1832422.
  5. ^ Grötschel, M.; Lovász, L.; Schrijver, A. (1981-06-01). "The ellipsoid method and its consequences in combinatorial optimization". Combinatorica. 1 (2): 169–197. doi:10.1007/BF02579273. ISSN 1439-6912.
  6. ^ Blum, Lenore; Shub, Mike; Smale, Steve (1989), "On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines", Bulletin of the American Mathematical Society, 21 (1): 1–46, doi:10.1090/S0273-0979-1989-15750-9, Zbl 0681.03020.