Полное факториальное моделирование равномерных последовательностей целых случайных величин

14 / 18

Полное факториальное моделирование равномерных последовательностей…
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 5 145
  2 ! 1 2 3 (2 1) 2 .w w w
T N w       
Непосредственный сравнительный анализ этих двух формул свидетельст-
вует о том, что множество факториальных равномерных последовательностей
превосходит по их числу множество вихревых последовательностей:
   .
F T N w N w
Однако вихревой генератор nsDeonYuliTwist32D уже успешно существует
[19], а факториальный генератор находится еще только на стадии начального
анализа. Очевидно, что только факториальный вариант генерации может обес-
печить абсолютно все последовательности случайных величин длиной w бит.
Вихревой генератор может создать только часть их них.
Заключение. Генераторы равномерных случайных последовательностей
могут допускать повторяемость и пропуски генерации случайных величин. Од-
нако современные вихревые кольцевые генераторы позволяют исключить по-
вторяемость и пропуски генерации. Такой вид технологии использует битовый
сдвиг внутри массива, создавая различные вихревые последовательности. Всего
можно создать только 2w w  вихревых последовательностей. Как было доказано
в теореме об упорядоченной биекции, полное множество содержит 2 !w равно-
мерных последовательностей неповторяющихся случайных величин длиной
w бит. Проведенное моделирование подтверждает теоретические результаты.
Полученные результаты можно использовать в огромном количестве приклад-
ных задач тестовых испытаний и планировании экспериментов.
ЛИТЕРАТУРА
1. Leva J.L. A fast normal random number generator // TOMS. 1992. Vol. 18. Iss. 4. P. 449–453.
DOI: 10.1145/138351.138364
2. Applebaum B. Pseudorandom generators with long stretch and low locality from random local
one-way functions // Proc. 44th Annual ACM Symposium on Theory of Computing. New York,
ACM, 2012. P. 805–816. DOI: 10.1145/2213977.2214050
3. White D.R., Clark J., Jacob J., Poulding S.M. Searching for resource-efficient programs: Low-
power pseudorandom number generators // Proc. 10th Annual Conf. on Genetic and Evolutionary
Computation. New York, ACM, 2008. P. 1775–1782. DOI: 10.1145/1389095.1389437
URL:
4. Langdon W.B. A fast high quality pseudo random number generator for nVidia CUDA //
Proc. 11th Annual Conf. on Genetic and Evolutionary Computation. New York, ACM, 2009.
P. 2511–2514. DOI: 10.1145/1570256.1570353
URL:
5. Deon A.F., Menyaev Y.A. The complete set simulation of stochastic sequences without repeated
and skipped elements // Journal of Universal Computer Science. 2016. Vol. 22. Iss. 8. P. 1023–1047.
DOI: 10.3217/jucs-022-08-1023
6. Lewko A.B., Waters B. Efficient pseudorandom functions from the decisional linear assumption
and weaker variants // Proc. 16th ACM Conf. on Computer and Communications Security.
New York, ACM, 2009. P. 112–120. DOI: 10.1145/1653662.1653677