Changes between Initial Version and Version 2 of Ticket #6706


Ignore:
Timestamp:
Apr 5, 2014, 6:34:27 PM (9 years ago)
Author:
Steven Watanabe
Comment:

Fixed in ​http://github.com/boostorg/random/commit/39d05f01614af0e8d46f97c3395b912fccf1fc79. 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.

Legend:

Unmodified
Added
Removed
Modified

  • Ticket #6706 – Description

    initial v2  
    1212http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/jump-seta-lfsr.pdf
    1313
    14 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).
     14If 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).