1011 0101 1010 GUI 1110 nil 1101 1001 0001 0010 0100

Jg°° Рис. 1. Последовательные значения компьютерного слова X в бинар-

0110 ном методе, если предположить, что к = 4 и СОДЕРЖИМОЕ (А) = (0011)2.

1100 1011

Первообразный полином по модулю 2 степени < 168 табулирован В. Станке (W. Stalinke, Math. Сотр. 27 (1973), 977-980.) Когда fc = 35, можем взять

СОДЕРЖИМОЕ (А) = (00000000000000000000000000000000101)2,

но, принимая во внимание упр. 18 и 3.3.4-24, приходим к заключению, что лучше найти "случайные" константы, определяющие первообразный полином по модулю 2.

Предостережение. Кое-кто обманывается, полагая, что техника случайного поразрядного генерирования может использоваться для генерирования случайных дробей, которые занимают целое слово {XqXi ... Xk-i)2, {XXic+i... X2k-i)2, - Но на самом деле это скудный источник случайных дробей, даже несмотря на то, что отдельный двоичный разряд совершенно случаен. В упр. 18 объясняется, почему так происходит.

Аддитивный генератор (7) Митчела (Mitchell) и Мура (Moore) в основном базируется на концепции первообразных полиномов: полином х + х* -Ь 1 является первообразным, а табл. 1 - это, по существу, таблица определенных первообразных трехчленов по модулю 2. Почти идентичный генератор независимо от Митчела и Мура открыли в 1971 год Т. Ж. Левис (Т. G. Lewis) и В. Г. Пэйн (W. Н. Payne) [JACM 20 (1973), 456-468], но они использовали операцию "исключающее или" вместо суммирования. Это делает длину периода равной точно 2 - 1. Каждая позиция двоичного разряда в последовательности Левиса и Пэйна пробегает ту же периодическую последовательность, но имеет собственную начальную позицию. Опыт показал, что (7) дает лучшие результаты.

Мы сейчас увидим, что последовательности с О < Х„ < m и периодом т* - 1 могут быть построены без больших усилий, где Х„ - подходящая функция от Хп-\,...,Хп-к и m - простое число. Наибольший возможный период для любой последовательности, определенной соотношением вида

Xn = f{Xn-u-..,Xn-k), 0<X„<m, (11)

как легко видеть, равен т*. М. Г. Мартин (М. Н. Martin) [Bull. Amer. Math. Soc. 40 (1934), 859-864] первым показал, что для всех m и fc существуют функции, позволяющие достичь максимального периода. Его метод можно легко сформулировать (упр. 17) и достаточно эффективно запрограммировать (см. упр. 29), но он непригоден для генерирования случайных чисел, потому что изменение значений Х„-1 + + Хп-к - очень медленный процесс: все строки размерностью к встречаются, но в не совсем случайном порядке. Лучший класс функций /,

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

Для генерирования случайных чисел предложено множество других схем. Наиболее интересным из этих альтернативных методов является, возможно, обратная конгруэнтная последовательность, предложенная Эйченауэром (Eichenauer) и Лехном (Lehn) [Statistische Hefte 27 (1986), 315-326]:

X„+i = (aX-i+c)modp. (12)

Здесь p - простое число, Х„ принимает значения из множества {0,1,..., р - 1, оо}, а обращение определено как 0"" = оо, оо~ = 0. В других случаях Х~Х = 1 (по модулю р). Так как О всегда следзет за оо, а затем за с в этой последовательности, можно было бы просто определить = О для удобства реализации, но теория является цельной и естественной, когда 0"" = оо. Существуют эффективные алгоритмы, которые можно реализовать на вычислительных машинах, пригодные для вычислений Х~ (по модулю р) (см., например, упр. 4.5.2-39). К несчастью, однако, операций, используемых в этих алгоритмах, в большинстве компьютеров нет. В упр. 35 показано, как много выборов а и с приводят к максимальному периоду длиной р -Ь 1. В упр. 37 продемонстрированы наиболее важные свойства: обратная конгруэнтная последовательность совершенно лишена решетчатой структуры, что характерно для линейных конгруэнтных последовательностей.

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

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

