29 Numerics library [numerics]

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

1. a)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.

2. b)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.

3. c)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.

4. d)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. e)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. f)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\le i<2^{32}$, 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 102 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. a)T is the type named by S's associated result_­type;

2. b)q is a value of S and r is a possibly const value of S;

3. c)ib and ie are input iterators with an unsigned integer value_­type of at least 32 bits;

4. d)rb and re are mutable random access iterators with an unsigned integer value_­type of at least 32 bits;

5. e)ob is an output iterator; and

6. f)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 103 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. a)T is the type named by G's associated result_­type, and

2. b)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\ge 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:

1. a)the size of E's state in multiples of the size of result_­type, given as an integral constant expression;

2. b)the transition algorithm TA by which e's state e${}_i$ is advanced to its successor state e${}_{i+1}$; and

3. c)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 also satisfies the requirements of a random number engine if the expressions shown in Table 104 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. a)T is the type named by E's associated result_­type;

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

3. c)s is a value of T;

4. d)q is an lvalue satisfying the requirements of a seed sequence;

5. e)z is a value of type unsigned long long;

6. f)os is an lvalue of the type of some class template specialization basic_­ostream<charT, traits>; and

7. g)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 and CopyAssignable types. These operations shall each be of complexity no worse than $O\left(\text{size of state}\right)$.

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 shall also satisfy the following additional requirements:

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

2. b)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. c)Copying A's state (e.g., during copy construction or copy assignment) shall include copying the state of the base engine of A.

4. d)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\left(z_i\right)$. A distribution's specification identifies its associated probability function p(z) or $P\left(z_i\right)$.

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\left(z_i|\left\{\text{p}\right\}\right)$, 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 105 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. a)T is the type named by D's associated result_­type;

2. b)P is the type named by D's associated param_­type;

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

4. d)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. e)p is a (possibly const) value of P;

6. f)g, g1, and g2 are lvalues of a type satisfying the requirements of a uniform random bit generator;

7. g)os is an lvalue of the type of some class template specialization basic_­ostream<charT, traits>; and

8. h)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 and 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, CopyAssignable, and 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\left({\text{x}}_i\right)=(a\cdot {\text{x}}_i+c)modm$; the generation algorithm is $GA\left({\text{x}}_i\right)={\text{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$.

A mersenne_­twister_­engine random number engine270 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. a)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. b)With $\alpha =a\cdot \left(Ybitand1\right)$, set $X_i$ to $X_{i+m-n}xor\left(Yrshift1\right)xor\alpha$.

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

The generation algorithm determines the unsigned integer values $z_1,z_2,z_3,z_4$ as follows, then delivers $z_4$ as its result:

1. a)Let $z_1=X_{i}xor(\left(X_{i}rshiftu\right)bitandd)$.

2. b)Let $z_2=z_{1}xor(\left(z_1{lshift}_{w}s\right)bitandb)$.

3. c)Let $z_3=z_{2}xor(\left(z_2{lshift}_{w}t\right)bitandc)$.

4. d)Let $z_4=z_{3}xor\left(z_{3}rshift\ell \right)$.

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  $2^w-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},\dots ,X_{i-1}$, in that order.

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 $O\left(r\right)$, and consists of a sequence X of r integer values $0\le 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. a)Let $Y=X_{i-s}-X_{i-r}-c$.

2. b)Set $X_i$ to $y=Ymodm$. 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\left({\text{x}}_i\right)=(a\cdot {\text{x}}_i)modb$, 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\left({\text{x}}_i\right)=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},\dots ,X_{i-1}$, in that order, followed by c.

Each type instantiated from a class template specified in this section [rand.adapt] satisfies the requirements of a random number engine adaptor 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\ge r$ values delivered by e. The state transition is performed as follows: If $n\ge 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. a)Let $R=\text{e.max() - e.min() + 1}$ and $m=\lfloor {\log }_{2}R\rfloor$.

2. b)With n as determined below, let $w_0=\lfloor w/n\rfloor$, $n_0=n-wmodn$, $y_0=2^{w_0}\lfloor R/2^{w_0}\rfloor$, and $y_1=2^{w_0+1}\lfloor R/2^{w_0+1}\rfloor$.

3. c)Let $n=\lceil w/m\rceil$ if and only if the relation $R-y_0\le \lfloor y_0/n\rfloor$ holds as a result. Otherwise let $n=1+\lceil w/m\rceil$.

[ Note: The relation $w=n_0{w}_0+(n-n_0)(w_0+1)$ always holds.  — end note ]

The transition algorithm is carried out by invoking e() as often as needed to obtain $n_0$ values less than $y_0+\text{e.min()}$ and $n-n_0$ values less than $y_1+\text{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\ne n_0$; k += 1)  {
 do u = e() - e.min(); while ($u\ge y_0$);
 S = $2^{w_0}\cdot S+umod{2}^{w_0}$;
}
for (k = $n_0$; $k\ne n$; k += 1)  {
 do u = e() - e.min(); while ($u\ge y_1$);
 S = $2^{w_0+1}\cdot S+umod{2}^{w_0+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 $2^w-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. a)Calculate an integer $j=\lfloor \frac{k\cdot (Y-e_{min})}{e_{max}-e_{min}+1}\rfloor$ .

2. b)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 V[k];   // exposition only
    result_type Y;      // 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 $\text{V[0]},\dots ,\text{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\le 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 ]

Each type instantiated from a class template specified in this section [rand.dist] satisfies the requirements of a random number distribution 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\left(z_i\right)$ specified in this section is 0 everywhere outside its stated domain.