29 Numerics library [numerics]

29.5 Random number generation [rand]

29.5.3 Requirements [rand.req]

29.5.3.1 General requirements [rand.req.genl]

Throughout [rand], the effect of instantiating a template:

(1.1)
that has a template type parameter named Sseq is undefined unless the corresponding template argument is cv-unqualified and meets the requirements of seed sequence .
(1.2)
that has a template type parameter named URBG is undefined unless the corresponding template argument is cv-unqualified and meets the requirements of uniform random bit generator .
(1.3)
that has a template type parameter named Engine is undefined unless the corresponding template argument is cv-unqualified and meets the requirements of random number engine .
(1.4)
that has a template type parameter named RealType is undefined unless the corresponding template argument is cv-unqualified and is one of float, double, or long double.
(1.5)
that has a template type parameter named IntType is undefined unless the corresponding template argument is cv-unqualified and is one of short, int, long, long long, unsigned short, unsigned int, unsigned long, or unsigned long long.
(1.6)
that has a template type parameter named UIntType is undefined unless the corresponding template argument is cv-unqualified and is one of unsigned short, unsigned int, unsigned long, or unsigned long long.

Throughout [rand], phrases of the form “x is an iterator of a specific kind” shall be interpreted as equivalent to the more formal requirement that “x is a value of a type meeting the requirements of the specified iterator type”.

Throughout [rand], any constructor that can be called with a single argument and that meets a requirement specified in this subclause shall be declared explicit.

29.5.3.2 Seed sequence requirements [rand.req.seedseq]

A seed sequence is an object that consumes a sequence of integer-valued data and produces a requested number of unsigned integer values i,

0 \leq i < 2^{32}

, based on the consumed data.

[Note 1:

Such an object provides a mechanism to avoid replication of streams of random variates.

This can be useful, for example, in applications requiring large numbers of random number engines.

— end note]

A class S meets the requirements of a seed sequence if the expressions shown in Table 124 are valid and have the indicated semantics, and if S also meets all other requirements of [rand.req.seedseq].

In Table 124 and throughout this subclause:

(2.1)
T is the type named by S's associated result_type;
(2.2)
q is a value of type S and r is a value of type S or const S;
(2.3)
ib and ie are input iterators with an unsigned integer value_type of at least 32 bits;
(2.4)
rb and re are mutable random access iterators with an unsigned integer value_type of at least 32 bits;
(2.5)
ob is an output iterator; and
(2.6)
il is a value of type initializer_list<T>.

Table 124 — Seed sequence requirements [tab:rand.req.seedseq]

🔗 Expression	Return type	Pre/post-condition	Complexity
🔗 S::result_type	T	T is an unsigned integer type of at least 32 bits.
🔗 S()		Creates a seed sequence with the same initial state as all other default-constructed seed sequences of type S.	constant
🔗 S(ib,ie)		Creates a seed sequence having internal state that depends on some or all of the bits of the supplied sequence [ib,ie).	$O (ie - ib)$
🔗 S(il)		Same as S(il.begin(), il.end()).	same as S(il.begin(), il.end())
🔗 q.generate(rb,re)	void	Does nothing if rb == re. Otherwise, fills the supplied sequence [rb,re) with 32-bit quantities that depend on the sequence supplied to the constructor and possibly also depend on the history of generate's previous invocations.	$O (re - rb)$
🔗 r.size()	size_t	The number of 32-bit units that would be copied by a call to r.param.	constant
🔗 r.param(ob)	void	Copies to the given destination a sequence of 32-bit units that can be provided to the constructor of a second object of type S, and that would reproduce in that second object a state indistinguishable from the state of the first object.	$O (r.size())$

29.5.3.3 Uniform random bit generator requirements [rand.req.urng]

A uniform random bit generator g of type G is a function object returning unsigned integer values such that each value in the range of possible results has (ideally) equal probability of being returned.

[Note 1:

The degree to which g's results approximate the ideal is often determined statistically.

— end note]

