Boost C++ Libraries: Ticket #6706: Mersenne Twister discard() speed improvement https://svn.boost.org/trac10/ticket/6706 <p> There is an algorithm for fast jump ahead for the MT: </p> <p> <a class="ext-link" href="http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/JUMP/index.html"><span class="icon">​</span>http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/JUMP/index.html</a> </p> <p> Some more references (thanks Topher!) </p> <p> 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 <a class="ext-link" href="http://dx.doi.org/10.1007/978-3-540-85912-3_26"><span class="icon">​</span>http://dx.doi.org/10.1007/978-3-540-85912-3_26</a> </p> <p> An accessible online copy is at: </p> <p> <a class="ext-link" href="http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/jump-seta-lfsr.pdf"><span class="icon">​</span>http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/jump-seta-lfsr.pdf</a> </p> <p> 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<sup>1.6</sup>) 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<sup>1.6</sup> (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). </p> en-us Boost C++ Libraries /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/6706 Trac 1.4.3 Steven Watanabe Tue, 18 Mar 2014 16:31:02 GMT <link>https://svn.boost.org/trac10/ticket/6706#comment:1 </link> <guid isPermaLink="false">https://svn.boost.org/trac10/ticket/6706#comment:1</guid> <description> <p> I'm working on implementing this, but the performance isn't really acceptable. The timings in the paper aren't really relevant because the execution time is dominated by the calculation of <code>g(t) = t</code><sup><code>J</code></sup> <code>mod phi(t)</code>, which they precomputed as it only depends on <code>J</code>, not on the state of the generator. The interface of discard doesn't really allow <code>g(t)</code> to be precomputed, so we have to take the cost every time. </p> </description> <category>Ticket</category> </item> <item> <dc:creator>Steven Watanabe</dc:creator> <pubDate>Sat, 05 Apr 2014 18:34:27 GMT</pubDate> <title>description changed https://svn.boost.org/trac10/ticket/6706#comment:2 https://svn.boost.org/trac10/ticket/6706#comment:2 <ul> <li><strong>description</strong> modified (<a href="/trac10/ticket/6706?action=diff&amp;version=2">diff</a>) </li> </ul> <p> Fixed in <a class="ext-link" href="http://github.com/boostorg/random/commit/39d05f01614af0e8d46f97c3395b912fccf1fc79"><span class="icon">​</span>http://github.com/boostorg/random/commit/39d05f01614af0e8d46f97c3395b912fccf1fc79</a>. The algorithm is still slow (20-50 ms/jump on my machine), but it starts to become faster than the naive algorithm for a jump size of about 10,000,000. I'm leaving this ticket open for now, because I believe that a similar algorithm can be used for several other generators. In particular, the lagged_fibonacci generator has a structure which should be suitable for this. </p> Ticket