Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 13
Текст из файла (страница 13)
Пэйн (%. Н. Рауле) (эАСМ 20 (1973), 456-468), но они использовали операцию "исключающее или" вместо суммирования. Это делает длину пернода равной точно 2ээ — 1. Каждая позиция двоичного разряда в последовательности Левиса и Пэйна пробегает ту же периодическую последовательность, но имеет собственную начальную позицию. Опыт показал, что (7) дает лучшие результаты.
Мы сейчас увидим, что последовательности с О < Л„< т и периодом гп~' — 1 могут быть построены без больших усилий, где Մ— подходящая функция от Х 1,..., Хь я и гл — простое число. Наибольший возможный период для любой последовательности, определенной соотношением вида Л„= 7'(Х„1,..., Ха Я), 0 < Х„< т, (11) как легко видеть, равен тп". М.
Г. Мартин (М. Н. !Маг!(п) (Ви1). А!пег. МаНь Кос. 40 (1934), 859-864] первым показал, что для всех !и и й существуют функции, позволяющие достичь максимального периода. Его метод можно легко сформулировать (упр. 17) и достаточно эффективно запрограммировать (см. упр. 29), но он непригоден для генерирования случайных чисел, потому что изменение значений Х„.! + + Ха я — очень медленный процесс: все строки размерностью й встречалотся, но в не совсем случайном порядке. Лучший класс функций г, дающих максимальный период т~, рассмотрен в упр.
21. Подобные программы, вообще говоря, не так эффективны для генератора случайных чисел, как друтие уже описанные методы, но, когда речь идет о периоде в целом, они все-таки производят достаточно случайные последовательности. Для генерирования случайных чисел предложено множество других схем. Наиболее интересным из этих альтернативных методов является, возможно, обратнал кангруэнтная последовательность, предложенная Эйченаузром (Е1сЬепацег) и Лехном (1 еЬп) [Вгаггзг)зсЬе Нейе 27 (1986), 315 — 326]: (12) Х„+~ — — (аЛ„'+ с) щод р.
Здесь р — простое число, Х„принимает значения из множества (О, 1,..., р — 1, оо), а обращение определено как 0 ' = оо, оо ' = О. В других случаях Х 'Х = 1 (по модулю р). Так как О всегда следует за оо, а затем за с в этой последовательности, можно было бы просто определить 0 ' = 0 для удобства реализации, но теория является цельной и естественной, когда 0 ' = оо. Существуют эффективные алгоритмы, которые можно реализовать на вычислительных машинах, пригодные для вычислений Х ' (по модулю р) (см., например, упр. 4.5.2-39). К несчастью, однако, операций, используемых в этих алгоритмах, в большинстве колшьютеров нет.
В упр. 35 показано, как много выборов а и с приводят к максимальному периоду длиной р + 1. В упр. 37 продемонстрированы наиболее важные свойства: обратная конгруэнтная последовательность совершенно лишена решетчатой структуры, что характерно для линейных конгрузнтных последовательностей. Другой важный класс методов связан с комбинацией генераторов случайных чисел.
Всегда найдутся сторонники того, что линейные конгрузнтные, алдитивные и другие методы слишком просты лля того, чтобы давать достаточно случайную последовательность, и невозможно будет доказать, что такой скептицизм необоснован. Может быть, онн в самом деле правы, так что совершенно бесполезно обсуждать этот вопрос.
Существует достаточно эффективный способ объединения двух последовательностей в третью. которая была бы настолько случайной, что удовлетворяла бы всех, кроме совершенно убежденных скептиков. Допустим, имеются последовательности Хо, Хг,... и 1'о, 1'г,...
случайных чисел, лежащих между 0 и т — 1 и предпочтительно сгенерированных двумя различными методами. Тогда можно, например, использовать одну случайную последовательность для изменения порядка элементов другой, как предложили М. Д. Мак-Нарев (М. Р. Мас1 агеп) и Дж. Марсалья (С. Магзай!(а) [дАСМ 12 (1965), 83 89: см. также работу Мярсалья и Брея (Вгау), САСМ 11 (1968), 757-759]. Алгоритм М (Раидомизацил пергмсшиааиием). Если заданы методы генерирования двух последовательностей (Х„) и (У„), этот алгоритм будет последовательно генерировать элементы "значительно более случайной" последовательности.
Воспользуемся вспомогательной таблицей 1'[О], 1г[1], ..., 1'[й — 1], где й -- некоторое число, для удобства обычно выбираемое приблизительно равным 100. Вначале К-таблица заполняется первыми Й значениями Х-последовательности. М1. [Генерирование Х, 11] Положим Х н У равными следующим членам последовательностей (Х ) и (1„) соответственно. МЗ. [Выбор 7.] Присвоим у <- [И'Тт], где т — модуль, используемый в последовательности (У„), т. е, 7' — случайная величина, определяемая У, 0 <,у ( а, МЗ. [Замена.] Выведем И[7], а затем присвоим И[Я Х.
! Предположим, например, чта алгоритм М применяется к таким двум последовательностям при Й = 64: Лв = 5772156649, Х„э.1 = (3141592653Х„+ 2718281829) шод 2ы; 1а = 1781072418 1'а+1 = (27182818291'ч+ 3141592653) шоб 2 (13) Интуиция подсказывает, что последовательность, полученная в результате реализации алгоритма М (13), удовлетворяет любым требованиям случайности, которые предьявляются к генерируемым на компьютере последовательностям, поскольку зависимость между соседними выходными элементами почти полностью исключена, Более того„время генерирования этой последовательности лишь незначительно превышает удвоенное время, необходимое для генерирования последовательности (Х„). В упр.
1о показано, что в ситуациях, представляющих наибольший практический интерес, длина периода последовательности, которая получается при реализации алгоритма М, равна наименьшему общему кратному длин периодов (Л'„) и (1;,). В частности, если отбросить значение О, когда оно встречается в У-последовательности, так что (К,) имеет период длиной Зээ -1, то числа, генерируемые алгоритмом М нз рекуррентных соотнон1еннй (13), будут иметь период длиной 2го — 2ээ. (См.
работу Дж. Артура Гринвуда [3. Агйиг Огеептгоод, Согпр. Ясй апг( агаг!эВсв: Яушр. оп йе ГнгегГасе 9 (1976), 222].) Однако существует еще лучший путь перемешивання элементов последовательности. открытый Картером Вейсом (Саггш Вауэ) и С. Д. Дархамом (8. Р. Рпг)шш) [АСМ Тгапэ. Май. Яойваге 2 (1976), 59-64]. Хотя их подход и появился для того, чтобы несколько упростить алгоритм М, неожиданно оказалось, что он может дать лучшие результаты, чем алгоритм М, даже несмотря на то, чта на входе он требует талька одну последовательность (Х„) вместо двух.
Алгоритм В (Ракдомиэацил перемсшиввнием). Если задан метод генерирования последовательности (Х„), этот алгоритм будет последовательно выводить элементы "значительно более случайной" последовательности, используя вспомогательную таблицу г [0]„1 "[1], ..., Ик — 1], как и в алгоритме М. Вначале 1'-таблица заполняется первыми к значениями Х-последовательности, а вспомогательную переменную 1' положим равной Й + 1-му значению. В1. (Выбор 7'.] Присвоим 7' <- [И'7'т], где т — модуль, используемый в последователыюсти (Хв); т.
е. у — зто случайная величина., определяемая 1', 0 < 7 ( в, В2. [Замена.] Выведем Цу], присвоим Цу] +- Х, выведем 1:[Я и установим 1'[Я следующим членом последовательности (Л„). $ Желание почувствовать различие между алгоритмами М н В побудит читателя заняться упр. 3 и 5. На компьютере 81Х можно реализовать алгоритм В, взяв к равным размеру байта и выполнив вычисления в соответствии со следующей простой программой генерирования случайных чисел. Юб У(1: 1) у э- старший разряд байта У.
1.ПА Х гй +- Х 19СА 1 (См. упр. 3.2.1,1-1.) ИШ. А гХ+- Х эь (14) БТХ Х "и+- в+ 1." ЮА У,б 87А у 1 е- М[)). йтХ 9„6 Р(У)+-Х„. Выход появляется в регистре А. Заметим, что алгоритм В требует всего четыре дополнительные операции для генерирования числа. Ф, Гебхардт (Г. СеЬЬапЬ) [Масй.
Сотр. 21 (1967), 708-709) нашел, что удовлетворительная случайная последовательность порождается алгоритмом М, даже когда он применяется к такой неслучайной последовательности, как последовательность Фибоначчи, с Х„= Гз„щи щ и У' = Ея„э~ шод щ. Однако для алгоритма М также возможно получение последовательности, менее случайной, чем исходная последовательность, если (Х„) н (1'„) строго зависимы, как в упр.
3. Такие проблемы, кажется, не возникают с алгоритмом В. Поскольку алгоритм В не делает никакую последовательность менее случайной и очень мала цена увеличения случайности, он может быть рекомендован к использованию с любым другим генератором случайных чисел. Однако методы перемешнвания имеют "врожденный дефект" Они изменяют порядок следования генерируемых чисел, но не сами числа. В большинстве случаев порядок следования является решающим фактором, но, если генератор случайных чисел не удовлетворяет "критерию промежутков между днями роясдений", обсуждаемому в разделе 3.3.2, нли критерию случайных блужданий из упр. 3.3.2-31, то положение после перемешивания не улучшится.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
