Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 12
Текст из файла (страница 12)
Кюка апб М. Маишгюго, мыл. Сотар. 56 (199Ц, 817-821; Неплба, В151е, апб Сопграблег, !лп .1. могл Рлуз. сз (1992), 561-564. значений х„, лежащих строго между х„та и х„ы «см. упр. 2). ж.-м. норманд (д.-М. Коппапб), Г. Й, Герман (Н. 3. Неггшапп) и М. Квджар (М. На))аг) обнаружили небольшое смещение в числах, генерируемых (7), когда им понадобилось 10" случайных чисе41 для проводимых с высокой точностью обширных исследований метода Монте-Карло (л. Ягаггвггса) )г)гуясв 62 (1988), 441 — 446]; но при больших значениях )г смещение уменьшалось.
В табл. 1 приведено несколько пар чисел ((,й), для которых последовательность Х„= (Х„1+ Х„а) тод 2' имеет период длиной 2' 1(21 — 1). Случая, когда (1,9) = (30,127), казалось бы, достаточно для большинства применений, особенно в сочетании с другими, увеличивающими случайность, методами, которые мы обсудим ниже. Генератор случайных чисел во многом подобен сексу: когда он хорош — зто прекрасно, когда он плох, все равно приятно (Джордж Марсалья, 1984). Джордж Марсалья (Сотр.
Вой апс( Вгаггвбсв: Вутровгигп оп 1)ге 1псегГасе 16 (1984), 3-10) предложил заменить (7) на (7') Х„=-(Х.ае Л .ы)гног1пг, п>55, где гп кратно 4, а все числа от Ло до Ла„нечетны, но сравнимы с 1 (по модулю 4). Тогда второстепенные младшие разряды имеют период 255 — 1, в то время как старшие двоичные разряды более тщательно перемешаны, чем раньше, так как они существенно зависят от всех разрядов Хо 24 и Л„аа. В упр. 31 показано, что длина периода последовательности (7') лишь незначительно меньше длины периода последовательности.(7).
Генераторы последовательности Фибоначчи с запаздыванием успешно применялись во многих ситуациях с 1958 года. Таким образом, открытие в 90-е годы того, что они фактически провалились на крайне простом, незамысловатом критерии случайности, явилось шоком (см. упр. 3.3.2-31). Как кзбежать таких неприятностей, отбрасывая ненужные элементы последовательности, рассказывается в конце этого Ф раздела. Вместо рассмотрения исключительно аддитивных или исключительно мультипликативных последовательностей можно построить достаточно хороший генератор случайных чисел, используя всевозможные линейные комбинации Х„г, ..., Хп а для малых Й. В этом случае наилучший результат получается, когда модуль нт является болыпим прослгыаг числом; например, гп может быть выбрано так, чтобы оно было наибольшим простым числом, которое можно записать одним компьютерным словом (см.
табл. 4.5.4 — 2). Когда гп = р — простое число, то по теории конечных полей можно найти множители аг,..., аа, такие, что последовательность, определенцая соотношением Л„= (а1Х„1+ +аэЛ„ь) тодр, (8) будет иметь период длиной рь — 1. Здесь Хэ,..., Хь 1 могут быть выбраны произвольно, но так, чтобы все они не были нулями. (Частный случай, когда й = 1, соответствует мультипликативной конгруэнтной последовательности с уже известным простым модулем.) Константы а„..., аь в (8) обладают подходящими свойствами тогда и только тогда, когда полипом /(х) = х — а1х — ° — аэ э ь-1 (9) является первообразным полиномом по модулю р, что выполняется тогда и только тогда., когда корень этого полинома есть первообразиый элемент поля с р~ элементами (см.
упр. 4.6.2-16). Конечно, для достижения практических целей недостаточно простого факта суи4естввванил подходящих констант а„..., аь, дающих период длиной р" — 1. Необходимо быть в состоянии нацгпи их, ведь нельзя проверить все р~ возможностей, так как р имеет порядок длины слова компьютера. К счастью, есть точно р(р~ — 1)/к подходящих наборов (а„...,аэ), поэтому в известной степени существует хороший шанс натолкнуться на один из них после нескольких случайных попыток. Но также следует уметь быстро определять, будет ли (9) первообразным полнномом по модулю р.
Конечно, немыслимо генерировать до рэ — 1 элементов последовательности и ждать повторения! Методы проверки того, что полинам будет первообразным по модулю р, обсуждались Аланеном (А!апеп) и Кнутом (КппсЬ) в Яалхауа А26 (1964), 305-328. Можно использовать следующий критерий. Пусть г = (рл — 1)/(р — 1). !) (-1)ь 'аэ должен быть первообрвзным корнем по модулю р (см. раздел 3.2.1.2). 8) Полинам х" должен быть сравним с (-1)" 'аэ по модулим /(х) и р. ш) Степень хг/г щам/(х) (здесь используется арифметика полиномов по модулю р) должна быть положительной для каждого г — простого делителя ((.
Эффективный способ вычисления полинома х" щоб/(х) с использованием полиномиальной арифметики по модулю, заданному простым числом р, обсуждается в разделе 4.6.2. Для того чтобы довести до конца тест, необходимо знать разложение на простые множители числа г ж (р" — 1)/(р — 1), что и являетси ограничивающим фактором в вычислениях. г можно разложить на множители в приемлемый отрезок времени, когда й = 2, 3 и, возможно, 4, но большие значении й усложняют вычисления, когда р балыков.
Даже при и = 2 число "значащих случайных цифр", которое достигается при /г = 1, по существу, удваивается, так что большие значения й вряд ли понадобятся. Видоизмененный спектральный критерий (раздел 3.3.4) можно использовать для оценки последовательности чисел, генерируемых (8); см. упр. 3.3.4-24. Рассуждения, приведенные в этом разделе, показывают, что ив следовало бы делать очевидный выбор (а1 — — +1 или -1), когда встречается такал форма первообразного полинома. Лучше выбрать болыпие, совершенно "случайные" значения аэ,... „аы удовлетворяющие условиял», и проверить выбор с помощью спектрального крите. рви. Значительный объем вычислений приходится выполнять при возвадении в степень для нахождении аы..., аы Но все известные доводы указывают на то, что результатом будет весьма удовлетворительный источник случайных чисел.
Мы, по существу, добились случайности линейных конгруэнтных генераторов с Й-кратной точностью, используя только операции с простой точностью. Представляет интерес частный случай, когда р = 2. Иногда требуется генератор случайных чисел, вырабатывающий всего лишь случайную последовательность двоичных разрядов — нулей и единиц — вместо дробей, лежащих между нулем и единицей. Существует простой способ генерирования высокослучайных двоичных разрядов последовательности на бинарных компьютерах, основанный на манипулировании Й-разрядными словами. Начать следует с произвольного ненулевого двоичного слова Х. Затем необходимо вычислить следующий случайный бит последовательности, выполнив операции, которые приведены на языке компьютера, М1Х (см. упр.
16): 1ОА Х (Предположим, что переполнение сейчас "выключено".) АВО Х Перенестн влево один разряд. ЮМОРА о+2 Перейти к другой команде, если исходное значение высшего разряда было нулюь ХОЯ А Иначе — установить число с "исключающим пли". ЯТА Х 5 (10) Четвертая операция чисключающее илич существует почти на всех двоичных компьютерах (см.
упр. 2.5-28 и раздел 7.1). Она изменяет каждую позицию двоичного разряда гА, в ячейке А которой содержится "'1". Содержимое ячейки А — зто двоичная константа (а1...пь)м где хь — а1хь ' — ° — аь является первообразным полиномом по модулю 2, как упоминалось выше. После выполнения программы (10) следующим двоичным разрядом генерируемой последовательности можно взять младший двоичный разряд слова Х. Или же можно последовательно выбирать старший двоичный разряд Х, если он больше подходит. Рассмотрим, например, рис.
1, на котором иллюстрируется генерируемая последовательность для Й = 4 и СОДЕРЖИМОГО(А) = (0011)ю Это, конечно„необычно малое значение Й. В столбце показано, что последовательность двоичных разрядов последовательности, а именно — 1101011110001001..., повторяется с длиной периода 2" — 1 = 15. Эта последовательность совершенно случайна, если принять во внимание, что она была сгенерирована только с четырьмя двоичными разрядами памяти. Чтобы убедиться в зтолц рассмотрим примыкающие множества четырех двоичных разрядов в периоде, а именно — 1101, 1010, 0101, 1011., 0111, 1111, 1110, 1100., 1000, 0001, 0010, 0100, 1001, 0011, 0110.
Вообще говоря, каждое возможное примыкающее множество Й двоичных разрядов однажды встречается в периоде, исключая множество всех нулей, так как ддина периода равна 2ь — 1. Таким образом, примыкающие множества Й двоичных разрядов совершенно независимы. В разделе 3.5 показано, что зто очень сильный критерий случайности, когда Й равняется, скажем, 30 или больше, Теоретические результаты, иллюстрирующие случайность втой последовательности, приведены в статье Р. К. Таусвортв (К. С. ТапзюоггЬе, МаГЬ.
Сотр. 19 (1965), 201-209). !ом О1О! !шо о!!! )1!О 1111 110! !оо! ооо! оо!а о!оо гооо оаы 0110 !100 !он Рмс. 1. Последовательные значения компьютерного слова Е в бинарном методе, если предположить, что я = 4 в СОДЕРИИИОЕ(я) = (0011)ь Первообразный поливом по модулю 2 степени < 168 табулирован В. Станке (Ж. Б!а(тп(се, Май. Со!яр.
27 (1973), 977-980.) Когда й = 35, можем взять СОЕЕРЖИИРЕ(а) = (00000000000000000000000000000000101) з, но, принимая во внимание упр. 18 и 3.3,4-24„приходим к заключению, что лучше найти "случайные" константы, определяющие первообразный полинам по модулю 2. Предостережение. Кое-кто обманывается, полагая, что техника случайного поразрядного генерирования может использоваться для генерирования случайных дробей, которые занимают целое слово (ЛоХ!... Х1-1)ю (Х!Хь!.! ° Хы-1)м Но на самом деле это скудный источник случайных дробей, даже несмотря на то, что отдельный двоичный разряд совершенно случаен.
В упр. 18 обьясняется, почему так происходит. Адлитивный генератор (7) Митчела (М1!сЬе!!) н Мура (Мооге) в основном базируется на концепции первообразных полиномов: полипом хы + хы + 1 является первообразным, а табл. 1 — - это, по существу, таблица определенных первообразных трехчленов по модулю 2. Почти идентичный генератор независимо от 51итчела и Мура открыли в 1971 году Т. Ж. Левис (Т. О. 1еъ)э) и В. Г.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
