Генератор псевдослучайных чисел Mersenne Twister

Принцип получения псевдослучайных чисел

В качестве наглядного примера, рассмотрим сначала один из простейших генераторов псевдослучайных чисел – метод середины квадратов, предложенный Дж. Нейманом в 1946 г. Пусть

g₀ = 0.9876 -

число, инициализирующее случайную последовательность. Возведение его в квадрат даёт восьмизначное число

= 0.97535376.

Четыре средние цифры этого числа можно использовать как следующий элемент псевдослучайной последовательности:

g₁ = 0.5353.

Дальнейшая генерация аналогична:

= 0.28654609 Þ g₂ = 0.6546, и так далее.

Этот пример демонстрирует основные особенности генераторов псевдослучайных чисел:

· использование предыдущих членов последовательности для получения следующих;

· получение очередного числа как части мантиссы некоторого промежуточного результата;

· существование конечного периода последовательности; в показанном примере последовательность повторится полностью после появления числа, совпадающего с одним из предыдущих (поскольку {g_i+1=f(g_i), g_i+2=f(g_i+1), ¼}, то совпадение g_k = g_i приведёт к тому, что g_k+1=f(g_k) =f(g_i), и так далее).

Алгоритм генератора Mersenne Twister

Принцип работы генератора псевдослучайных чисел Mersenne Twister [11],[14], который мы в дальнейшем будем использовать, похож на показанный выше. Этот алгоритм относится к числу генераторов, основанных на линейных рекуррентных соотношениях, связывающих следующие элементы случайной последовательности {x_i} с предыдущими.

Элементы последовательности x_i в алгоритме Mersenne Twister рассматриваются как w-компонентные векторы из чисел 0 и 1 (в дальнейшем - векторы над полем F₂), представляющие собой побитовое представление целых чисел w-битной точности. Ниже w = 32, поскольку именно это значение соответствует одинарной точности вычислений на графических процессорах.

Рекуррентное соотношение для генератора Mersenne Twister имеет вид

,

где - соединение r первых битов вектора x_k с (w-r) последними битами вектора x_k+1; r - параметр в диапазоне от 1 до w-1; - произвольная двоичная матрица размерности (w´w) над полем F₂; «·» - операция скалярного умножения вектора x = справа на матрицу , при котором нули и единицы складываются по модулю 2 (операция XOR).

Для того, чтобы в умножение на матрицу могло быть представлено простой серией побитовых операций над числом x, эта матрица выбирается в виде

,

где a = [a_w-1, a_w-1, ¼, a₀] – вектор над полем F₂, представляющий некоторое целое число с побитовым представлением a_w-1, a_w-1, ¼, a₀. Тогда умножение реализуется следующими побитовыми операциями:

Здесь - операция побитового сдвига числа x вправо на n битов, Å - сложение по модулю 2 (побитовая операция XOR). Для улучшения свойств случайного распределения, полученное число y умножается (операцией «·») на «закаливающую» (англ. tempering) матрицу Т, такую, что это умножение представляется следующей последовательностью побитовых операций:

z = y Å (z >> u);

z = z Å (z << s) AND b;

z = z Å (z << t) AND c;

z = z Å (z >> l);

Здесь u, s, t, l, b и c – параметры генератора, представляющие собой 32-битные векторы над полем F₂, соответствующие некоторым целым числам w-битной точности. В результате всех операций, очередной элемент псевдослучайной последовательности x_k (k ≥ n) оказывается функцией трёх предыдущих элементов:

.

Значения m и n, вместе с другими константами, входящими в формулы -, являются параметрами генератора. Первые n членов последовательности {x₀, x₁, ¼, x_n-1} должны быть заданы как инициализирующая последовательность (англ. seeds).

Для перехода от случайной последовательности целых чисел {x_i} к последовательности вещественных чисел g Î [0; 1] достаточно разделить все числа x_i на 2^w. Если w = 32, то

.

Период генератора и значения параметров алгоритма

Согласно работе [11], период генератора Mersenne Twister, - количество случайных чисел, генерируемых до зацикливания последовательности, - при оптимальных сочетаниях параметров дается формулой

T = 2^nw-r - 1,

где n – длина инициализирующей последовательности {x₀, x₁, ¼, x_n-1}, w и r – параметры алгоритма, рассмотренные выше. Для получения такого периода и максимального качества случайной последовательности, остальные параметры генератора (a, b, c, u, s, t, l) должны быть согласованы со значениями n, w и r [11].

В работе [11] были исследованы различные наборы параметров, в качестве лучшего из них, по качеству равномерного распределения, был принят набор n = 624, m = 397, r = 31, a = h9908B0DF, b = h9D2C5680, c = hEFC6000, u = 11, s = 7, t = 15, l = 18 [11]. Этим значениям соответствует период

T = 2¹⁹⁹³⁷ - 1 » 10⁶⁰⁰² чисел,

более чем достаточный для любого практического приложения. Этот период является максимальным среди всех генераторов, обсуждавшихся в работе [11].