# Word RAM

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Word_RAM
> Markdown URL: https://mediated.wiki/source/Word_RAM.md
> Source: https://en.wikipedia.org/wiki/Word_RAM
> Source revision: 1256156892
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [theoretical computer science](/source/theoretical_computer_science), the '''word RAM''' (word random-access machine) model is a [model of computation](/source/model_of_computation) in which a [random-access machine](/source/random-access_machine) does arithmetic and bitwise operations on a word of {{mvar|w}} bits. [Michael Fredman](/source/Michael_Fredman) and [Dan Willard](/source/Dan_Willard) created it in 1990 to simulate programming languages like [C](/source/C_(programming_language)).<ref name="Fredman90">{{cite journal|last1=Fredman|first1=Michael|author1-link=Michael Fredman|last2=Willard|first2=Dan|author2-link=Dan Willard|title=Blasting through the information theoretic barrier with fusion trees|journal=[Symposium on Theory of Computing](/source/Symposium_on_Theory_of_Computing)|pages=1–7|date=1990}}</ref>

== Model ==
The word RAM model is an [abstract machine](/source/abstract_machine) similar to a [random-access machine](/source/random-access_machine), but with finite memory and word-length. It works with words of size up to {{mvar|w}} bits, meaning it can store [integers](/source/integer_(computing)) up to <math>2^w-1</math>. Because the model assumes that the [word size](/source/word_size) matches the problem size, that is, for a problem of size {{mvar|n}}, <math>w \ge \log n</math>, the word RAM model is a [transdichotomous model](/source/transdichotomous_model).<ref>In fact one usually assumes {{mvar|n}} to be smaller than <math>2^w</math>, so that the data-structure considered can be indexed with {{mvar|w}}-bit addresses.</ref> The model allows both arithmetic operations and [bitwise operations](/source/bitwise_operations) including [logical shift](/source/logical_shift)s to be done in [constant time](/source/constant_time) (the precise instruction set assumed by an algorithm or proof using the model may vary).

== Algorithms and data structures ==
In the word RAM model, [integer sorting](/source/integer_sorting) can be done fairly efficiently. Yijie Han and [Mikkel Thorup](/source/Mikkel_Thorup) created a [randomized algorithm](/source/randomized_algorithm) to sort integers in [expected time](/source/expected_time)  of (in [Big O notation](/source/Big_O_notation)) <math>O(n \sqrt{\log \log n})</math>,<ref name="Han02">{{citation
 | last1 = Han | first1 = Yijie
 | last2 = Thorup | first2 = M. | author2-link = Mikkel Thorup
 | contribution = Integer sorting in {{math|O(''n''{{sqrt|log log ''n''}})}} expected time and linear space
 | doi = 10.1109/SFCS.2002.1181890
 | pages = 135–144
 | publisher = IEEE Computer Society
 | title = Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS 2002)
 | year = 2002| title-link = Symposium on Foundations of Computer Science
 | isbn = 978-0-7695-1822-0
 | citeseerx = 10.1.1.671.5583
 }}</ref> while Han also created a [deterministic](/source/deterministic_algorithm) variant with [running time](/source/running_time) <math>O(n \log \log n)</math>.<ref name="Han04">{{citation
 | last = Han | first = Yijie
 | doi = 10.1016/j.jalgor.2003.09.001
 | mr = 2028585
 | issue = 1
 | journal = Journal of Algorithms
 | pages = 96–105
 | title = Deterministic sorting in {{math|''O''(''n'' log log ''n'')}} time and linear space
 | volume = 50
 | year = 2004}}</ref>

The [dynamic predecessor problem](/source/dynamic_predecessor_problem) is also commonly analyzed in the word RAM model, and was the original motivation for the model. [Dan Willard](/source/Dan_Willard) used [y-fast trie](/source/y-fast_trie)s to solve this in <math>O(\log w)</math> time, or, more precisely, <math>O(\log\log U)</math> where {{mvar|U}} is a bound on the values stored.<ref>{{cite journal |last1=Willard |first1=Dan E. |title=Log-logarithmic worst-case range queries are possible in space Θ (N) |journal=Information Processing Letters |date=1983 |volume=17 |issue=2 |pages=81–84|doi=10.1016/0020-0190(83)90075-3 }}</ref> [Michael Fredman](/source/Michael_Fredman) and Willard also solved the problem using [fusion tree](/source/fusion_tree)s in <math>O(\log_w n)</math> time.<ref name="Fredman90"/> Using [exponential search trees](/source/exponential_tree), a query can be performed in <math>O(\sqrt{\log n / \log\log n})</math>.<ref>{{cite journal |last1=Andersson |first1=Arne |last2=Thorup |first2=Mikkel |title=Dynamic ordered sets with exponential search trees |journal=Journal of the ACM |date=2007 |volume=54 |issue=3 |page=13 |doi=10.1145/1236457.1236460|arxiv=cs/0210006 }}</ref>

Additional results in the word RAM model are listed in the article on [range searching](/source/range_searching).

Lower bounds applicable to word RAM algorithms are often proved in the [cell-probe model](/source/cell-probe_model).

== See also ==
* [Transdichotomous model](/source/Transdichotomous_model)

== References ==
{{reflist}}

Category: Models of computation

---
Adapted from the Wikipedia article [Word RAM](https://en.wikipedia.org/wiki/Word_RAM) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Word_RAM?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.