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

Danny Elfman

Image
Danny Elfman From Wikipedia, the free encyclopedia Jump to navigation Jump to search Danny Elfman Elfman at the 2010 San Diego Comic-Con Born Daniel Robert Elfman ( 1953-05-29 ) May 29, 1953 (age 65) Los Angeles, California, U.S. Spouse(s) Bridget Fonda ( m.  2003) Children 1 Musical career Genres Rock [1] ska [2] new wave film music video game music Occupation(s) Composer, singer, songwriter, record producer Instruments Trombone guitar percussion vocals keyboards [3] Years active 1972–present Associated acts Oingo Boingo James Newton Howard Daniel Robert Elfman (born May 29, 1953) is an American composer, singer, songwriter, and record producer. Elfman first became known for being the lead singer and songwriter for the band Oingo Boingo from 1974 to 1995. He is well known for scoring films and television shows, particularly his frequent collabora
Read more

Retrieve a Users Dashboard in Tumblr with R and TumblR. Oauth Issues

Image
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 0 I am trying to use the TumblR package in R to set up the Oauth Authentication to Retrieve a user's dashboard using the second example in tumblR documentation However I get the following error, it seems that using twitter others have been able to use a different function to get around this, but I am not finding the same function available for Tumblr. See twitter package for R authentication: error 401 My code consumer_key <- OKey consumer_secret <- SKey appname <- App_name tokenURL <- 'http://www.tumblr.com/oauth/request_token' accessTokenURL <- 'http://www.tumblr.com/oauth/acces_token'
Read more