Section: 29.5.8.1 [rand.util.seedseq] Status: CD1 Submitter: Charles Karney Opened: 2007-05-15 Last modified: 2016-01-28
Priority: Not Prioritized
View all other issues in [rand.util.seedseq].
View all issues with CD1 status.
Discussion:
seed_seq::randomize provides a mechanism for initializing random number
engines which ideally would yield "distant" states when given "close"
seeds. The algorithm for seed_seq::randomize given in the current
Working 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 lengths s < n
result in distinct states.
2^(32n) seed vectors of length s == n result in
distinct states.
Poor mixing of v's entropy into the state. Consider v.size() == n
and hold v[n/2] thru v[n-1] fixed while varying v[0] thru v[n/2-1],
a total of 2^(16n) possibilities. Because of the simple recursion
used in seed_seq, begin[n/2] thru begin[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 for v.size() == 0. The proposed
algorithm remedies this.
The current algorithm for seed_seq::randomize is adapted by me from the
initialization procedure for the Mersenne Twister by Makoto Matsumoto
and Takuji Nishimura. The weakness (2) given above was communicated to
me by Matsumoto last year.
The proposed replacement for seed_seq::randomize is due to Mutsuo Saito,
a student of Matsumoto, and is given in the implementation of the
SIMD-oriented Fast Mersenne Twister random number generator SFMT.
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/SFMT-src-1.2.tar.gz
See Mutsuo Saito, An Application of Finite Field: Design and Implementation of 128-bit Instruction-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 small n
(setting t = (n-1)/2 for n < 7).
Since seed_seq was introduced relatively recently there is little cost
in making this incompatible improvement to it.
See N2391 and N2423 for some further discussion.
Proposed resolution:
Adopt the proposed resolution in N2423.
[ 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. ]