Word RAM

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 ${\displaystyle 2^{w}}$. Because the model assumes that the word size matches the problem size, that is, for a problem of size n, ${\displaystyle w\geq \log 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 ${\displaystyle U\leq 2^{w}}$.

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) ${\displaystyle O(n{\sqrt {\log \log n}})}$,[3] while Han also created a deterministic variant with running time ${\displaystyle O(n\log \log n)}$.[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 ${\displaystyle O(\log \log U)}$ time.[2] Michael Fredman and Willard also solved the problem using fusion trees in ${\displaystyle O(\log _{w}n)}$ time.[1]

See also

• Transdichotomous model

References

1. Fredman, Michael; Willard, Dan (1990). "Blasting through the information theoretic barrier with fusion trees". Symposium on Theory of Computing: 1–7.
2. 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(n√log 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