Re: [boost] [random] status on discard(), PRF, and SOC2010 quasi-random

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

AMDG

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

Can you file a ticket at http://svn.boost.org/ for
this so I don't forget it?

In Christ,
Steven Watanabe