4 / 25
Генератор равномерных случайных величин по технологии полного вихревого массива
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 2
89
допустимых значений параметров
a
,
c
,
x
. Другими словами, мы имеем не полную
возможность равномерных последовательностей, а лишь
СС
= 56/392 =
= 0,1429 = 14,29 % полного конгруэнтного списка. Показатель невелик.
При генерации конгруэнтных случайных последовательностей принимается
следующая технология: операцию модуля
mod
в (1) можно заменить на операцию &
битовой конъюнкции. Такой вариант действий допускается, если генерируемое
двоичное число
x
длиной
w
бит принадлежит интервалу
0, 2 1 .
w
x
∈ −
Технология вихревых генераторов использует в качестве основы битовый
сдвиг двоичных чисел в случайной последовательности. Частный случай такого
подхода использовался в классических работах японских исследователей
Матсумото и Нишимура [13, 14, 19] на основе ранних исследований Леви [20].
Они разработали несколько генераторов, включая хорошо известный генератор
MT19937 (или MT19937-64 для выполнения с 64-битными словами), которые,
по оценкам авторов, имеют большую величину повторяемости
19937
2 1
−
, что до-
вольно значительно в некоторых специальных случаях.
В общем случае суть кольцевого сдвига или глобального вихря заключается
в следующем. Если взять два числа
i
x
и
1
i
x
+
одинаковой битовой длины
w
, то
новые значения создаются согласно правилу: значения бит, взятые из числа
1
,
i
x
+
успешно сдвигаются влево в число ;
i
x
в то же время высвобождающиеся
биты слева из числа
i
x
циклично присоединяются один за другим к правой ча-
сти числа
1
.
i
x
+
В качестве примера покажем вихревой сдвиг в двоичной форме при
3
w
=
для последовательности чисел
0 10
2
5
,
101
x
= =
1 10
2
3
,
011
x
= =
2 10
2
6
.
110
x
= =
Структуру такого подхода можно представить так же, как на диаграмме (рис. 1),
где рассмотрены первые две строки. Вихрь 0 является начальной последователь-
ностью конгруэнтной генерации. Вихрь 1 является результатом глобального
сдвига влево на 1 бит. В свою очередь старший бит исходной последовательности
совершает кольцевое движение в последнюю позицию справа в следующей по-
следовательности. Таким образом, исходная последовательность 101 011 110
2
=
= 5 3 6
10
превращается в вихревую 010 111 101
2
= 2 7 5
10
. Этот алгоритм называется
вихревой технологией, или кольцевым вихрем, или глобальным кольцевым вих-
Рис. 1.
Диаграмма кольцевого вихря