Section: 29.6.7.1 [rand.util.seedseq] Status: Resolved Submitter: Charles Karney Opened: 2008-02-22 Last modified: 2016-02-10
Priority: Not Prioritized
View all other issues in [rand.util.seedseq].
View all issues with Resolved status.
Discussion:
seed_seq(InputIterator begin, InputIterator end); constructs a seed_seq object repacking the bits of supplied sequence [begin, end) into a 32-bit vector.
This repacking triggers several problems:
I propose simplifying this seed_seq constructor to be "32-bit only". Despite it's being simpler, there is NO loss of functionality (see below).
Here's how the description would read
29.6.7.1 [rand.util.seedseq] Class seed_seq
template<class InputIterator> seed_seq(InputIterator begin, InputIterator end);5 Requires: NO CHANGE
6 Effects: Constructs a seed_seq object by
for (InputIterator s = begin; s != end; ++s) v.push_back((*s) mod 2^{32});
Discussion:
The chief virtues here are simplicity, portability, and generality.
Arguments (and counter-arguments) against making this change (and retaining the n2461 behavior) are:
The user can pass an array of unsigned char and seed_seq will nicely repack it.
Response: So what? Consider the seed string "ABC". The n2461 proposal results in
v = { 0x3, 0x434241 };
while the simplified proposal yields
v = { 0x41, 0x42, 0x43 };
The results produced by seed_seq::generate with the two inputs are different but nevertheless equivalently "mixed up" and this remains true even if the seed string is long.
With long strings (e.g., with bit-length comparable to the number of bits in the state), v is longer (by a factor of 4) with the simplified proposal and seed_seq::generate will be slower.
Response: It's unlikely that the efficiency of seed_seq::generate will be a big issue. If it is, the user is free to repack the seed vector before constructing seed_seq.
A user can pass an array of 64-bit integers and all the bits will be used.
Response: Indeed. However, there are many instances in the n2461 where integers are silently coerced to a narrower width and this should just be a case of the user needing to read the documentation. The user can of course get equivalent behavior by repacking his seed into 32-bit pieces. Furthermore, the unportability of the n2461 proposal with
unsigned long s[] = {1, 2, 3, 4}; seed_seq q(s, s+4);
which typically results in v = {1, 2, 3, 4} on 32-bit machines and in v = {1, 0, 2, 0, 3, 0, 4, 0} on 64-bit machines is a major pitfall for unsuspecting users.
Note: this proposal renders moot issues 782 and 800.
[ Bellevue: ]
Walter needs to ask Fermilab for guidance. Defer till tomorrow. Bill likes the proposed resolution.
[ Sophia Antipolis: ]
Marc Paterno wants portable behavior between 32bit and 64bit machines; we've gone to significant trouble to support portability of engines and their values.
Jens: the new algorithm looks perfectly portable
Marc Paterno to review off-line.
Modify the proposed resolution to read "Constructs a seed_seq object by the following algorithm ..."
Disposition: move to review; unanimous consent.
Proposed resolution:
Change 29.6.7.1 [rand.util.seedseq]:
template<class InputIterator, size_t u = numeric_limits<iterator_traits<InputIterator>::value_type>::digits> seed_seq(InputIterator begin, InputIterator end);-5- Requires: InputIterator shall satisfy the requirements of an input iterator (24.1.1) such that iterator_traits<InputIterator>::value_type shall denote an integral type.
-6- Constructs a seed_seq object by the following algorithm
rearranging some or all of the bits of the supplied sequence [begin,end) of w-bit quantities into 32-bit units, as if by the following:
First extract the rightmost u bits from each of the n = end - begin elements of the supplied sequence and concatenate all the extracted bits to initialize a single (possibly very large) unsigned binary number, b = ∑^{n-1}_{i=0} (begin[i] mod 2^{u}) · 2^{w·i} (in which the bits of each begin[i] are treated as denoting an unsigned quantity). Then carry out the following algorithm:
v.clear(); if ($w$ < 32) v.push_back($n$); for( ; $n$ > 0; --$n$) v.push_back(b mod 2^{32}), b /= 2^{32};for (InputIterator s = begin; s != end; ++s) v.push_back((*s) mod 2^{32});
Rationale:
Addressed by N2836 "Wording Tweaks for Concept-enabled Random Number Generation in C++0X".