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.

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 $2^{w}$. Because the model assumes that the word size matches the problem size, that is, for a problem of size n, $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. The number of possible values is U, where $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) $O(n{\sqrt {\log \log n}})$, while Han also created a deterministic variant with running time $O(n\log \log n)$.

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 $O(\log \log U)$ time. Michael Fredman and Willard also solved the problem using fusion trees in $O(\log _{w}n)$ time.

See also

• Transdichotomous model