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

Для порождения последовательности целых чисел из диапазона от 0 до (M-1) наиболее широко используется метод на основе рекуррентной формулы типа

U_n = AU_(n-1) + B (mod M),

где A, B и M - целые числа. A называется множителем, B - приращением, а M - модулем. Процесс начинается с выбора так называемого начального значения U₀ из диапазона от 0 до (M-1). Такая рекуррента должна в конце концов повториться, и очевидно, что максимальный период не может превосходить числа M, так что M нужно выбирать "достаточно большим". Для правильно подобранных значений A, B и M большой период является достижимым. В самом лучшем случае период будет максимальным; тогда выбор начального значения не важен, так как в этом случае в последовательности встретятся все значения по модулю M, кроме одного. Данный метод лежит в основе большинства генераторов случайных чисел, применяемых в компьютерах, причем значения модуля, приращения и множителя встроены в программу, а выбор начального значения предоставляется пользователю. Чтобы обеспечить еще лучшие результаты, можно использовать несколько таких генераторов, комбинируя каким-либо образом их выходные последовательности. Другое усовершенствование может состоять в том, чтобы использовать числа не в порядке их получения, а "перетасовать" их каким-нибудь способом, дабы уменьшить риск корреляции между последовательными значениями. Таким способом можно получать длинные "псевдослучайные" последовательности с хорошими свойствами. В таблице 8.1 приведены некоторые из известных "хороших" вариантов выбора чисел A, B и M.

Таблица 8.1

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

Пример 8.4

Используя рекурренту

U_n = 3U_(n-1) + 4 (mod 17),

получить последовательность целых чисел, начиная с

1. U₀ = 5,

2. U₀ = 15.

Решение

(1) Поскольку U₀ = 5, то U₁ = 35+4=192(mod 17), и т.д. Получается последовательность длины 16:

5, 2, 10, 0, 4, 16, 1, 7, 8, 11, 3, 13, 9, 14, 12, 6, 5, 2, 10, ... .

Этот генератор, хотя и скромный с виду, имеет максимально возможный цикл, в данном случае 16. Дополнительные комментарии можно найти в приложении M13.

2. U₀ = 15 дает нам U₁ = 315+4=4915(mod 17), и период равен единице! Это объясняет, почему число 15 не встречается в полученном выше цикле длины 16.

Задача 8.2

Проверить, что последовательность, полученная методом срединных квадратов для четырехзначных чисел, начиная с X=7789, вырождается в цикл из четырех чисел.

Задача 8.3

Каковы будут для U₀ = 1 длины циклов следующих рекуррент:

1. U_n = 3U_(n-1) + 7 (mod 19),

2. U_n = 4U_(n-1) + 7 (mod 19)?

При использовании генераторов псевдослучайных чисел этого типа получаемые значения обычно делят на значение модуля M, чтобы получить в результате действительное число от нуля до единицы. Поскольку генератор вырабатывает целые числа в диапазоне от 0 до (M‑1), то среди получаемых действительных чисел может встретиться число 0.0, но никогда не встретится число 1.0. Это небольшое ограничение, скорее всего, не очень важно, и для правильно подобранных значений A, B и M получаемые действительные числа будут равномерно распределены в диапазоне от 0 до 1. Более подробно этот вопрос освещен в [8.4] и в приложении M13.