Proposed resolution:

Adopt the proposed resolution in N2423.

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

1. 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:

   • For a given s <= n, each of the 2^(32s) seed vectors results in a distinct state.

   The proposed algorithm (below) has the considerably stronger properties:

   • All of the (2^(32n)-1)/(2^32-1) seed vectors of lengths s < n result in distinct states.
   • All of the 2^(32n) seed vectors of length s == n result in distinct states.

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

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