29 Numerics library [numerics]

29.6 Random number generation [rand]

29.6.3 Random number engine class templates [rand.eng]

Каждый тип, созданный из шаблона класса, указанного в этом разделе, [rand.eng] удовлетворяет требованиям random number engine типа.

Если не указано иное, сложность каждой функции, указанной в этом разделе, [rand.eng] является постоянной.

Если не указано иное, ни одна функция, описанная в этом разделе, не [rand.eng] вызывает исключение.

Каждая функция, описанная в этом разделе, [rand.eng] которая имеет параметр функции q типа Sseq& для параметра типа шаблона с именем Sseq , отличным от типа, seed_seq вызывает то, что и когда q.generate вызывает вызов throw.

Описания представлены в этом разделе [rand.eng] только для операций двигателя, которые не описаны, [rand.req.eng] или для операций, для которых имеется дополнительная семантическая информация. В частности, объявления для конструкторов копирования, для операторов присваивания копий, для операторов потоковой передачи и для операторов равенства и неравенства не показаны в резюме.

Каждый шаблон, указанный в этом разделе, [rand.eng] требует удержания одного или нескольких отношений, включающих значение (значения) не относящихся к типу параметров шаблона. Программа, реализующая любой из этих шаблонов, плохо сформирована, если какая-либо такая требуемая взаимосвязь не выполняется.

Для каждого механизма случайных чисел и для каждого адаптера механизма случайных чисел, X определенных в этом подпункте ([rand.eng]) и в подпункте [rand.adapt]:

(7.1)
если конструктор
```
template <class Sseq> explicit X(Sseq& q);
```
вызывается с типом Sseq , который не квалифицируется как начальная последовательность, тогда этот конструктор не должен участвовать в разрешении перегрузки;
(7.2)
если функция-член
```
template <class Sseq> void seed(Sseq& q);
```
вызывается с типом Sseq , который не квалифицируется как начальная последовательность, то эта функция не должна участвовать в разрешении перегрузки.

Степень, в которой реализация определяет, что тип не может быть начальной последовательностью, не указана, за исключением того, что, как минимум, тип не должен квалифицироваться как начальная последовательность, если он неявно конвертируется в X::result_type.

29.6.3.1 Class template linear_congruential_engine [rand.eng.lcong]

Механизм linear_congruential_engine случайных чисел производит беззнаковые целые случайные числа. Состояние из объекта имеет размер и состоит из одного целого числа. Алгоритм перехода представляет собой модульную линейную функцию формы ; алгоритм генерации есть . x $_{i}$ linear_congruential_engine x 1 $T A (x_{i}) = (a \cdot x_{i} + c) mod m$ $G A (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);
  };

Если параметр шаблона m равен 0, модуль, m используемый в этом разделе, равен плюсу . [ не обязательно представлять как значение типа . ] [rand.eng.lcong] numeric_limits<result_type>::max() 1 Note: m result_type — end note

Если параметр шаблона m не равен 0, должны выполняться следующие отношения: a < m и c < m.

Текстовое представление состоит из значения x $_{i}$ .

explicit linear_congruential_engine(result_type s = default_seed);

Effects: Создает linear_congruential_engine объект. Если $c mod m$ есть 0 и $s mod m$ есть 0, устанавливает состояние двигателя в 1, в противном случае устанавливает состояние двигателя в $s mod m$ .

template<class Sseq> explicit linear_congruential_engine(Sseq& q);

Effects: Создает linear_congruential_engine объект. С $k = ⌈ \frac{{log}_{2} m}{32} ⌉$ и a массивом (или эквивалентом) длины $k + 3$ вызывает, q.generate( $a + 0$ , $a + k + 3$ ) а затем вычисляет $S = (\sum_{j = 0}^{k - 1} a_{j + 3} \cdot 2^{32 j}) mod m$ . Если $c mod m$ есть 0 и S есть 0, устанавливает состояние двигателя в 1, иначе устанавливает состояние двигателя в S.

29.6.3.2 Class template mersenne_twister_engine [rand.eng.mers]

Механизм mersenne_twister_engine случайных чисел270 производит беззнаковые целые случайные числа в закрытом интервале $[0, 2^{w} - 1]$ . Состояние из объекта имеет размер и состоит из последовательности из значений типа поставляемого ; все применяемые индексы следует брать по модулю .x $_{i}$ mersenne_twister_engine x n X n x X n

Алгоритм перехода использует сдвиговый регистр с обобщенной обратной связью, определяемый значениями сдвига и , значением поворота и условной xor-маской . Чтобы улучшить однородность результата, биты необработанного регистра сдвига дополнительно (т. Е. Скремблируются) в соответствии с матрицей битового скремблирования, определенной значениями и . n m r a tempered $u, d, s, b, t, c,$ ℓ

Переход между состояниями выполняется следующим образом:

a)Соедините верхние $w - r$ биты $X_{i - n}$ с младшими r битами, $X_{i + 1 - n}$ чтобы получить беззнаковое целое число Y.
b)С $α = a \cdot (Y b i t a n d 1)$ , установите $X_{i}$ на $X_{i + m - n} x o r (Y r s h i f t 1) x o r α$ .

Последовательность X инициализируется с помощью множителя инициализации f.

Алгоритм генерации определяет беззнаковые целочисленные значения следующим образом, а затем выдает в качестве своего результата: $z_{1}, z_{2}, z_{3}, z_{4}$ $z_{4}$

