Журнал вычислительной математики и математической физики, 2020, T. 60, № 1, стр. 70-79

1. ВВЕДЕНИЕ

В информатике и вычислительной технике случайные числа находят широкое применение: для проведения статистических испытаний, в криптографии, в имитационном моделировании. Однако получение истинно случайных чисел является крайне трудоемким процессом. Это вызвано в первую очередь сложностью и дороговизной генераторов истинно случайных чисел. Также следует учесть, что генерация истинно случайных чисел может занимать много времени, и вполне вероятен вариант, когда при исчерпании источника истинно случайных чисел программа переходит в режим ожидания (время которого тоже случайно). Таким образом, чаще речь идет не об истинно случайных числах, а о псевдослучайных числах. В данной работе мы будем рассматривать программные реализации только генераторов псевдослучайных чисел.

Генераторы псевдослучайных чисел должны удовлетворять следующему ряду критериев [1]:

• для предотвращения зацикливания последовательности псевдослучайных чисел необходимо иметь достаточно длинный период;

• алгоритм должен быть эффективным по скорости работы алгоритма и затрате вычислительных ресурсов;

• алгоритм должен удовлетворять критерию воспроизводимости, то есть должна быть возможность воспроизвести ранее сгенерированную последовательность псевдослучайных чисел любое количество раз;

• алгоритм должен быть переносим по отношению к архитектурам оборудования и операционным окружениям;

• алгоритм должен быть быстрым и ресурсосберегающим.

Тестирование генераторов псевдослучайных чисел фактически заключается в проверке последовательности псевдослучайных величин на независимость, одинаковую распределенность, равномерность на единичном интервале. Работы по данной тематике активно велись и отечественными учеными (см. [2]–[5]). Также доказательство статистической выявляемости псевдослучайных чисел можно найти, например, в [6].

В основе каждой программной реализации генератора псевдослучайных чисел лежит свой алгоритм. Во многих теоретических исследованиях обсуждаются и сравниваются сами алгоритмы, но мы оставим данный аспект без обсуждения. В работе сосредоточимся на вопросах практической проверки качества генерируемых программным кодом последовательностей псевдослучайных чисел. Исследование проводится с помощью программных инструментов.

В рамках работы затрагиваются следующие проблемы. Во-первых, в свободных системах компьютерной алгебры зачастую используют генераторы псевдослучайных чисел, не прошедшие всех возможных тестов. Во-вторых, желательно использовать наилучший (хотя бы по некоторым критериям) генератор псевдослучайных чисел. Для решения данных проблем нами описывается практическая структура стенда для исследования программных реализаций генераторов псевдослучайных чисел. Это позволяет оценить текущую реализацию генератора, встроенную в ту или иную систему компьютерной алгебры. Кроме того, можно подобрать другую программную реализацию для встраивания ее в свободную систему компьютерной алгебры.

В качестве иллюстрации методика исследования продемонстрирована на некоторых системах компьютерной алгебры.

2. ГЕНЕРАТОРЫ В СОВРЕМЕННЫХ СИСТЕМАХ КОМПЬЮТЕРНОЙ АЛГЕБРЫ

Изобретение первого алгоритма генерации последовательности псевдослучайных чисел приписывают Дж. фон Нейману в 1946 г. После этого в 1949 г. Д.Г. Лехмер (D.H. Lehmer) предложил свой алгоритм, который впоследствии был обобщен и стал известен как линейный конгруэнтный генератор (linear congruential generator – LCG) [7]. Именно этот генератор в различных его модификациях стал основным алгоритмом, реализованным в библиотеках на языках Fortran, ADA, C.

В 1995 г. Джордж Марсальея (George Marsaglia) выпустил набор статистических тестов, который позволял проверить, насколько случайную и равномерно-распределенную последовательность чисел дает тот или иной алгоритм. Применение данного набора тестов показало, что подавляющее большинство генераторов случайных чисел на практике дают некачественную последовательность и проваливают большинство тестов.

Данный набор тестов приобрел широкую известность и побудил специалистов начать поиски более качественных алгоритмов генерации случайных чисел и их программных реализаций.

К настоящему моменту в современных версиях стандартных библиотек активно поддерживаемых языков программирования и систем компьютерной алгебры, таких как Maple [8], Mathematica [9], SymPy [10] применяется реализация алгоритма вихрь Мерсенна (MT – Mersenne Twister). Именно этот алгоритм стали повсеместно внедрять как качественную замену LCG, так как он был одним из первых алгоритмов, программная реализация которого проходила все имеющиеся на тот момент тесты. Он был разработан в 1997 г. [11] и получил свое название из-за использования простого числа Мерсенна ${{2}^{{19937}}} - 1$. В зависимости от реализации он обеспечивает период вплоть до ${{2}^{{216091}}} - 1$.

