29 Numerics library [numerics]

29.6 Random number generation [rand]

29.6.3 Random number engine class templates [rand.eng]

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

1
#

Механизм mersenne_­twister_­engine случайных чисел270 производит беззнаковые целые случайные числа в закрытом интервале [0,2w−1]. Состояние из объекта имеет размер и состоит из последовательности из значений типа поставляемого ; все применяемые индексы следует брать по модулю .xi mersenne_­twister_­engine x n X n x X n

2
#

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

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

  1. a)Соедините верхние w−r биты Xi−n с младшими r битами, Xi+1−n чтобы получить беззнаковое целое число Y.

  2. b)С α=a⋅(Ybitand1), установите Xi на Xi+m−nxor(Yrshift1)xorα.

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

3
#

Алгоритм генерации определяет беззнаковые целочисленные значения следующим образом, а затем выдает в качестве своего результата: z1,z2,z3,z4 z4

  1. a)Пусть z1=Xixor((Xirshiftu)bitandd).

  2. b)Пусть z2=z1xor((z1lshiftws)bitandb).

  3. c)Пусть z3=z2xor((z2lshiftwt)bitandc).

  4. d)Пусть z4=z3xor(z3rshiftℓ). 

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

Следующие соотношения должны занимать: 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.

5
#

Текстовое представление о xi состоит из значений Xi−n,…,Xi−1, в таком порядке.

explicit mersenne_twister_engine(result_type value = default_seed);

6
#

Effects: Создает mersenne_­twister_­engine объект. Устанавливается X−n на valuemod2w. Затем итеративно для i=1−n,…,−1, наборы Xi для

[f⋅(Xi−1xor(Xi−1rshift(w−2)))+imodn]mod2w.

7
#

Complexity: O(n).

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

8
#

Effects: Создает mersenne_­twister_­engine объект. With k=⌈w/32⌉ и a массив (или эквивалент) длины n⋅kвызывает, q.generate(a+0, a+n⋅k) а затем, итеративно для i=−n,…,−1, устанавливает Xi значение (∑k−1j=0ak(i+n)+j⋅232j)mod2w. Наконец, если наиболее значимые w−r биты X−n равны нуль, и если каждый из других в результате чего Xi это 0, изменяется X−n с 2w−1.

270)

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