803. Simplification of seed_seq::seq_seq

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:

  1. Distinctness of the output of seed_seq::generate required the introduction of the initial "if (w < 32) v.push_back(n);" (Otherwise the unsigned short vectors [1, 0] and [1] generate the same sequence.)
  2. Portability demanded the introduction of the template parameter u. (Otherwise some sequences could not be obtained on computers where no integer types are exactly 32-bits wide.)
  3. The description and algorithm have become unduly complicated.

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 232);

Discussion:

The chief virtues here are simplicity, portability, and generality.

Arguments (and counter-arguments) against making this change (and retaining the n2461 behavior) are:

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.

(moots 782 and 800)

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-1i=0 (begin[i] mod 2u) · 2w·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 232), b /= 232;

for (InputIterator s = begin; s != end; ++s) v.push_back((*s) mod 232);

Rationale:

Addressed by N2836 "Wording Tweaks for Concept-enabled Random Number Generation in C++0X".