Subject: Re: [boost] [random] status on discard(), PRF, and SOC2010 quasi-random
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2012-03-18 19:13:40
On 03/18/2012 02:22 PM, Topher Cooper wrote:
> 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).
Can you file a ticket at http://svn.boost.org/ for
this so I don't forget it?
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk