Word RAM

In theoretical computer science, the word RAM (word random-access machine) model is a model of computation in which a random-access machine does bitwise operations on a word of bits. Michael Fredman and Dan Willard created it 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 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 , $w \ge \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 , where $U \le 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)$, 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

References

{{reflist

Models of computation