template<class G> concept uniform_random_bit_generator = invocable<G&> && unsigned_integral<invoke_result_t<G&>> && requires { { G::min() } -> same_as<invoke_result_t<G&>>; { G::max() } -> same_as<invoke_result_t<G&>>; requires bool_constant<(G::min() < G::max())>::value; };

Let g be an object of type G.

G models uniform_random_bit_generator only if

(2.1)
G::min() <= g(),
(2.2)
g() <= G::max(), and
(2.3)
g() has amortized constant complexity.

A class G meets the uniform random bit generator requirements if G models uniform_random_bit_generator, invoke_result_t<G&> is an unsigned integer type ([basic.fundamental]), and G provides a nested typedef-name result_type that denotes the same type as invoke_result_t<G&>.

29.5.3.4 Random number engine requirements [rand.req.eng]

A random number engine (commonly shortened to engine) e of type E is a uniform random bit generator that additionally meets the requirements (e.g., for seeding and for input/output) specified in this subclause.

At any given time, e has a state e

_{i}

for some integer i ≥ 0.

Upon construction, e has an initial state e

_{0}

An engine's state may be established via a constructor, a seed function, assignment, or a suitable operator>>.

E's specification shall define:

(3.1)
the size of E's state in multiples of the size of result_type, given as an integral constant expression;
(3.2)
the transition algorithm TA by which e's state e $_{i}$ is advanced to its successor state e $_{i + 1}$ ; and
(3.3)
the generation algorithm GA by which an engine's state is mapped to a value of type result_type.

A class E that meets the requirements of a uniform random bit generator also meets the requirements of a random number engine if the expressions shown in Table 125 are valid and have the indicated semantics, and if E also meets all other requirements of [rand.req.eng].

In Table 125 and throughout this subclause:

(4.1)
T is the type named by E's associated result_type;
(4.2)
e is a value of E, v is an lvalue of E, x and y are (possibly const) values of E;
(4.3)
s is a value of T;
(4.4)
q is an lvalue meeting the requirements of a seed sequence;
(4.5)
z is a value of type unsigned long long;
(4.6)
os is an lvalue of the type of some class template specialization basic_ostream<charT, traits>; and
(4.7)
is is an lvalue of the type of some class template specialization basic_istream<charT, traits>;

where charT and traits are constrained according to [strings] and [input.output].

Table 125 — Random number engine requirements [tab:rand.req.eng]

🔗 Expression	Return type	Pre/post-condition	Complexity
🔗 E()		Creates an engine with the same initial state as all other default-constructed engines of type E.	$O (size of state)$
🔗 E(x)		Creates an engine that compares equal to x.	$O (size of state)$
🔗 E(s)		Creates an engine with initial state determined by s.	$O (size of state)$
🔗 E(q)241		Creates an engine with an initial state that depends on a sequence produced by one call to q.generate.	same as complexity of q.generate called on a sequence whose length is size of state
🔗 e.seed()	void	Postconditions: e == E().	same as E()
🔗 e.seed(s)	void	Postconditions: e == E(s).	same as E(s)
🔗 e.seed(q)	void	Postconditions: e == E(q).	same as E(q)
🔗 e()	T	Advances e's state e $_{i}$ to e $_{i + 1}$ $= T A ($ e $_{i}$ ) and returns GA(e $_{i}$ ).	per [rand.req.urng]
🔗 e.discard(z)242	void	Advances e's state e $_{i}$ to $e_{i + z}$ by any means equivalent to z consecutive calls e().	no worse than the complexity of z consecutive calls e()
🔗 x == y	bool	This operator is an equivalence relation. With $S_{x}$ and $S_{y}$ as the infinite sequences of values that would be generated by repeated future calls to x() and y(), respectively, returns true if $S_{x} = S_{y}$ ; else returns false.	$O (size of state)$
🔗 x != y	bool	!(x == y).	$O ($ size of state $)$

E shall meet the Cpp17CopyConstructible (Table 32) and Cpp17CopyAssignable (Table 34) requirements.

These operations shall each be of complexity no worse than

O (size of state)

On hosted implementations, the following expressions are well-formed and have the specified semantics.

🔗

os << x

Effects: With os.fmtflags set to ios_base::dec|ios_base::left and the fill character set to the space character, writes to os the textual representation of x's current state.