a)Пусть $z_{1} = X_{i} x o r ((X_{i} r s h i f t u) b i t a n d d)$ .
b)Пусть $z_{2} = z_{1} x o r ((z_{1} {l s h i f t}_{w} s) b i t a n d b)$ .
c)Пусть $z_{3} = z_{2} x o r ((z_{2} {l s h i f t}_{w} t) b i t a n d c)$ .
d)Пусть $z_{4} = z_{3} x o r (z_{3} r s h i f t ℓ)$ .

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

Следующие соотношения должны занимать: 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, и f <= (1u<<w) - 1u.

Текстовое представление о x $_{i}$ состоит из значений $X_{i - n}, \dots, X_{i - 1}$ , в таком порядке.

explicit mersenne_twister_engine(result_type value = default_seed);

Effects: Создает mersenne_twister_engine объект. Устанавливается $X_{- n}$ на $value mod 2^{w}$ . Затем итеративно для $i = 1 - n, \dots, - 1$ , наборы $X_{i}$ для

$[f \cdot (X_{i - 1} x o r (X_{i - 1} r s h i f t (w - 2))) + i mod n] mod 2^{w} .$

Complexity: $O (n)$ .

template<class Sseq> explicit mersenne_twister_engine(Sseq& q);

Effects: Создает mersenne_twister_engine объект. With $k = ⌈ w / 32 ⌉$ и a массив (или эквивалент) длины $n \cdot k$ вызывает, q.generate( $a + 0$ , $a + n \cdot k$ ) а затем, итеративно для $i = - n, \dots, - 1$ , устанавливает $X_{i}$ значение $(\sum_{j = 0}^{k - 1} a_{k (i + n) + j} \cdot 2^{32 j}) mod 2^{w}$ . Наконец, если наиболее значимые $w - r$ биты $X_{- n}$ равны нуль, и если каждый из других в результате чего $X_{i}$ это 0, изменяется $X_{- n}$ с $2^{w - 1}$ .

270)

Название этого механизма частично относится к свойству его периода: для правильно выбранных значений параметров период тесно связан с большим простым числом Мерсенна.

29.6.3.3 Class template subtract_with_carry_engine [rand.eng.sub]

Механизм subtract_with_carry_engine случайных чисел производит беззнаковые целые случайные числа.

Состояние из объекта имеет размера , и состоит из последовательности из целочисленных значений ; все применяемые индексы следует брать по модулю . Состояние дополнительно состоит из целого числа (известного как ) , значение которого равно или . x $_{i}$ subtract_with_carry_engine x $O (r)$ X r $0 \leq X_{i} < m = 2^{w}$ X r x $_{i}$ c carry 0 1

Переход между состояниями выполняется следующим образом:

a)Пусть $Y = X_{i - s} - X_{i - r} - c$ .
b)Установите $X_{i}$ на $y = Y mod m$ . Установите c в 1, если $Y < 0$ , в противном случае установите c в 0.

[ Note: Этот алгоритм соответствует модульной линейной функции вида $T A (x_{i}) = (a \cdot x_{i}) mod b$ , где b имеет вид $m^{r} - m^{s} + 1$ и $a = b - (b - 1) / m$ . ] — end note

Алгоритм генерации задается формулой , где - значение, полученное в результате улучшения состояния двигателя, как описано выше. $G A (x_{i}) = y$ y

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

Следующие соотношения должны проводить: 0u < s, s < r, 0 < w, и w <= numeric_limits<UIntType>::digits.

Текстовое представление состоит из значений в указанном порядке, за которыми следует . $X_{i - r}, \dots, X_{i - 1}$ c

explicit subtract_with_carry_engine(result_type value = default_seed);

Effects: Создает subtract_with_carry_engine объект. Устанавливает значения $X_{- r}, \dots, X_{- 1}$ в указанном ниже порядке в указанном ниже порядке. Если $X_{- 1}$ есть, то 0устанавливается c в 1; в противном случае устанавливается c на 0.

Для того, чтобы установить значение $X_{k}$ , первые построить e, А linear_congruential_engine объект, как если бы по следующему определению:

linear_congruential_engine<result_type,
                          40014u,0u,2147483563u> e(value == 0u ? default_seed : value);

Затем, чтобы установить каждый $X_{k}$ , получить новые значения $z_{0}, \dots, z_{n - 1}$ из $n = ⌈ w / 32 ⌉$ последовательных вызовов e взятого по модулю $2^{32}$ . Установите $X_{k}$ на $(\sum_{j = 0}^{n - 1} z_{j} \cdot 2^{32 j}) mod m$ .

Complexity: Собственно $n \cdot r$ заклинания e.

template<class Sseq> explicit subtract_with_carry_engine(Sseq& q);

Effects: Создает subtract_with_carry_engine объект. With $k = ⌈ w / 32 ⌉$ и a массив (или эквивалент) длины $r \cdot k$ вызывает, q.generate( $a + 0$ , $a + r \cdot k$ ) а затем, итеративно для $i = - r, \dots, - 1$ , устанавливает $X_{i}$ значение $(\sum_{j = 0}^{k - 1} a_{k (i + r) + j} \cdot 2^{32 j}) mod m$ . Если $X_{- 1}$ есть, то 0устанавливается c в 1; в противном случае устанавливается c на 0.

29 Numerics library [numerics]

29.6 Random number generation [rand]

29.6.3 Random number engine class templates [rand.eng]

29.6.3.1 Class template linear_­congruential_­engine [rand.eng.lcong]

29.6.3.2 Class template mersenne_­twister_­engine [rand.eng.mers]

29.6.3.3 Class template subtract_­with_­carry_­engine [rand.eng.sub]

29.6.3.1 Class template linear_congruential_engine [rand.eng.lcong]

29.6.3.2 Class template mersenne_twister_engine [rand.eng.mers]

29.6.3.3 Class template subtract_with_carry_engine [rand.eng.sub]