Основным недостатком алгоритма является относительная громоздкость и, как следствие, сравнительно медленная работа программного кода. Заметим также, что в настоящее время разработаны намного более эффективные и простые алгоритмы (см. [12]–[14]). В остальном же данный генератор обеспечивает псевдослучайную последовательность хорошего качества и вполне применим для большинства задач.

Перейдем, однако, к основной цели данной работы. Если в исследовательской работе используется генерация псевдослучайных чисел, то какими средствами можно проверить качество последовательностей этих чисел? Это может быть актуально при использовании нестандартной системы компьютерной алгебры или системы старых версий. Даже если используется одно из современных средств, то остается вопрос выбора удачного начального значения.

Очевидным ответом на данный вопрос будет использование какого-либо программного пакета, реализующего набор статистических тестов. Однако все известные авторам пакеты реализованы на языках C или C++ и для применения их функций непосредственно необходимо низкоуровневое программирование. Так как язык программирования для систем компьютерной алгебры является высокоуровневым проблемно-ориентированным языком программирования, то внедрение функций на языках типа C/C++ может быть невозможно или весьма трудоемко.

На наш взгляд, это затруднение можно обойти, использовав утилиты командной строки. Использование подобных утилит избавит от необходимости внедрять код на языках типа C/C++ в программу и позволит ограничиться созданием скрипта, передающего последовательность анализируемых чисел на вход тестирующей утилите.

3. СТАТИСТИЧЕСКИЕ ТЕСТЫ

Тестирование генераторов псевдослучайных чисел фактически является классической задачей проверки статистических гипотез. Но если в математической статистике обычно ставится задача опровержения нулевой гипотезы, то при тестировании генераторов псевдослучайных чисел, наоборот, нулевую гипотезу пытаются подтвердить. Иными словами, тесты направлены на обоснование того, что сгенерированные последовательности псевдослучайных чисел являются случайными независимо распределенными случайными величинами и не связаны никаким детерминированным законом. Генератор успешно проходит тест, если не удалось найти статистически значимых отклонений от ноль гипотезы.

Так как генератор псевдослучайных чисел является детерминированным алгоритмом, то всегда найдется тот или иной статистический тест, который данный генератор не пройдет. Качество генератора определяется тем, насколько много тестов он может пройти. Поэтому при создании программной реализации тестов их объединяют в наборы тестов и применяют совместно.

Перечислим несколько тестов, которые входят в набор статистических тестов DieHard.

• Тест на игру в кости. Генерируется 200 000 последовательностей равномерно распределенных псевдослучайных чисел. Каждая из полученных последовательностей используется для симуляции игры в кости. Далее проверяется, насколько теоретические значения математического ожидания и дисперсии согласуются с эмпирическими. Для статистической проверки используется критерий $\chi $-квадрат.

• Парадокс дней рождения. Генерируется последовательность на большом интервале. Расстояния между числами должны быть асимптотически распределены по Пуассону.

• Пересекающиеся перестановки. Генерируется большое число выборок из пяти последовательных случайных чисел. Вероятности появления каждой из всех возможных перестановок должны быть статистически эквивалентны.

Всего в DieHard входило 12 тестов. В современных программных пакетах, реализующих наборы статистических тестов, количество тестов существенно увеличено и превышает несколько десятков.

4. ПРОГРАММНЫЕ ПАКЕТЫ НАБОРОВ СТАТИСТИЧЕСКИХ ТЕСТОВ

Как уже отмечалось, исторически первым программным пакетом, реализующим набор статистических тестов (или просто набор тестов) для тестирования генераторов псевдослучайных чисел, был пакет программ DieHard [15], созданный в 1995 г. Джорджем Марсальей (George Marsaglia). Он распространялся на CD-диске и в настоящее время официальная страница доступна только в виде архива. Пакет DieHard на данный момент не актуален, но тесты, входившие в его состав, сейчас включены в другие программные пакеты статистических тестов.

Из актуальных в настоящее время программных пакетов, реализующих наборы тестов, можно выделить следующие четыре.

• TestU01 [16], [17] за авторством Пьера Л’Экуйе и Ричарда Симарда (Pierre L’Ecuyer, Richard Simard). Написана на ANSI C. На сегодняшний день является самым известным набором тестов. Тестирует генераторы, генерирующие числа из интервала $[0,1)$. Последняя версия 1.2.3 от 18 августа 2009 г.