In the output, adjacent numbers are separated by one or more space characters.

Postconditions: The os.fmtflags and fill character are unchanged.

Result: reference to the type of os.

Returns: os.

Complexity:

O ($ size of state $)

🔗

is >> v

Preconditions: is provides a textual representation that was previously written using an output stream whose imbued locale was the same as that of is, and whose type's template specialization arguments charT and traits were respectively the same as those of is.

Effects: With is.fmtflags set to ios_base::dec, sets v's state as determined by reading its textual representation from is.

If bad input is encountered, ensures that v's state is unchanged by the operation and calls is.setstate(ios_base::failbit) (which may throw ios_base::failure ([iostate.flags])).

If a textual representation written via os << x was subsequently read via is >> v, then x == v provided that there have been no intervening invocations of x or of v.

Postconditions: The is.fmtflags are unchanged.

Result: reference to the type of is.

Returns: is.

Complexity:

O ($ size of state $)

241)241)

This constructor (as well as the subsequent corresponding seed() function) can be particularly useful to applications requiring a large number of independent random sequences.

242)242)

This operation is common in user code, and can often be implemented in an engine-specific manner so as to provide significant performance improvements over an equivalent naive loop that makes z consecutive calls e().

29.5.3.5 Random number engine adaptor requirements [rand.req.adapt]

A random number engine adaptor (commonly shortened to adaptor) a of type A is a random number engine that takes values produced by some other random number engine, and applies an algorithm to those values in order to deliver a sequence of values with different randomness properties.

An engine b of type B adapted in this way is termed a base engine in this context.

The expression a.base() shall be valid and shall return a const reference to a's base engine.

The requirements of a random number engine type shall be interpreted as follows with respect to a random number engine adaptor type.

🔗

A::A();

Effects: The base engine is initialized as if by its default constructor.

🔗

bool operator==(const A& a1, const A& a2);

Returns: true if a1's base engine is equal to a2's base engine.

Otherwise returns false.

🔗

A::A(result_type s);

Effects: The base engine is initialized with s.

🔗

template<class Sseq> A::A(Sseq& q);

Effects: The base engine is initialized with q.

🔗

void seed();

Effects: With b as the base engine, invokes b.seed().

🔗

void seed(result_type s);

Effects: With b as the base engine, invokes b.seed(s).

🔗

template<class Sseq> void seed(Sseq& q);

Effects: With b as the base engine, invokes b.seed(q).

A shall also meet the following additional requirements:

(10.1)
The complexity of each function shall not exceed the complexity of the corresponding function applied to the base engine.
(10.2)
The state of A shall include the state of its base engine.

The size of A's state shall be no less than the size of the base engine.
(10.3)
Copying A's state (e.g., during copy construction or copy assignment) shall include copying the state of the base engine of A.
(10.4)
The textual representation of A shall include the textual representation of its base engine.

29.5.3.6 Random number distribution requirements [rand.req.dist]

A random number distribution (commonly shortened to distribution) d of type D is a function object returning values that are distributed according to an associated mathematical probability density function p(z) or according to an associated discrete probability function

P (z_{i})

A distribution's specification identifies its associated probability function p(z) or

P (z_{i})

An associated probability function is typically expressed using certain externally-supplied quantities known as the parameters of the distribution.

Such distribution parameters are identified in this context by writing, for example, p(z | a,b) or

P (z_{i} | a, b)

, to name specific parameters, or by writing, for example, p(z |{p}) or

P (z_{i} | {p})

, to denote a distribution's parameters p taken as a whole.

A class D meets the requirements of a random number distribution if the expressions shown in Table 126 are valid and have the indicated semantics, and if D and its associated types also meet all other requirements of [rand.req.dist].

In Table 126 and throughout this subclause,

