Word RAM

<h2 id="model">Model</h2>
<p>The word RAM model is an <a href="/facts/Abstract_machine/zuC4RKLn">abstract machine</a> similar to a <a href="/facts/Random-access_machine/9NrNtVSd">random-access machine</a>, but with finite memory and word-length. It works with words of size up to w bits, meaning it can store <a href="/facts/Integer_(computing)/zWabo5M9">integers</a> up to 
  
    
      
        
          2
          
            w
          
        
        −
        1
      
    
    {\displaystyle 2^{w}-1}
  
. Because the model assumes that the <a href="/facts/Word_size/2e5umRaj">word size</a> matches the problem size, that is, for a problem of size n, 
  
    
      
        w
        ≥
        log
        ⁡
        n
      
    
    {\displaystyle w\geq \log n}
  
, the word RAM model is a <a href="/facts/Transdichotomous_model/HJerWPkt">transdichotomous model</a>.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> The model allows both arithmetic operations and <a href="/facts/Bitwise_operations/0gkqnUda">bitwise operations</a> including <a href="/facts/Logical_shift/EAYEcmrk">logical shifts</a> to be done in <a href="/facts/Constant_time/77T62gmf">constant time</a> (the precise instruction set assumed by an algorithm or proof using the model may vary).
</p>
<h2 id="algorithms-and-data-structures">Algorithms and data structures</h2>
<p>In the word RAM model, <a href="/facts/Integer_sorting/eItzeey5">integer sorting</a> can be done fairly efficiently. Yijie Han and <a href="/facts/Mikkel_Thorup/d6Jg15CD">Mikkel Thorup</a> created a <a href="/facts/Randomized_algorithm/Fngl1zgk">randomized algorithm</a> to sort integers in <a href="/facts/Expected_time/6TqLIMMz">expected time</a>  of (in <a href="/facts/Big_O_notation/weFFjSWg">Big O notation</a>) 
  
    
      
        O
        (
        n
        
          
            log
            ⁡
            log
            ⁡
            n
          
        
        )
      
    
    {\displaystyle O(n{\sqrt {\log \log n}})}
  
,<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> while Han also created a <a href="/facts/Deterministic_algorithm/v8x4wz35">deterministic</a> variant with <a href="/facts/Running_time/77T62gmf">running time</a> 
  
    
      
        O
        (
        n
        log
        ⁡
        log
        ⁡
        n
        )
      
    
    {\displaystyle O(n\log \log n)}
  
.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p><p>The <a href="/facts/Dynamic_predecessor_problem/ukC4bR7D">dynamic predecessor problem</a> is also commonly analyzed in the word RAM model, and was the original motivation for the model. <a href="/facts/Dan_Willard/EFn9KKzE">Dan Willard</a> used <a href="/facts/Y-fast_trie/RRAPcoeK">y-fast tries</a> to solve this in 
  
    
      
        O
        (
        log
        ⁡
        w
        )
      
    
    {\displaystyle O(\log w)}
  
 time, or, more precisely, 
  
    
      
        O
        (
        log
        ⁡
        log
        ⁡
        U
        )
      
    
    {\displaystyle O(\log \log U)}
  
 where U is a bound on the values stored.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> <a href="/facts/Michael_Fredman/KynAwavf">Michael Fredman</a> and Willard also solved the problem using <a href="/facts/Fusion_tree/dJo3u0b0">fusion trees</a> in 
  
    
      
        O
        (
        
          log
          
            w
          
        
        ⁡
        n
        )
      
    
    {\displaystyle O(\log _{w}n)}
  
 time.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> Using <a href="/facts/Exponential_tree/IlXLv1Fn">exponential search trees</a>, a query can be performed in 
  
    
      
        O
        (
        
          
            log
            ⁡
            n
            
              /
            
            log
            ⁡
            log
            ⁡
            n
          
        
        )
      
    
    {\displaystyle O({\sqrt {\log n/\log \log n}})}
  
.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a>
</p><p>Additional results in the word RAM model are listed in the article on <a href="/facts/Range_searching/Fkls9MD3">range searching</a>.
</p><p>Lower bounds applicable to word RAM algorithms are often proved in the <a href="/facts/Cell-probe_model/qaFmxzeA">cell-probe model</a>.
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Transdichotomous_model/HJerWPkt">Transdichotomous model</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Fredman, Michael; Willard, Dan (1990). "Blasting through the information theoretic barrier with fusion trees". Symposium on Theory of Computing: 1–7. <a href="/wiki/Michael_Fredman" target="_blank">/wiki/Michael_Fredman</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>In fact one usually assumes n to be smaller than 
  
    
      
        
          2
          
            w
          
        
      
    
    {\displaystyle 2^{w}}
  
, so that the data-structure considered can be indexed with w-bit addresses. <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>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 <a href="978-0-7695-1822-0" target="_blank">978-0-7695-1822-0</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>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 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Willard, Dan E. (1983). "Log-logarithmic worst-case range queries are possible in space Θ (N)". Information Processing Letters. 17 (2): 81–84. doi:10.1016/0020-0190(83)90075-3. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Fredman, Michael; Willard, Dan (1990). "Blasting through the information theoretic barrier with fusion trees". Symposium on Theory of Computing: 1–7. <a href="/wiki/Michael_Fredman" target="_blank">/wiki/Michael_Fredman</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>Andersson, Arne; Thorup, Mikkel (2007). "Dynamic ordered sets with exponential search trees". Journal of the ACM. 54 (3): 13. arXiv:cs/0210006. doi:10.1145/1236457.1236460. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
</ol>

Word RAM open-in-new

Word RAM