Jump to content

Word RAM

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Citation bot (talk | contribs) at 20:57, 14 February 2019 (Alter: title. Add: citeseerx, isbn, title-link. | You can use this bot yourself. Report bugs here. | User-activated.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In theoretical computer science, the word RAM (word random access machine) model is a model of computation that is a random access machine able to do bitwise operations on a single word of w bits. The model was created by Michael Fredman and Dan Willard in 1990 to simulate programming languages like C.[1]

Model

The word RAM model is an abstract machine similar to a random access machine, but with additional capabilities. It works with words of size up to w bits, meaning it can store integers up to size . Because the model assumes that the word size matches the problem size, that is, for a problem of size n, , the word RAM model is a transdichotomous model. The model allows bitwise operations such as arithmetic and logical shifts to be done in constant time.[2] The number of possible values is U, where .

Algorithms and data structures

In the word RAM model, integer sorting can be done fairly efficiently. Yijie Han and Mikkel Thorup created a randomized algorithm to sort integers in expected time of (in Big O notation) ,[3] while Han also created a deterministic variant with running time .[4]

The dynamic predecessor problem is also commonly analyzed in the word RAM model, and was the original motivation for the model. Dan Willard used y-fast tries to solve this in time.[2] Michael Fredman and Willard also solved the problem using fusion trees in time.[1]

See also

References

  1. ^ a b Fredman, Michael; Willard, Dan (1990). "Blasting through the information theoretic barrier with fusion trees". Symposium on Theory of Computing: 1–7.
  2. ^ a b Wilkinson, Bryan (2015). Exploring the Problem Space of Orthogonal Range Searching (PDF) (PhD). Aarhus University.
  3. ^ Han, Yijie; Thorup, M. (2002), "Integer sorting in O(nlog log n) expected time and linear space", Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS 2002), IEEE Computer Society, pp. 135–144, CiteSeerX 10.1.1.671.5583, doi:10.1109/SFCS.2002.1181890, ISBN 978-0-7695-1822-0
  4. ^ Han, Yijie (2004), "Deterministic sorting in O(n log log n) time and linear space", Journal of Algorithms, 50 (1): 96–105, doi:10.1016/j.jalgor.2003.09.001, MR 2028585