(3.1)
T is the type named by D's associated result_type;
(3.2)
P is the type named by D's associated param_type;
(3.3)
d is a value of D, and x and y are (possibly const) values of D;
(3.4)
glb and lub are values of T respectively corresponding to the greatest lower bound and the least upper bound on the values potentially returned by d's operator(), as determined by the current values of d's parameters;
(3.5)
p is a (possibly const) value of P;
(3.6)
g, g1, and g2 are lvalues of a type meeting the requirements of a uniform random bit generator;
(3.7)
os is an lvalue of the type of some class template specialization basic_ostream<charT, traits>; and
(3.8)
is is an lvalue of the type of some class template specialization basic_istream<charT, traits>;

where charT and traits are constrained according to [strings] and [input.output].

Table 126 — Random number distribution requirements [tab:rand.req.dist]

🔗 Expression	Return type	Pre/post-condition	Complexity
🔗 D::result_type	T	T is an arithmetic type .
🔗 D::param_type	P
🔗 D()		Creates a distribution whose behavior is indistinguishable from that of any other newly default-constructed distribution of type D.	constant
🔗 D(p)		Creates a distribution whose behavior is indistinguishable from that of a distribution newly constructed directly from the values used to construct p.	same as p's construction
🔗 d.reset()	void	Subsequent uses of d do not depend on values produced by any engine prior to invoking reset.	constant
🔗 x.param()	P	Returns a value p such that D(p).param() == p.	no worse than the complexity of D(p)
🔗 d.param(p)	void	Postconditions: d.param() == p.	no worse than the complexity of D(p)
🔗 d(g)	T	With $p = d.param()$ , the sequence of numbers returned by successive invocations with the same object g is randomly distributed according to the associated p(z \|{p}) or $P (z_{i} \| {p})$ function.	amortized constant number of invocations of g
🔗 d(g,p)	T	The sequence of numbers returned by successive invocations with the same objects g and p is randomly distributed according to the associated p(z \|{p}) or $P (z_{i} \| {p})$ function.	amortized constant number of invocations of g
🔗 x.min()	T	Returns glb.	constant
🔗 x.max()	T	Returns lub.	constant
🔗 x == y	bool	This operator is an equivalence relation. Returns true if x.param() == y.param() and $S_{1} = S_{2}$ , where $S_{1}$ and $S_{2}$ are the infinite sequences of values that would be generated, respectively, by repeated future calls to x(g1) and y(g2) whenever g1 == g2. Otherwise returns false.	constant
🔗 x != y	bool	!(x == y).	same as x == y.

D shall meet the Cpp17CopyConstructible (Table 32) and Cpp17CopyAssignable (Table 34) requirements.

The sequence of numbers produced by repeated invocations of d(g) shall be independent of any invocation of os << d or of any const member function of D between any of the invocations of d(g).

If a textual representation is written using os << x and that representation is restored into the same or a different object y of the same type using is >> y, repeated invocations of y(g) shall produce the same sequence of numbers as would repeated invocations of x(g).

It is unspecified whether D::param_type is declared as a (nested) class or via a typedef.

In [rand], declarations of D::param_type are in the form of typedefs for convenience of exposition only.

P shall meet the Cpp17CopyConstructible (Table 32), Cpp17CopyAssignable (Table 34), and Cpp17EqualityComparable (Table 28) requirements.

For each of the constructors of D taking arguments corresponding to parameters of the distribution, P shall have a corresponding constructor subject to the same requirements and taking arguments identical in number, type, and default values.

Moreover, for each of the member functions of D that return values corresponding to parameters of the distribution, P shall have a corresponding member function with the identical name, type, and semantics.

P shall have a declaration of the form using distribution_type = D;

On hosted implementations, the following expressions are well-formed and have the specified semantics.

🔗

os << x

Effects: Writes to os a textual representation for the parameters and the additional internal data of x.

Postconditions: The os.fmtflags and fill character are unchanged.

Result: reference to the type of os.

Returns: os.

🔗

is >> d

Preconditions: is provides a textual representation that was previously written using an os whose imbued locale and whose type's template specialization arguments charT and traits were the same as those of is.

Effects: Restores from is the parameters and additional internal data of the lvalue d.

If bad input is encountered, ensures that d is unchanged by the operation and calls is.setstate(ios_base::failbit) (which may throw ios_base::failure ([iostate.flags])).

Postconditions: The is.fmtflags are unchanged.

Result: reference to the type of is.

Returns: is.