This page is a snapshot from the LWG issues list, see theLibrary Active Issues List for more information and the meaning ofCD1 status.
Section: 29.5.8.1[rand.util.seedseq]Status:CD1Submitter: Charles KarneyOpened: 2007-05-15Last modified: 2016-01-28
Priority:Not Prioritized
View all otherissues in [rand.util.seedseq].
View all issues withCD1 status.
Discussion:
seed_seq::randomize provides a mechanism for initializing random numberengines which ideally would yield "distant" states when given "close"seeds. The algorithm forseed_seq::randomize given in the currentWorking Draft for C++,N2284(2007-05-08), has 3 weaknesses
Collisions in state. Because of the way the state is initialized, seeds of different lengths may result in the same state. The current version of seed_seq has the following properties:
s <= n, each of the 2^(32s) seed vectors results in a distinct state.The proposed algorithm (below) has the considerably stronger properties:
(2^(32n)-1)/(2^32-1) seed vectors of lengthss < n result in distinct states.2^(32n) seed vectors of lengths == n result in distinct states. Poor mixing ofv's entropy into the state. Considerv.size() == n and holdv[n/2] thruv[n-1] fixed while varyingv[0] thruv[n/2-1], a total of2^(16n) possibilities. Because of the simple recursion used inseed_seq,begin[n/2] thrubegin[n-1] can take on only 2^64 possible states.
The proposed algorithm uses a more complex recursion which results in much better mixing.
seed_seq::randomize is undefined forv.size() == 0. The proposed algorithm remedies this.The current algorithm forseed_seq::randomize is adapted by me from theinitialization procedure for the Mersenne Twister by Makoto Matsumotoand Takuji Nishimura. The weakness (2) given above was communicated tome by Matsumoto last year.
The proposed replacement forseed_seq::randomize is due to Mutsuo Saito,a student of Matsumoto, and is given in the implementation of theSIMD-oriented Fast Mersenne Twister random number generator SFMT.http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.htmlhttp://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/SFMT-src-1.2.tar.gz
SeeMutsuo Saito,An Application of Finite Field: Design and Implementation of 128-bitInstruction-Based Fast Pseudorandom Number Generator,Master's Thesis, Dept. of Math., Hiroshima University (Feb. 2007)http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/M062821.pdf
One change has been made here, namely to treat the case of smalln(settingt = (n-1)/2 forn < 7).
Sinceseed_seq was introduced relatively recently there is little costin making this incompatible improvement to it.
SeeN2391 andN2423for some further discussion.
Proposed resolution:
Adopt the proposed resolution inN2423.
[Kona (2007): The LWG adopted the proposed resolution of N2423 for this issue.The LWG voted to accelerate this issue to Ready status to be voted into the WP at Kona.]