18 / 25
Генератор равномерных случайных величин по технологии полного вихревого массива
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 2
103
В качестве примера рассмотрим часто используемые в практических разра-
ботках случайные величины длиной 16 бит. Это двухбайтные числа из диапазо-
на
0, 65535 .
Число случайных величин в одной полной последовательности
составляет
(
)
16
16 2 2 65536.
w
N w
= = = =
Общее число неповторяющихся число-
вых последовательностей определяется как
(
)
4
3 3 4 3 2 3
16 2
2 2
w
s
N w w
−
⋅ −
= = ⋅
= ⋅
=
316 1 49
2
2 .
⋅ +
= =
Тогда количество всех генерируемых чисел определяется как
(
)
4 49 51
16
2 2 2 .
ns
ns
N w N N
= = ⋅
= ⋅
=
В этом случае битовая длина будет
(
)
4 51 55
.
16
2 2 2
bs
ns
N w w N
= = ⋅
= ⋅
=
Этот результат можно сравнить с оценкой для генераторов семейства
MT19937 [13]. Просматривая программный код этого генератора, обнаружива-
ем, что битовая длина генерируемых случайных величин составляет
32
32.
w
=
Длина массива начальной конгруэнтной генерации задана как
32
624
MT
=
эле-
мента. Глобальный вихрь не использует кольцевой перенос старшего бита по-
следовательности. Эти данные говорят о том, что полное число генерируемых
случайных величин составляет
= ⋅
− = ⋅
− =
− =
32
32
32
31 32 624 31 19968 31 19937.
ns
MT w MT
Вычитание константы 31 связано с тем, что вихрь не учитывает кольцо
избыточных бит. Гипотетически в этих
19 937
переменных можно получить не-
повторяющуюся битовую последовательность в
19937
2
бит. Однако это только
гипотетически, поскольку конгруэнтный генератор вихря 0 с последующими
однобитными вихрями позволяют получать только
=
19 937
ns
MT
чисел. Чтобы
получить больше чисел, необходимо вручную задавать новое исходное число
x
0
,
поскольку конгруэнтные константы
a
и
c
заданы стационарно и не подлежат
автоматическому изменению.
Продолжим обсуждение настройки рассмотренного вихревого генератора.
Необходимо явно убедиться, что все создаваемые случайные величины в гене-
раторе
nsDeonYuliTwist28DA
повторяются одинаковое число раз. Поскольку
условие равномерности предполагает, что все величины в полной генерации
присутствуют одинаковое число раз, то в простейшем варианте в одной такой
последовательности все числа встречаются лишь один раз. Следовательно, во
множестве перестановок любое число встречается столько раз, сколько самих
перестановок, так как в каждой равномерной перестановке любое число встре-
чается только один раз. Это является прекрасным средством для подтвержде-
ния равномерности генераторов.
Далее приведен код, в котором каждые элементы массива
xC
являются со-
ответствующими счетчиками случайных величин, т. е. индекс счетчика равен
случайной величине. В программе проверяется равномерность вихря 0, кото-
рый соответствует начальной конгруэнтной генерации. По умолчанию битовая
длина каждой случайной величины принимается
16
w
=
бит. Тогда длина пол-
ной последовательности составит
= = =
16
2 2 65536
w
N
случайных величин.