• PractRand [18] за авторством Криса Доти-Хамфри (Chris Doty-Humphrey). Написана на С++11 с элементами C99. Принимает на вход поток байт, может тестировать 32 и 64 битные генераторы. Способен справляться с очень большими объемами данных. Последняя версия 0.94 от 04 августа 2018 г.

• gjrand [19]. Контактов автора на официальном сайте найти не удалось. Написан на С99. Принимает на вход поток байт. Поставляется с набором различных генераторов, способных генерировать не только равномерно-распределенные последовательности псевдослучайных чисел, но и последовательности, подчиняющиеся нормальному, пуассоновскому и некоторым другим распределениям. Последняя версия 4.2.1 от 28 ноября 2014 г.

• DieHarder [20] за авторством Роберта Брауна. Позиционируется как наследник тестов DieHard. Написан на языке C. Требует для своей работы библиотеки GSL [21] и может тестировать любой генератор, с интерфейсом в стиле интерфейсов генераторов из GSL. Последняя версия 3.31.1 от 19 июня 2017 г.

В табл. 1 дана сводка основных характеристик обозреваемых пакетов программ. В колонке Unix указана возможность установки под *nix системами. В колонке Windows поставлен плюс только если программу возможно собрать без установки CygWin или MinGW. При должном старании любую библиотеку можно скомпилировать и под Windows тоже.

Все перечисленные программные пакеты наборов тестов имеют открытый исходный код. TestU01 и DieHarder доступны для установки через официальные репозитории многих дистрибутивов, в частности Ubuntu 18.10. Два других набора тестов необходимо устанавливать путем сборки из исходных кодов. Каждый из перечисленных программных пакетов позволяет проводить тесты как путем подключения библиотек к С/С++ программе пользователя, так и предоставляет утилиту командной строки. Наиболее функциональная утилита командной строки у программного пакета DieHarder.

5. ПРИМЕР ТЕСТИРОВАНИЯ ГЕНЕРАТОРОВ SymPy И Maxima

Рассмотрим, как можно организовать тестирование любого генератора псевдослучайных чисел на примере CAS Maxima и библиотеки SymPy для Python. Будем использовать CAS Maxima версии 5.42.1 и Python 3.6.8, дистрибутив Miniconda. Нашей целью не является сравнение реализаций генераторов, а лишь предоставление примера, который может быть использован для тестирования генераторов в других библиотеках, математических пакетах и системах компьютерной алгебры.

Так как SymPy является python-модулем, то для генерации псевдослучайных чисел используется стандартный модуль random. Следующий фрагмент кода позволяет организовать вывод беззнаковых 64-битных целых чисел в стандартный поток вывода.

 import random

 import sys

 while True:

   r = random.randint(0,2**64-1)

   r = r.to_bytes(8, byteorder="little“, signed=False)

   sys.stdout.buffer.write(r)

В данном фрагменте генерируется целое число из полуинтервала $[0,{{2}^{{64}}})$, затем оно преобразуется в двоичный вид и выводится в стандартный поток вывода. Записав данный скрипт в файл rand_test.py, мы можем организовать тестирование, выполнив в консоли следующую команду:

 python rand_test.py | dieharder -g 200 –a

или

 python rand_test.py | RNG_test stdin64

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

 for i: 1 thru 10 step 1 do print(random(2^64-1))$

Однако на выходе получим столбик целых чисел в текстовом виде, поэтому для тестирования данного генератора воспользуемся возможностью утилиты dieharder считывать данные в текстовом виде из заранее подготовленных файлов (см. п. 4.2.3).

Так как обе системы компьютерной алгебры используют алгоритм вихрь Мерсенна, то полученные результаты тестирования практически одинаковы. Утилита RNG_test для SymPy выдает результат no anomalies in 133 test result(s), а утилита отображает в отчете 5 слабо пройденных тестов из более чем тридцати. Результаты dieharder для Maxima практически идентичны.

6. ЗАКЛЮЧЕНИЕ

Авторы постарались дать исчерпывающее описание практики построения стенда для исследования программной реализации генераторов псевдослучайных чисел. Описанное программное обеспечение дает исследователю выбор из трех утилит командной строки. Эти утилиты снимают необходимость низкоуровневого программирования. Кроме того, их удобно использовать вместе с каким-либо промежуточным связующим языком программирования.

Для использования этих утилит необходимо обеспечить вывод в стандартный поток результатов генерации чисел в бинарном виде. Так как большинство систем компьютерной алгебры ориентированы на высокоуровневое программирование, то обеспечить бинарный вывод может быть затруднительно. В этом случае можно использовать только утилиту dieharder, так как она может обрабатывать данные в текстовом виде.

В конце работы демонстрируются приемы исследования программных реализаций генераторов случайных чисел на примере двух свободных систем компьютерной алгебры.