Датчики псевдослучайных чисел

Someone

Линейный конгруэнтный метод

Поскольку на нашем сайте можно найти датчик (генератор) псевдослучайных чисел RandAs, к нам иногда обращаются с вопросом о том, с помощью какого алгоритма можно генерировать такие числа. Этот вопрос подробно обсуждается в книге [1], поэтому здесь мы ограничимся только некоторыми простыми замечаниями.

Речь будет идти исключительно о генерации целых чисел отрезка , где - натуральное число.

Прежде всего, нужно понимать, что последовательность чисел, порождаемая любым алгоритмом, не может считаться случайной, если под случайной последовательностью понимать результат серии независимых испытаний, в которых все исходы равновероятны. Однако нам вполне достаточно того, что эта последовательность в интересующих нас приложениях выглядит как случайная. С другой стороны, в бесконечной случайной последовательности с вероятностью должна бесконечно много раз встретиться любая наперёд заданная конечная последовательность целых чисел отрезка , например, последовательность, состоящая из миллиона нулей; никто не может "запретить" этой последовательности встретиться в самом начале наших "экспериментов". Так что обнаружение каких-либо закономерностей в просмотренном конечном отрезке бесконечной последовательности нельзя рассматривать как доказательство её неслучайности.

Разумеется, такие "отклонения от случайности" в наперёд заданном отрезке случайной последовательности маловероятны и встречаются редко, но они вполне возможны [Примечание 1].

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

,

(1)

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

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

В качестве простого, но эффективного алгоритма выработки псевдослучайных последовательностей, в книге [1] рекомендуется и подробно изучается так называемый линейный конгруэнтный метод.

Этот метод состоит в следующем. Выбирается натуральное число , которое далее называется модулем. Затем выбираются целые числа (множитель) и (приращение), удовлетворяющие условиям и . Начав с произвольного целого числа (), порождаем последовательность псевдослучайных чисел (1) по формуле [Примечание 2]

, .

(2)

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

Максимальный достижимый период последовательности (2) равен . Такой период получается тогда и только тогда, когда параметры , и удовлетворяют следующим условиям:

1. число делится на все простые делители числа ;
2. если делится на , то и делится на ;
3. число взаимно просто с .

Далее будем предполагать, что эти условия выполняются.

Заметим, что значение удовлетворяет условиям I и II, но брать такое не следует: в этом случае

,

так что трудно рассчитывать на "случайность" такой последовательности. Поэтому далее мы будем предполагать, что и, соответственно, . В этом случае, используя формулу суммы геометрической прогрессии, легко получить соотношение, обобщающее исходное соотношение (2):

.

(3)

Условие вместе с условием максимальности периода сразу же исключают многие значения . Например, если , где - простые числа, а , то единственное значение , удовлетворяющее условиям I и II, - это . Поэтому такие значения рассматривать не будем.

Другое ограничение накладывается понятием мощности линейной конгруэнтной последовательности. Мощность определяется как наименьшее целое число , для которого делится на . Из условия I следует, что такое обязательно существует.

Предположим, что мощность равна . Пользуясь для вычисления формулой бинома Ньютона [Примечание 3], можно привести формулу (3) к виду

(4)

или к виду

.

(5)

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

Практика показывает, что последовательности с небольшой мощностью "недостаточно случайны", поэтому желательно, чтобы мощность была "достаточно" большой; при этом большая мощность сама по себе ещё не гарантирует "хорошего" поведения псевдослучайной последовательности.

Практически это означает, что модуль должен делиться на достаточно большую степень какого-нибудь простого числа . Если делится на , где - нечётное простое число, то мы можем рассчитывать на мощность , взяв делящимся на , но не делящимся на ; если делится на , где , то можно рассчитывать на мощность [Примечание 4], взяв делящимся на , но не делящимся на (это означает, что множитель при делении на должен давать в остатке ).

Поскольку компьютеры, как правило, используют двоичную систему счисления, чаще всего берут в качестве модуля степень числа : . Это удобно ещё и потому, что при вычислении остатка при делении на можно обойтись без деления, просто отбросив старшие разряды числа. Как было только что сказано, в этом случае наибольшая мощность получается, если множитель при делении на даёт в остатке .

Заметим также, что идея использовать числа последовательности (1) не подряд, а только каждое -ое (), вопреки интуитивному ожиданию, что в последовательности

(6)

зависимость между соседними элементами меньше, чем в исходной последовательности (1), не оправдывается.

Действительно, из формулы (3) следует, что эта последовательность имеет такой же вид, что и исходная последовательность (1), только имеет параметры , и . Ясно, что "прореженная" последовательность не может иметь больший период, чем последовательность (1). Из указанных формул, в частности, следует, что если делится на , а делится на , то делится на и может делиться на большую степень числа . Поэтому "прореженная" последовательность имеет мощность, не превосходящую мощности первоначальной последовательности. В действительности, как мы сейчас увидим, период (и мощность) последовательности (6) может быть меньше периода (и мощности) последовательности (1).

Обозначим [Примечание 5] и . Проверим, что число делится на . Используя формулу бинома Ньютона для вычисления , получим

.

(7)

Предположим, что делится на и не делится на , где - простое число и . Тогда делится на , так как делится на , а делится на все простые делители числа .

Первое слагаемое суммы (7) делится на .

