[Boost-bugs] [Boost C++ Libraries] #6706: Mersenne Twister discard() speed improvement

Subject: [Boost-bugs] [Boost C++ Libraries] #6706: Mersenne Twister discard() speed improvement
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2012-03-19 11:12:16

#6706: Mersenne Twister discard() speed improvement
------------------------------+---------------------------------------------
 Reporter:  info@…            |       Owner:  no-maintainer
     Type:  Tasks             |      Status:  new          
Milestone:  To Be Determined  |   Component:  random       
  Version:  Boost 1.48.0      |    Severity:  Optimization 
 Keywords:                    |  
------------------------------+---------------------------------------------
 There is an algorithm for fast jump ahead for the MT:

 http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/JUMP/index.html



 Some more references (thanks Topher!)

 Hiroshi Haramoto, Makoto Matsumoto, and Pierre L'Ecuyer. 2008. A Fast Jump
 Ahead Algorithm for Linear Recurrences in a Polynomial Space. In
 /Proceedings of the 5th international conference on Sequences and Their
 Applications/ (SETA '08), Solomon W. Golomb, Matthew G. Parker, Alexander
 Pott, and Arne Winterhof (Eds.). Springer-Verlag, Berlin, Heidelberg,
 290-298. DOI=10.1007/978-3-540-85912-3_26
 http://dx.doi.org/10.1007/978-3-540-85912-3_26


 An accessible online copy is at:

 http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/jump-seta-

 lfsr.pdf

 If I understand it correctly, whether or not it is "constant time" is a
 bit ambiguous.  Applying it to an arbitrary MT generator requires O(k^1.6)
 where k is the size of the state, and k must be moderately large before
 this asymptote is approached. For a particular generator the k is a
 constant so it is "constant time" -- i.e., constant in the size of the
 jumps.  So, for example, k for MT19937 is 19937 and so is k^1.6 (about 7.5
 million).  The timing tests in the paper seem to indicate reasonable
 performance for common applications (e.g., where generating the jumps is
 done infrequently relative to the number of calls to the generators
 themselves).

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/6706>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.