v) (/(0), /(1),..., /(m - 1)) - это перестановка последовательности (0,1,..., m - 1) тогда и только тогда, когда (жо,Xi,... ,Xm-i) представляет собой обратную перестановку к той перестановке, которая в разделе 1.3.3 названа необычным соответствием.

vi) Хо = xi тогда и только тогда, когда (Ж],..., Жщ-х) представляет собой ориентированное дерево, построенное в упр. 2.3.4.4-18, с f{x) порождающим х.

3.2. ГЕНЕРИРОВАНИЕ РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ СЛУЧАЙНЫХ ЧИСЕЛ

В этом разделе будут рассмотрены методы генерирования последовательности случайных дробей, т. е. случайных действительных чисел Un, равномерно распределенных между нулем и единицей (на интервале [0,1]. Так как компьютер может представлять действительные числа только с определенной точностью, мы будем генерировать целое число ЛГ„ между нулем и некоторым числом т: дробь

Un = XJm

будет, следовательно, лежать между нулем и единицей. Обычно т выбирают равным размеру слова в компьютере. (В этой книге размером слова {word size) автор называет число где b - основание системы счисления, используемой в компьютере, а е - числоразрядов машины. - Прим. ред.) Поэтому Х„ можно по традиции рассматривать как целое число, занимающее все компьютерное слово, с точкой, которая отделяет целую часть числа от дробной, стоящей в правом конце слова, SiUn - если хотите, как содержание того же слова с разделяющей точкой, стоящей в левом конце слова.

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

В настоящее время наиболее популярными генераторами случайных чисел являются генераторы, в которых используется следующая схема, предложенная Д. Г. Лехме-ром (D. Н. Lehmer) в 1949 году [см. Ргос. 2nd Symp. on Large-Scale Digital Calculating Machinary (Cambridge, Mass.: Harvard University Press, 1951, 141-146)]. Выберем четыре "волшебных числа":

m, модуль; О < m;

а, множитель; О < а < т; . .

с, приращение; О < с < т;

Хо, начальное значение; О < ЛГо < т.

Затем получим желаемую последовательность случайных чисел (Х„), полагая

Хп+1 = {аХ„ + с) mod m, n > 0. (2)

Эта последовательность называется линейной конгруэнтной последовательностью. Получение остатков по модулю т отчасти напоминает предопределенность, когда шарик попадает в ячейку крутящегося колеса рулетки. Например, для m = 10 и Ло = а = с = 7 получим последовательность

7,6,9,0,7,6,9,0,.... (3)

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

В примере (3) иллюстрируется тот факт, что конгруэнтная последовательность всегда образует петли, т. е. обязательно существует цикл, повторяющийся бесконечное число раз. Это свойство является общим для всех последовательностей вида Хп+1 = f{Xn), где / преобразует конечное множество само в себя (см. упр. 3.1-6).

Повторяющиеся циклы называются периодами; длина периода последовательности (3) равна 4. Безусловно, последовательности, которые мы будем использовать, имеют относительно длинный период.

Заслуживает внимания счучай, когда с = О, так как генерируемые числа будут иметь меньший период, чем при с 7 0. Мы убедимся в дальнейшем, что ограничение с = О уменьшает длину периода последовательности, хотя при этом все еще возможно сделать период достаточно длинным. В оригинальном методе, предложенном Д. Г. Лехмером, с выбиралось равным нулю, хотя он и допускал случай, когда с О, как один из возможных. Тот факт, что условие с О может приводить к появлению более длинных периодов, был установлен В. Е. Томсоном (W. Е. Thomson) [Сотр. J. 1 р. 83, 86] и независимо от него А. Ротенбергом (А. Rotenberg) [JACM 7 (1960), 75-77]. Многие авторы называют линейную конгруэнтную последовательность при с = О мультипликативным конгруэнтным методом, а при с О - смешанным конгруэнтным методом. Буквы т, а, с и ЛГо буд>т использованы в этой главе в том смысле, в каком они вводились раньше. То же самое относится и к константе

6 = а - 1, (4)

которая вводится для упрощения многих наших формул.

Можно сразу отбросить случай, когда а = 1, при котором последовательность Хп представима в виде Х„ = (Ло + по) mod т и ведет себя явно не как случайная последовательность. Случай, когда а = О, даже хуже предыдущего. Следовательно, для практических целей предполагаем, что

а>2, Ь>1. (5)

Сейчас можно обобщить формулу (2)

Хп+к = {аХп + {а - 1)с/Ь) mod m, к>0, п>0, (6)

где (п + к)-й член выражается непосредственно через п-й. (Случай, когда п = О, в этом уравнении также достоин внимания.) Из (4) следует, что подпоследовательность, содержащая каждый к-й член последовательности (А„), является также линейной конгруэнтной последовательностью, множитель которой равен а* mod rn и приращение равно ((а* - 1)с/Ь) mod т. Важным следствием из (6) является то, что общая последовательность, определенная с помощью а, с и ЛГо, может быть очень просто выражена в терминах специального случая, когда с = 1 и ЛГо = 0. Пусть

Уо = О, Yn+i = {aYn + 1) mod т. (7)

В соответствии с (6) получим Yk = (а* - 1)/Ь (по модулю тп). Значит, последовательность, определенная в (2), будет имеет вид

Хп = (AYn + ЛГо) mod т, где А = (ЛГоЬ + с) mod т. (8)

УПРАЖНЕНИЯ

1. [10] в примере (3) показана ситуация, когда 4 = Хо, так что последовательность начинается сначала. Приведите пример линейной конгруэнтной последовательности при т = 10, для которой число Хо никогда снова не появится. ► 2. [М20] Покажите, что если а и m взаимно простые, то Хо всегда появится в периоде.