Рассмотрим -тое слагаемое при . Числитель этой дроби делится на , где , а знаменатель - на , где (учитывая, что , и что в первых двух суммах имеется только конечное число слагаемых, отличных от ) и, следовательно, . Поэтому -тый член суммы (7) делится на , где . Поэтому все члены суммы (7) делятся на . Таким образом, число делится на все простые делители числа в необходимых степенях; следовательно, оно делится и на .

Пользуясь только что доказанной делимостью, проверим, что все члены последовательности (6) при делении на дают один и тот же остаток. Для этого нужно доказать, что разность делится на . Так как модуль делится на , и имея в виду формулу (3), достаточно проверить, что делится на , а это сразу же следует из доказанного.

Отсюда следует также, что период последовательности (6) не превосходит . Легко проверить, что этот период равен . Действительно, по свойству наибольшего общего делителя существуют такие целые числа и , что выполняется равенство . Тогда, как легко видеть, , и так далее. Поэтому последовательность (6) содержит все числа последовательности , которых как раз штук.

Обозначим остаток, который дают при делении на все члены последовательности (6). Считаем, естественно, что . Тогда число является целым и .

Элементы последовательности (6) выражаются через элементы последовательности

(8)

формулой

.

(9)

Последовательность (8) также является линейной конгруэнтной последовательностью:

, ,

(10)

где , и .

Это ещё раз показывает, что "прореженная" последовательность не имеет никаких очевидных преимуществ по сравнению с исходной.

Однако такого рода "прореженные" последовательности при использовании датчиков псевдослучайных чисел возникают естественным образом. Нередко каждый цикл расчётов требует не одного псевдослучайного числа, а . В таком случае элементы последовательности (1) используются группами:

.

Взяв первые элементы каждой группы, получим "прореженную" последовательность типа (6).

Спектральный тест

В книге [1] описано довольно большое число различных тестов для проверки датчиков псевдослучайных чисел. Наиболее важным там считается так называемый спектральный тест. Этот тест основан на дискретном преобразовании Фурье.

Предположим, что датчик псевдослучайных чисел используется следующим образом: каждый цикл расчётов использует псевдослучайных чисел; в -том цикле используются числа

,

(11)

где и [Примечание 6]. Например, в книге [1] спектральный тест даётся для случая (точнее, для случая взаимно простых и ) и ; описанному выше разбиению на группы соответствуют значения и .

Между прочим, спектральный тест проверяет только "случайность" внутри групп (11), но не контролирует возможную "неслучайность" последовательности групп. Проверка последовательности (8) не выглядит достаточной для этого.

Применяя дискретное преобразование Фурье так, как это описано в книге [1], и имея в виду, что период последовательности (6) равен , где, как и раньше, , получим [Примечание 7]

.

Используя формулу (3) и обозначая , приведём это выражение к виду

.

Подставив выражение (9), получим

.

Поскольку числа (8) - это "перемешанные" числа , последнее выражение можно записать также в виде

.

Последнее выражение представляет собой сумму геометрической прогрессии; используя соответствующую формулу [Примечание 8], получим (при )

,

если - не целое число, так как в этом случае , и

,

если - целое число, так как в этом случае .

Из этих вычислений следует, что во всех случаях, когда число не делится на [Примечание 9]; если же делится на , то .

Таким образом, при использовании элементов линейной конгруэнтной последовательности (2) максимального периода группами (11) наименьшее волновое число равно

,

(12)

где минимум берётся по всем наборам чисел , для которых число делится на . Как и в книге [1], задача сводится к отысканию наименьшего значения квадратичной формы

при целых значениях , хотя бы одно из которых не равно .

В книге [1] качество датчика рекомендуется оценивать по набору чисел [Примечание 10]

.

(13)

Малые значения соответствуют "отсутствию" случайности, большие - "наличию".

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

Результаты применения спектрального теста к датчику псевдослучайных чисел RandAs продемонстрированы в статье "Датчик псевдослучайных чисел RandAs".

Литература

[1] Д.Кнут. Искусство программирования для ЭВМ. Том2. Получисленные алгоритмы. "Мир", Москва, 1977.

Примечания

1)	Необходимо учитывать ещё то обстоятельство, что человек очень легко находит "закономерности" в хаосе случайных точек, поэтому случайность предстаёт перед человеком под маской закономерности. Посмотрите, например, на звёздное небо. Другое дело, что "закономерность", обнаруженная на одном участке случайной последовательности, не работает на другом её участке. [Вернуться]
2)	Запись "" означает, что число равно остатку от деления числа на число . [Вернуться]
3)	, где - биномиальные коэффициенты (). Поскольку , получаем . Считаем, что при или . При удобно пользоваться формулой , из которой следует, что является многочленом степени от перемнной . [Вернуться]
4)	Квадратные скобки обозначают целую часть числа: - наибольшее целое число, не превосходящее числа . [Вернуться]
5)	- наибольший общий делитель чисел и . [Вернуться]
6)	Параметры рекомендуется выбирать так, чтобы группы, используемые в программе, не имели общих элементов. [Вернуться]
7)	- показательная функция; - мнимая единица. [Вернуться]
8)	, если , и , если . [Вернуться]
9)	Так как числа и взаимно просты, то множитель для делимости числа на не играет роли и может быть опущен. [Вернуться]
10)	Заметим, что всегда , поэтому можно считать, что . [Вернуться]

Если у Вас возникнут какие-либо вопросы, Если вопросов будет много, мы, возможно, сделаем на сайте раздел вопросов и ответов.