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]




Contents






  • 1 Model


  • 2 Algorithms and data structures


  • 3 See also


  • 4 References





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 2w{displaystyle 2^{w}}2^{w}. Because the model assumes that the word size matches the problem size, that is, for a problem of size n, w≥log⁡n{displaystyle wgeq log n}{displaystyle wgeq 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 U≤2w{displaystyle Uleq 2^{w}}{displaystyle Uleq 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(nlog⁡log⁡n){displaystyle O(n{sqrt {log log n}})}{displaystyle O(n{sqrt {log log n}})},[3] while Han also created a deterministic variant with running time O(nlog⁡log⁡n){displaystyle O(nlog log n)}{displaystyle O(nlog 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 O(log⁡log⁡U){displaystyle O(log log U)}{displaystyle O(log log U)} time.[2]Michael Fredman and Willard also solved the problem using fusion trees in O(logw⁡n){displaystyle O(log _{w}n)}{displaystyle O(log _{w}n)} time.[1]



See also


  • Transdichotomous model


References





  1. ^ ab Fredman, Michael; Willard, Dan (1990). "Blasting through the information theoretic barrier with fusion trees". Symposium on Theory of Computing: 1–7..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output .citation q{quotes:"""""""'""'"}.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-maint{display:none;color:#33aa33;margin-left:0.3em}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}


  2. ^ ab 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









-

Popular posts from this blog

Florida Star v. B. J. F.

Image
Florida Star v. B. J. F. From Wikipedia, the free encyclopedia Jump to navigation Jump to search United States Supreme Court case Florida Star v. B. J. F. Supreme Court of the United States Argued March 21, 1989 Decided June 21, 1989 Full case name The Florida Star v. B. J. F. Citations 491 U.S. 524 ( more ) 109 S. Ct. 2603; 105 L. Ed. 2d 443; 1989 U.S. LEXIS 3120; 57 U.S.L.W. 4816; 16 Media L. Rep. 1801 Prior history The Florida Star v. B.J.F., 530 So.2d 286 (1988) Supreme Court of Florida; Florida Star v. B.J.F., 499 So.2d 883 (1986) Fla. Dist. Court of Appeals Holding Florida Stat. § 794.03 is unconstitutional to the extent it makes the truthful reporting of information that was a matter of public record unlawful, as it violates the First Amendment. Court membership Chief Justice William Rehnquist Associate Justices William J. Brennan Jr.  · Byron White Thurgood Marshall  · Harry Blac
Read more

Error while running script in elastic search , gateway timeout

Image
0 while running script in elastic search, I got 504 Gateway timeout error. { "query": { "bool": { "filter": { "script": { "script": " doc['creted_date'].date.getMonthOfYear() == 12 " } } } }, "aggs": { "test": { "date_histogram": { "field": "creted_date", "interval": "month", "format": "MMM" }, "aggs": { "cost": { "sum": { "field": "cost" } } }
Read more

Adding quotations to stringified JSON object values

Image
0 My stringified object data doesn't include quotation marks around object values, which errors when attempting JSON.parse() : '{ "affiliation": CORPORATE, "userId": 75c35d1c-5d12-4485-8fa8-b2f1551a3e6e }' I need the string to be: '{ "affiliation": "CORPORATE", "userId": "75c35d1c-5d12-4485-8fa8-b2f1551a3e6e" }' I'm using this regex to add quotes to the object keys: var newStr = str.replace(/(['"])?([a-z0-9A-Z_]+)(['"])?:/g, '"$2": '); For instance: '{ affiliation: CORPORATE }' to '{ "affiliation": CORPORATE }' There are only string values in my data, so I don't need to check value types. How can I alter my regex expression to add quotations to
Read more