Допустим, имеются последовательности Xo,Xi,... iiYo,Yi,... случайных чисел, лежащих между О и m - 1 и предпочтительно сгенерированных двумя различными методами. Тогда можно, например, использовать одну случайную последовательность для изменения порядка элементов другой, как предложили М. Д. Мак-Дарен (М. D. MacLaren) и Дж. Марсалья (G. Marsaglia) [JACM 12 (1965), 83-89; см. также работу Марсалья и Брея (Bray), CACM 11 (1968), 757-759].

Алгоритм М (Рандомизация перемешиванием). Если заданы методы генерирования двух последовательностей (А„) и (У„), этот алгоритм будет последовательно генерировать элементы "значительно более случайной" последовательности. Воспользуемся вспомогательной таблицей V[0], V[l], V[k - 1], где fc - некоторое число, для удобства обычно выбираемое приблизительно равным 100. Вначале У-таблица заполняется первыми к значениями Х-последовательности.

Ml. [Генерирование X,Y.] Положим X и Y равными следующим членам последовательностей (Хп) и (Yn) соответственно.

М2. [Выбор j.] Присвоим j <r- [kY/mj, где тп - модуль, используемый в последовательности (Yn), т. е. j - случайная величина, определяемая Y, О < j < к.

МЗ. [Замена.] Выведем V[j], а затем присвоим V[j] <- X.

Предположим, например, что алгоритм М применяется к таким двум последовательностям при fc = 64:

Ло = 5772156649, Xn+i = (3141592653Л„ + 2718281829) mod 2 Ус = 1781072418, У„+1 = (2718281829У„ + 3141592653) mod 2=

35 (13)

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

В упр. 15 показано, что в ситуациях, представляющих наибольший практический интерес, длина периода последовательности, которая получается при реализации алгоритма М, равна наименьшему общему кратному длин периодов (Л„) и (Yn). В частности, если отбросить значение О, когда оно встречается в У-последовательно-сти, так что (Yn) имеет период длиной 2 -1, то числа, генерируемые алгоритмом М из рекуррентных соотношений (13), будут иметь период длиной 2"° - 2. (См. работу Дж. Артура Гринвуда [J. Arthur Greenwood, Сотр. Sci. and Statistics: Symp. on the Interface 9 (1976), 222].)

Однако существует еще лучший путь перемешивания элементов последовательности, открытый Картером Бейсом (Carter Bays) и С. Д. /1архамом (S. D. Durham) [ACM Trans. Math. Software 2 (1976), 59-64]. Хотя их подход и появился для того, чтобы несколько упростить алгоритм М, неожиданно оказалось, что он может дать лучшие результаты, чем алгоритм М, даже несмотря на то, что на входе он требует только одну последовательность (Л„) вместо двух.

Алгоритм В [Рандомизация перемешиванием). Если задан метод генерирования последовательности (Л„), этот алгоритм будет последовательно выводить элементы "значительно более случайной" последовательности, используя вспомогательную таблицу У[0], V[l], ..., y[fc-1], как и в алгоритме М. Вначале У-таблица заполняется первыми к значениями Л-последовательности, а вспомогательную переменную У положим равной fc + 1-му значению.

81. [Выбор j.] Присвоим j <- [kY/m\, где т - модуль, используемый в последовательности (Хп); т. е. j - это случайная величина, определяемая У, О < j < fc.

82. [Замена.] Выведем V[j], присвоим V[j] X, выведем V[j] и установим V[j] следующим членом последовательности (Л„).

Желание почувствовать различие между алгоритмами М и В побудит читателя заняться упр. 3 и 5.

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