Таблица 1

СМЕЩЕНИЯ, ПРИВОДЯЩИЕ К ДЛИННЫМ ПЕРИОДАМ ПО МОДУЛЮ 2

(24,55) (37,100) (83,258) (273,607) (576,3217) (7083,19937)

(38,89) (30,127) (107,378) (1029,2281) (4187,9689) (9739,23209)

Расширенные варианты этой таблицы приводятся в работах N. Zierler and J. Brillhart, Information and Control 13 (1968), 541-554, 14 (1969), 566-569, 15 (1969), 67-69; Y. Kurita and M. Matsumoto, Math. Сотр. 56 (1991), 817-821; Heringa, Blote, and Compagner, Int. J. Mod. Phys. C3 (1992), 561-564.

значений An, лежащих строго между Xn-2i и Хп-ьъ (см. упр. 2). Ж.-М. Норманд (J.-M. Normand), Г. Й. Герман (Н. J. Herrmann) и М. Хаджар (М. Hajjar) обнаружили небольшое смещение в числах, генерируемых (7), когда им понадобилось 10 случайных чисе для проводимых с высокой точностью обширных исследований метода Монте-Карло [J. Statistical Physics 52 (1988), 441-446]; но при больших значениях к смещение уменьшалось. В табл. 1 приведено несколько пар чисел (Z,fc), для которых последовательность Хп = (Xn-t + A„ fc) mod 2" имеет период длиной 2~(2* - 1). Случая, когда {1,к) = (30,127), казалось бы, достаточно для большинства применений, особенно в сочетании с другими, увеличивающими случайность, методами, которые мы обсудим ниже.

Генератор случайных чисел во многом подобен сексу: когда он хорош - это прекрасно, когда он плох, все равно приятно (Джордж Марсалья, 1984).

Джордж Марсалья [Сотр. Sci. and Statistics: Symposium on the Interface 16 (1984), 3-10] предложил заменить (7) на

Хп = (Хп-24 Хп-55) mod т, п> 55, (7)

где т кратно 4, а все числа от Ло ДО Х4 нечетны, но сравнимы с 1 (по модулю 4). Тогда второстепенные младшие разряды имеют период 2 - 1, в то время как старшие двоичные разряды более тщательно перемешаны, чем раньше, так как они существенно зависят от всех разрядов Xn-2i и Хп-55- В упр. 31 показано, что длина периода последовательности (7) лишь незначительно меньше длины периода последовательности • (7).

Генераторы последовательности Фибоначчи с запаздыванием успешно применялись во многих ситуациях с 1958 года. Таким образом, открытие в 90-е годы того, что они фактически провалились на крайне простом, незамысловатом критерии случайности, явилось шоком (см. упр. 3.3.2-31). Как избежать таких неприятностей, отбрасьшая ненужные элементы последовательности, рассказывается в конце этого раздела.

Вместо рассмотрения исключительно аддитивных или исключительно мультипликативных последовательностей можно построить достаточно хороший генератор случайных чисел, используя всевозможные линейные комбинации A-i, ..., Хп~к для малых к. В этом случае наилучший результат получается, когда модуль т является большим простым числом; например, т может быть выбрано так, чтобы оно было наибольшим простым числом, которое можно записать одним компьютерным словом (см. табл. 4.5.4-2). Когда т = р - простое число, то по теории конечных полей можно найти множители ai,.. .,ак, такие, что последовательность.

определенная соотношением

Xn = {aiXn-i+---+akXn-k)modp, (8)

будет иметь период длиной р - 1. Здесь Ао,. • •, Xk-i могут быть выбраны произвольно, но так, чтобы все они не были нулями. (Частный случай, когда fc = 1, соответствует мультипликативной конгруэнтной последовательности с уже известным простым модулем.) Константы ai,...,ak в (8) обладают подходящими свойствами тогда и только тогда, когда полином

fix) =х- а.х"------ajfe (9)

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

Конечно, для достижения практических целей недостаточно простого факта существования подходящих констант oi, ojt, дающих период длиной р* - 1. Необходимо быть в состоянии найти их, ведь нельзя проверить все р* возможностей, так как р имеет порядок длины слова компьютера. К счастью, есть точно ¥(р* - 1)/к подходящих наборов (oi,... ,ajt), поэтому в известной степени существует хороший шанс натолкнуться на один из них после нескольких случайных попыток. Но также следует уметь быстро определять, будет ли (9) первообразным полиномом по модулю р. Конечно, немыслимо генерировать до р* - 1 элементов последовательности и ждать повторения! Методы проверки того, что полином будет первообразным по модулю р, обсуждались Аланеном (Alanen) и Кнутом (Knuth) в Sankhya А26 (1964), 305-328. Можно использовать следующий критерий. Пусть

