26 Numerics library [numerics]

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

1. (1.1)

   that has a template type parameter named Sseq is undefined unless the corresponding template argument is cv-unqualified and satisfies the requirements of seed sequence ([rand.req.seedseq]).

2. (1.2)

   that has a template type parameter named URBG is undefined unless the corresponding template argument is cv-unqualified and satisfies the requirements of uniform random bit generator ([rand.req.urng]).

3. (1.3)

   that has a template type parameter named Engine is undefined unless the corresponding template argument is cv-unqualified and satisfies the requirements of random number engine ([rand.req.eng]).

4. (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.

5. (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.

6. (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 this subclause [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 satisfying the requirements of the specified iterator type.”

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

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 ≤ i < 2³² , based on the consumed data. [ Note: 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 satisfies the requirements of a seed sequence if the expressions shown in Table [tab:SeedSequence] are valid and have the indicated semantics, and if S also satisfies all other requirements of this section [rand.req.seedseq]. In that Table and throughout this section:

1. (2.1)

   T is the type named by S's associated result_type;

2. (2.2)

   q is a value of S and r is a possibly const value of S;

3. (2.3)

   ib and ie are input iterators with an unsigned integer value_type of at least 32 bits;

4. (2.4)

   rb and re are mutable random access iterators with an unsigned integer value_type of at least 32 bits;

5. (2.5)

   ob is an output iterator; and

6. (2.6)

   il is a value of initializer_list<T>.

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: The degree to which g's results approximate the ideal is often determined statistically.  — end note ]

A class G satisfies the requirements of a uniform random bit generator if the expressions shown in Table [tab:UniformRandomBitGenerator] are valid and have the indicated semantics, and if G also satisfies all other requirements of this section [rand.req.urng]. In that Table and throughout this section:

1. (2.1)

   T is the type named by G's associated result_type, and

2. (2.2)

   g is a value of G.

The following relation shall hold: G::min() < G::max().

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 section.

At any given time, e has a state e_i for some integer i ≥ 0. Upon construction, e has an initial state e₀. An engine's state may be established via a constructor, a seed function, assignment, or a suitable operator>>.

E's specification shall define:

1. (3.1)

   the size of E's state in multiples of the size of result_type, given as an integral constant expression;

2. (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.3)

   the generation algorithm GA by which an engine's state is mapped to a value of type result_type.

A class E that satisfies the requirements of a uniform random bit generator ([rand.req.urng]) also satisfies the requirements of a random number engine if the expressions shown in Table [tab:RandomEngine] are valid and have the indicated semantics, and if E also satisfies all other requirements of this section [rand.req.eng]. In that Table and throughout this section:

1. (4.1)

   T is the type named by E's associated result_type;

2. (4.2)

   e is a value of E, v is an lvalue of E, x and y are (possibly const) values of E;

3. (4.3)

   s is a value of T;

4. (4.4)

   q is an lvalue satisfying the requirements of a seed sequence ([rand.req.seedseq]);

5. (4.5)

   z is a value of type unsigned long long;

6. (4.6)

   os is an lvalue of the type of some class template specialization basic_ostream<charT, traits>; and

7. (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 Clause [strings] and Clause [input.output].

E shall meet the requirements of CopyConstructible (Table [tab:copyconstructible]) and CopyAssignable (Table [tab:copyassignable]) types. These operations shall each be of complexity no worse than Ο(size of state).

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

A shall also satisfy the following additional requirements:

1. (10.1)

   The complexity of each function shall not exceed the complexity of the corresponding function applied to the base engine.

2. (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.

3. (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.

4. (10.4)

   The textual representation of A shall include the textual representation of its base engine.

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 satisfies the requirements of a random number distribution if the expressions shown in Table [tab:RandomDistribution] are valid and have the indicated semantics, and if D and its associated types also satisfy all other requirements of this section [rand.req.dist]. In that Table and throughout this section,

1. (3.1)

   T is the type named by D's associated result_type;

2. (3.2)

   P is the type named by D's associated param_type;

3. (3.3)

   d is a value of D, and x and y are (possibly const) values of D;

4. (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;

5. (3.5)

   p is a (possibly const) value of P;

6. (3.6)

   g, g1, and g2 are lvalues of a type satisfying the requirements of a uniform random bit generator ([rand.req.urng]);

7. (3.7)

   os is an lvalue of the type of some class template specialization basic_ostream<charT, traits>; and

8. (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 Clauses [strings] and [input.output].

D shall satisfy the requirements of CopyConstructible (Table [tab:copyconstructible]) and CopyAssignable (Table [tab:copyassignable]) types.

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 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 this subclause [rand], declarations of D::param_type are in the form of typedefs for convenience of exposition only.

P shall satisfy the requirements of CopyConstructible (Table [tab:copyconstructible]), CopyAssignable (Table [tab:copyassignable]), and EqualityComparable (Table [tab:equalitycomparable]) types.

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;

A linear_congruential_engine random number engine produces unsigned integer random numbers. The state x_i of a linear_congruential_engine object x is of size 1 and consists of a single integer. The transition algorithm is a modular linear function of the form TA(x_i) = (a · x_i + c) mod m; the generation algorithm is GA(x_i) = x_i+1 .

template<class UIntType, UIntType a, UIntType c, UIntType m>
 class linear_congruential_engine{
public:
 // types
 using result_type = UIntType;

 // engine characteristics
 static constexpr result_type multiplier = a;
 static constexpr result_type increment = c;
 static constexpr result_type modulus = m;
 static constexpr result_type min() { return c == 0u ? 1u: 0u; }
 static constexpr result_type max() { return m - 1u; }
 static constexpr result_type default_seed = 1u;

 // constructors and seeding functions
 explicit linear_congruential_engine(result_type s = default_seed);
 template<class Sseq> explicit linear_congruential_engine(Sseq& q);
 void seed(result_type s = default_seed);
 template<class Sseq> void seed(Sseq& q);

 // generating functions
 result_type operator()();
 void discard(unsigned long long z);
};

If the template parameter m is 0, the modulus m used throughout this section [rand.eng.lcong] is numeric_limits<result_type>::max() plus 1. [ Note: m need not be representable as a value of type result_type.  — end note ]

If the template parameter m is not 0, the following relations shall hold: a < m and c < m.

The textual representation consists of the value of x_i.

explicit linear_congruential_engine(result_type s = default_seed);

A mersenne_twister_engine random number engine271 produces unsigned integer random numbers in the closed interval [0,2^w-1]. The state x_i of a mersenne_twister_engine object x is of size n and consists of a sequence X of n values of the type delivered by x; all subscripts applied to X are to be taken modulo n.

The transition algorithm employs a twisted generalized feedback shift register defined by shift values n and m, a twist value r, and a conditional xor-mask a. To improve the uniformity of the result, the bits of the raw shift register are additionally tempered (i.e., scrambled) according to a bit-scrambling matrix defined by values u, d, s, b, t, c, and ℓ.

The state transition is performed as follows:

1. (2.1)

   Concatenate the upper w-r bits of X_i-n with the lower r bits of X_i+1-n to obtain an unsigned integer value Y.

2. (2.2)

   With α = a · (Y   bitand   1), set X_i to X_i+m-n     xor     (Y   rshift   1)     xor     α.

The sequence X is initialized with the help of an initialization multiplier f.

The generation algorithm determines the unsigned integer values z₁, z₂, z₃, z₄ as follows, then delivers z₄ as its result:

1. (3.1)

   Let z₁ = X_i   xor   (( X_i   rshift   u )   bitand   d).

2. (3.2)

   Let z₂ = z₁   xor   ( (z₁   lshift_w     s)   bitand   b ).

3. (3.3)

   Let z₃ = z₂   xor   ( (z₂   lshift_w     t)   bitand   c ).

4. (3.4)

   Let z₄ = z₃   xor   ( z₃   rshift   ℓ ).

template<class UIntType, size_t w, size_t n, size_t m, size_t r,
          UIntType a, size_t u, UIntType d, size_t s,
          UIntType b, size_t t,
          UIntType c, size_t l, UIntType f>
 class mersenne_twister_engine{
public:
 // types
 using result_type = UIntType;

 // engine characteristics
 static constexpr size_t word_size = w;
 static constexpr size_t state_size = n;
 static constexpr size_t shift_size = m;
 static constexpr size_t mask_bits = r;
 static constexpr UIntType xor_mask = a;
 static constexpr size_t tempering_u = u;
 static constexpr UIntType tempering_d = d;
 static constexpr size_t tempering_s = s;
 static constexpr UIntType tempering_b = b;
 static constexpr size_t tempering_t = t;
 static constexpr UIntType tempering_c = c;
 static constexpr size_t tempering_l = l;
 static constexpr UIntType initialization_multiplier = f;
 static constexpr result_type min() { return 0; }
 static constexpr result_type max() { return  2w - 1; }
 static constexpr result_type default_seed = 5489u;

 // constructors and seeding functions
 explicit mersenne_twister_engine(result_type value = default_seed);
 template<class Sseq> explicit mersenne_twister_engine(Sseq& q);
 void seed(result_type value = default_seed);
 template<class Sseq> void seed(Sseq& q);

 // generating functions
 result_type operator()();
 void discard(unsigned long long z);
};

The following relations shall hold: 0 < m, m <= n, 2u < w, r <= w, u <= w, s <= w, t <= w, l <= w, w <= numeric_limits<UIntType>::digits, a <= (1u<<w) - 1u, b <= (1u<<w) - 1u, c <= (1u<<w) - 1u, d <= (1u<<w) - 1u, and f <= (1u<<w) - 1u.

The textual representation of x_i consists of the values of X_i-n, …, X_i-1, in that order.

explicit mersenne_twister_engine(result_type value = default_seed);

A subtract_with_carry_engine random number engine produces unsigned integer random numbers.

The state x_i of a subtract_with_carry_engine object x is of size Ο(r), and consists of a sequence X of r integer values 0 ≤ X_i < m  = 2^w; all subscripts applied to X are to be taken modulo r. The state x_i additionally consists of an integer c (known as the carry) whose value is either 0 or 1.

The state transition is performed as follows:

1. (3.1)

   Let Y = X_i-s - X_i-r - c .

2. (3.2)

   Set X_i to y = Y mod m . Set c to 1 if Y < 0, otherwise set c to 0.

[ Note: This algorithm corresponds to a modular linear function of the form TA(x_i) = (a · x_i) mod b , where b is of the form m^r - m^s + 1 and a = b - (b-1) / m .  — end note ]

The generation algorithm is given by GA(x_i) = y , where y is the value produced as a result of advancing the engine's state as described above.

template<class UIntType, size_t w, size_t s, size_t r>
 class subtract_with_carry_engine{
public:
 // types
 using result_type = UIntType;

 // engine characteristics
 static constexpr size_t word_size = w;
 static constexpr size_t short_lag = s;
 static constexpr size_t long_lag = r;
 static constexpr result_type min() { return 0; }
 static constexpr result_type max() { return m - 1; }
 static constexpr result_type default_seed = 19780503u;

 // constructors and seeding functions
 explicit subtract_with_carry_engine(result_type value = default_seed);
 template<class Sseq> explicit subtract_with_carry_engine(Sseq& q);
 void seed(result_type value = default_seed);
 template<class Sseq> void seed(Sseq& q);

 // generating functions
 result_type operator()();
 void discard(unsigned long long z);
};

The following relations shall hold: 0u < s, s < r, 0 < w, and w <= numeric_limits<UIntType>::digits.

The textual representation consists of the values of X_i-r, …, X_i-1, in that order, followed by c.

explicit subtract_with_carry_engine(result_type value = default_seed);

Each type instantiated from a class template specified in this section [rand.adapt] satisfies the requirements of a random number engine adaptor ([rand.req.adapt]) type.

Except where specified otherwise, the complexity of each function specified in this section [rand.adapt] is constant.

Except where specified otherwise, no function described in this section [rand.adapt] throws an exception.

Every function described in this section [rand.adapt] that has a function parameter q of type Sseq& for a template type parameter named Sseq that is different from type seed_seq throws what and when the invocation of q.generate throws.

Descriptions are provided in this section [rand.adapt] only for adaptor operations that are not described in section [rand.req.adapt] or for operations where there is additional semantic information. In particular, declarations for copy constructors, for copy assignment operators, for streaming operators, and for equality and inequality operators are not shown in the synopses.

Each template specified in this section [rand.adapt] requires one or more relationships, involving the value(s) of its non-type template parameter(s), to hold. A program instantiating any of these templates is ill-formed if any such required relationship fails to hold.

A discard_block_engine random number engine adaptor produces random numbers selected from those produced by some base engine e. The state x_i of a discard_block_engine engine adaptor object x consists of the state e_i of its base engine e and an additional integer n. The size of the state is the size of e's state plus 1.

The transition algorithm discards all but r > 0 values from each block of p ≥ r values delivered by e. The state transition is performed as follows: If n ≥ r, advance the state of e from e_i to e_i+p-r and set n to 0. In any case, then increment n and advance e's then-current state e_j to e_j+1.

The generation algorithm yields the value returned by the last invocation of e() while advancing e's state as described above.

template<class Engine, size_t p, size_t r>
 class discard_block_engine{
public:
 // types
 using result_type = typename Engine::result_type;

 // engine characteristics
 static constexpr size_t block_size = p;
 static constexpr size_t used_block = r;
 static constexpr result_type min() { return Engine::min(); }
 static constexpr result_type max() { return Engine::max(); }

 // constructors and seeding functions
 discard_block_engine();
 explicit discard_block_engine(const Engine& e);
 explicit discard_block_engine(Engine&& e);
 explicit discard_block_engine(result_type s);
 template<class Sseq> explicit discard_block_engine(Sseq& q);
 void seed();
 void seed(result_type s);
 template<class Sseq> void seed(Sseq& q);

 // generating functions
 result_type operator()();
 void discard(unsigned long long z);

 // property functions
 const Engine& base() const noexcept { return e; };

private:
 Engine e;   // exposition only
 int n;      // exposition only
};

The following relations shall hold: 0 < r and r <= p.

The textual representation consists of the textual representation of e followed by the value of n.

In addition to its behavior pursuant to section [rand.req.adapt], each constructor that is not a copy constructor sets n to 0.

An independent_bits_engine random number engine adaptor combines random numbers that are produced by some base engine e, so as to produce random numbers with a specified number of bits w. The state x_i of an independent_bits_engine engine adaptor object x consists of the state e_i of its base engine e; the size of the state is the size of e's state.

The transition and generation algorithms are described in terms of the following integral constants:

1. (2.1)

   Let R = e.max() - e.min() + 1 and m = ⌊ log₂ R ⌋ .

2. (2.2)

   With n as determined below, let w₀ = ⌊ w / n ⌋ , n₀ = n - w mod n , y₀ = 2^w₀ ⌊ R / 2^w₀ ⌋ , and y₁ = 2^{w₀ + 1} ⌊ R / 2^{w₀ + 1} ⌋ .

3. (2.3)

   Let n = ⌈ w / m ⌉ if and only if the relation R - y₀ ≤ ⌊ y₀ / n ⌋ holds as a result. Otherwise let n = 1 + ⌈ w / m ⌉ .

[ Note: The relation w = n₀ w₀ + (n - n₀)(w₀ + 1) always holds.  — end note ]

The transition algorithm is carried out by invoking e() as often as needed to obtain n₀ values less than y₀ + e.min() and n - n₀ values less than y₁ + e.min() .

The generation algorithm uses the values produced while advancing the state as described above to yield a quantity S obtained as if by the following algorithm:

S = 0;
for (k = 0; k ≠ n0; k += 1)  {
 do u = e() - e.min(); while ( u ≥ y0 );
 S =  2w0 · S + u mod 2w0 ;
}
for (k = n0; k ≠ n; k += 1)  {
 do u = e() - e.min(); while ( u ≥ y1 );
 S =  2w0 + 1 · S + u mod 2w0 + 1 ;
}

template<class Engine, size_t w, class UIntType>
class independent_bits_engine{
public:
 // types
 using result_type = UIntType;

 // engine characteristics
 static constexpr result_type min() { return 0; }
 static constexpr result_type max() { return 2w - 1; }

 // constructors and seeding functions
 independent_bits_engine();
 explicit independent_bits_engine(const Engine& e);
 explicit independent_bits_engine(Engine&& e);
 explicit independent_bits_engine(result_type s);
 template<class Sseq> explicit independent_bits_engine(Sseq& q);
 void seed();
 void seed(result_type s);
 template<class Sseq> void seed(Sseq& q);

 // generating functions
 result_type operator()();
 void discard(unsigned long long z);

 // property functions
 const Engine& base() const noexcept { return e; };

private:
 Engine e;   // exposition only
};

The following relations shall hold: 0 < w and w <= numeric_limits<result_type>::digits.

The textual representation consists of the textual representation of e.

A shuffle_order_engine random number engine adaptor produces the same random numbers that are produced by some base engine e, but delivers them in a different sequence. The state x_i of a shuffle_order_engine engine adaptor object x consists of the state e_i of its base engine e, an additional value Y of the type delivered by e, and an additional sequence V of k values also of the type delivered by e. The size of the state is the size of e's state plus k+1.

The transition algorithm permutes the values produced by e. The state transition is performed as follows:

1. (2.1)

   Calculate an integer .

2. (2.2)

   Set Y to V_j and then set V_j to e().

The generation algorithm yields the last value of Y produced while advancing e's state as described above.

template<class Engine, size_t k>
 class shuffle_order_engine{
public:
 // types
 using result_type = typename Engine::result_type;

 // engine characteristics
 static constexpr size_t table_size = k;
 static constexpr result_type min() { return Engine::min(); }
 static constexpr result_type max() { return Engine::max(); }

 // constructors and seeding functions
 shuffle_order_engine();
 explicit shuffle_order_engine(const Engine& e);
 explicit shuffle_order_engine(Engine&& e);
 explicit shuffle_order_engine(result_type s);
 template<class Sseq> explicit shuffle_order_engine(Sseq& q);
 void seed();
 void seed(result_type s);
 template<class Sseq> void seed(Sseq& q);

 // generating functions
 result_type operator()();
 void discard(unsigned long long z);

 // property functions
 const Engine& base() const noexcept { return e; };

private:
 Engine e;           // exposition only
 result_type Y;      // exposition only
 result_type V[k];   // exposition only
};

The following relation shall hold: 0 < k.

The textual representation consists of the textual representation of e, followed by the k values of V, followed by the value of Y.

In addition to its behavior pursuant to section [rand.req.adapt], each constructor that is not a copy constructor initializes V[0], …, V[k-1] and Y, in that order, with values returned by successive invocations of e().

Each function instantiated from the template described in this section [rand.util.canonical] maps the result of one or more invocations of a supplied uniform random bit generator g to one member of the specified RealType such that, if the values g_i produced by g are uniformly distributed, the instantiation's results t_j, 0 ≤ t_j < 1 , are distributed as uniformly as possible as specified below.

[ Note: Obtaining a value in this way can be a useful step in the process of transforming a value generated by a uniform random bit generator into a value that can be delivered by a random number distribution.  — end note ]

template<class RealType, size_t bits, class URBG> RealType generate_canonical(URBG& g);

Each type instantiated from a class template specified in this section [rand.dist] satisfies the requirements of a random number distribution ([rand.req.dist]) type.

Descriptions are provided in this section [rand.dist] only for distribution operations that are not described in [rand.req.dist] or for operations where there is additional semantic information. In particular, declarations for copy constructors, for copy assignment operators, for streaming operators, and for equality and inequality operators are not shown in the synopses.

The algorithms for producing each of the specified distributions are implementation-defined.

The value of each probability density function p(z) and of each discrete probability function P(z_i) specified in this section is 0 everywhere outside its stated domain.

The class template valarray<T> is a one-dimensional smart array, with elements numbered sequentially from zero. It is a representation of the mathematical concept of an ordered set of values. The illusion of higher dimensionality may be produced by the familiar idiom of computed indices, together with the powerful subsetting capabilities provided by the generalized subscript operators.277

An implementation is permitted to qualify any of the functions declared in <valarray> as inline.