Defect Report: Weaknesses in seed_seq::randomize [rand.util.seedseq]
Charles Karney
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 Mutso 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.
The following is the proposed replacement of paragraph 8 of section
26.4.7.1 [rand.util.seedseq]:
================================================================
8 Effects: With s = v.size() and n = end - begin, fills the supplied
range [begin,end) according to the following algorithm in which each
operation is to be carried out modulo 2^32, each indexing operator
applied to begin is to be taken modulo n, and T(x) is defined as
x xor (x rshift 27):
fill(begin, end, 0x8b8b8b8b);
if (n >= 623)
t = 11;
else if (n >= 68)
t = 7;
else if (n >= 39)
t = 5;
else if (n >= 7)
t = 3;
else
t = (n-1)/2;
p = (n-t)/2;
q = p+t;
m = max(s+1, n);
for (k = 0; k < m; k += 1) {
r = 1664525 * T(begin[k] ^ begin[k+p] ^ begin[k-1]);
begin[k+p] += r;
r += k % n;
if (k == 0)
r += s;
else if (k <= s)
r += v[k-1];
begin[k+q] += r;
begin[k] = r;
}
for (k = m; k < m + n; k += 1) {
r = 1566083941 * T(begin[k] + begin[k+p] + begin[k-1]);
begin[k+p] ^= r;
r -= k % n;
begin[k+q] ^= r;
begin[k] = r;
}
================================================================
B. Section 26.4.1.3 Random number engine requirements [rand.req.eng]
[This change follows naturally from the proposed change to
seed_seq::randomize given above.]
In table 104 the description of X(q) contains a special treatment of
the case q.size() == 0. This is undesirable for 4 reasons:
(1) It replicates the functionality provided by X().
(2) It leads to the possibility of a collision in the state provided
by some other X(q) with q.size() > 0.
(3) It is inconsistent with the description of the X(q) in paragraphs
26.4.3.1.5, 26.4.3.2.8, and 26.4.3.3.10 where there is no special
treatment of q.size() == 0.
(4) The proposed replacement for seed_seq::randomize given above
allows for the case q.size() == 0.
I recommend removing the special-case treatment of q.size() == 0. Here
is the replacement line for table 104 of section 26.4.1.3
[rand.req.eng]:
================================================================
expression: X(q)^272
return type: --
pre/post-condition: Create an engine u with an initial state which
depends on a sequence produced by one call to q.randomize.
complexity: O(max(q.size(), size of state))
================================================================
Please let me know if you have any questions.
--
Charles Karney <cka...@sarnoff.com>
Sarnoff Corporation, Princeton, NJ 08543-5300
URL: http://charles.karney.info
Tel: +1 609 734 2312
Fax: +1 609 734 2662
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std...@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]