Boost logo

Boost :

Subject: Re: [boost] [random] status on discard(), PRF, and SOC2010 quasi-random
From: Topher Cooper (topher_at_[hidden])
Date: 2012-03-18 17:22:55

On 3/18/2012 2:46 PM, Steven Watanabe wrote in reply to Thijs (M.A.) van
den Berg <thijs_at_[hidden]>:
>> Eg for MT these is a constant time algorithm, is there work being done on that?
> Really? Do you have a link?
There is:

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

An accessible online copy is at:

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).


Boost list run by bdawes at, gregod at, cpdaniel at, john at