More on Issues with Random Number Generators in the Library TR Proposal

Issue 6 of N1535: Should Random Number Initializers Take Iterators by Reference or by Value?

(See also the thread started with Pete Becker's message c++std-lib-10785.)

The concern is that section 5.1.1, table 5.2 (Pseudo-random number engine requirements), specifies that engines can be constructed and seeded using an iterator range [it1, it2) of unsigned integral values. It appears surprising to the user that, unlike any other function or class in the standard library, the iterators are not both passed by value, but it1 is passed by reference, and is modified during the construction or seeding.

Any solution has to satisfy the following requirements (see also section III.E of N1452):

Engine constructors and seeding are visible and meant to be used by users.
Engines may be compounded of other engines; the compounding engine must be able to initialize its compounds.
Engines may have a large state (up to several KB) that should not be initialized twice for efficiency reasons.

There are two solutions to remedy this problem. The first keeps the iterator range, but passes the iterators by value. In order to avoid initializing the (potentially large) state of the engine twice, this requires that engines have a "construct, but don't seed" special constructor overload, similar to the "nothrow_t" overload of operator new.

The second avoids iterator ranges altogether, and instead passes a generator (i.e. zero-argument function object) by reference. There is a chance of ambiguous single-argument constructor and seeding overloads here, because most engines can be initialized with an "int" seed as well, but library implementors already have acquired a means to deal with the situation for the similar case of two-argument std::vector constructors. The advantage of passing a generator by reference is that the user can easily decide the behaviour on "end-of-sequence" to be "throw an exception" or "warp around", thereby reducing the complexity of the requirements specifications of the random number library. As outlined in N1452, section III.E, it is also easier to make a generator out of an iterator compared to the reverse, because a generator has less requirements.

After this discussion, I propose to move to a generator-based approach. (Note: The pre-TR random number library in Boost used this approach, but failed to fix the "overload" problem, so the iterator range approach was tried in the TR proposal - and failed due to reasonable design concerns.)

Proposed resolution

In section 5.1.1 [tr.rand.req], replace in the paragraph before table 5.2

... it1 is an lvalue and it2 is a (possibly const) value of an input iterator type It having an unsigned integral value type, ...

... g is an lvalue of a zero-argument function object returning values of unsigned integral type, ...

In the same section, replace in table 5.2 the table row for X(it1, it2) by

expression: X(g)
return type: (none)
pre/post-condition: creates an engine with the initial internal state given by the results of successive invocations of g. Throws what and when g throws.
complexity: O(size of state)

In the same section, replace in table 5.2 the table row for u.seed(it1, it2) by

expression: u.seed(g)
return type: void
pre/post-conditions: sets the internal state of u so that u == X(g). If an invocation of g throws, that exception is rethrown, and further use of u (except destruction) is undefined until a seed member function has been executed without throwing an exception.
complexity: same as X(g)

After table 5.2, add a new paragraph following the one starting "Additional Requirements":

For every pseudo-random number engine defined in this clause:
the constructor
template<class Gen> X(Gen& g)
shall have the same effect as
X(static_cast<Gen>(g))
if Gen is a fundamental type.
The member function of the form
template<class Gen> void seed(Gen& g)
shall have the same effect as
X(static_cast<Gen>(g))
if Gen is a fundamental type.
[Note: The casts make g an rvalue, unsuitable for binding to a reference.]

[Note to editor: The following changes intend to morph "dereferencing *first" to "invoking g" only. However, complete text has been given.]

In section 5.1.4.1 [tr.rand.eng.lcong], replace the constructor template<class In> linear_congruential(In& first, In last) by

template<class Gen> linear_congruental(Gen& g)
Effects: If c mod m = 0 and g() mod m = 0, sets the state x(i) of the engine to 1 mod m, else sets the state x(i) of the engine to g() mod m.

Complexity: Exactly one invocation of g.

Furthermore, adjust the class synopsis accordingly.

In section 5.1.4.2 [tr.rand.eng.mers], replace the description of the constructor template<class In> mersenne_twister(In& first, In last) by

template<class Gen> mersenne_twister(Gen& g)
Effects: Given the values z[0] ... z[n-1] obtained by successive invocations of g, sets x(-n) ... x(-1) to z[0] mod 2^w ... z[n-1] mod 2^w.
Complexity: Exactly n invocations of g.