7- = (р=-1)/(р-1).

i) (-1)*~а<; должен быть первообразным корнем по модулю р (см. раздел 3.2.1.2).

ii) Полином х должен быть сравним с (-l)*~ajt по модулям f{x) и р.

iii) Степень mod f{x) (здесь используется арифметика полиномов по модулю р) должна быть положительной для каждого г - простого делителя q.

Эффективный способ вычисления полинома х" mod f{x) с использованием полиномиальной арифметики по модулю, заданному простым числом р, обсуждается в разделе 4.6.2.

Для того чтобы довести до конца тест, необходимо знать разложение на простые множители числа г = (р* - 1)/(р- 1), что и является ограничивающим фактором в вычислениях, г можно разложить на множители в приемлемый отрезок времени, когда fc = 2, 3 и, возможно, 4, но большие значения к усложняют вычисления, когда р большое. Даже при fc = 2 число "значащих случайных цифр", которое достигается при fc = 1, по существу, удваивается, так что большие значения fc вряд ли понадобятся.

Видоизмененный спектральный критерий (раздел 3.3.4) можно использовать для оценки последовательности чисел, генерируемых (8); см. упр. 3.3.4-24. Рассуждения, приведенные в этом разделе, показывают, что не следовало бы делать очевидный выбор (fli =-1-1 или -1), когда встречается такая форма первообразного полинома. Лучше выбрать большие, совершенно "случайные" значения ai,...,ak, удовлетворяющие условиям, и проверить выбор с помощью спектрального критерия. Значительный объем вычислений приходится выполнять при возведении в

степень для нахождении ai,... ,а. Но все известные доводы указывают на то, что результатом будет весьма удовлетворительный источник случайных чисел. Мы, по существу, добились случайности линейных конгруэнтных генераторов с fc-кратной точностью, используя только операции с простой точностью.

Представляет интерес частный случай, когда р = 2. Иногда требуется генератор случайных чисел, вырабатывающий всего лишь случайную последовательность двоичных разрядов - нулей и единиц - вместо дробей, лежащих между нулем и единицей. Существует простой способ генерирования высокослучайных двоичных разрядов последовательности на бинарных компьютерах, основанный на манипулировании fc-разрядными словами. Начать следует с произвольного ненулевого двоичного слова X. Затем необходимо вычислить следующий случайный бит последовательности, выполнив операции, которые приведены на языке компьютера MIX (см. упр. 16):

LDA X (Предположим, что переполнение сейчас "выключено".) ADD X Перенести влево один разряд.

JNOV *+2 Перейти к другой команде, если исходное значение высшего

разряда было нулем.

XOR А Иначе - установить число с "исключающим или". STA X I

Четвертая операция "исключающее или" существует почти на всех двоичных компьютерах (см. упр. 2.5-28 и раздел 7.1). Она изменяет каждую позицию двоичного разряда гА, в ячейке А которой содержится "1". Содержимое ячейки А - это двоичная константа (ai...ajt)2, где х - aix~ - • • • - является первообразным полиномом по модулю 2, как упоминалось выше. После выполнения программы (10) следующим двоичным разрядом генерируемой последовательности можно взять младший двоичный разряд слова X. Или же можно последовательно выбирать старший двоичный разряд X, если он больше подходит.

Рассмотрим, например, рис. 1, на котором иллюстрируется генерируемая последовательность для fc = 4 и СОДЕРЖИМОГО (А) = (0011)2. Это, конечно, необычно малое значение к. В столбце показано, что последовательность двоичных разрядов последовательности, а именно - 1101011110001001..., повторяется с длиной периода 2* - 1 = 15. Эта последовательность совершенно случайна, если принять во внимание, что она была сгенерирована только с четырьмя двоичными разрядами памяти. Чтобы убедиться в этом, рассмотрим примыкающие множества четырех двоичных разрядов в периоде, а именно - 1101, 1010, 0101, 1011, 0111, 1111, 1110, 1100, 1000, 0001, 0010, 0100, 1001, ООП, ОНО. Вообще говоря, каждое возможное примыкающее множество к двоичных разрядов однажды встречается в периоде, исключая множество всех нулей, так как длина периода равна 2*-1. Таким образом, примыкающие множества к двоичных разрядов совершенно независимы. В разделе 3.5 показано, что это очень сильный критерий случайности, когда к равняется, скажем, 30 или больше. Теоретические результаты, иллюстрирующие случайность этой последовательности, приведены в статье Р. К. Таусворта (R. С. Tausworthe, Math. Сотр. 19 (1965), 201-209).