Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 34
Текст из файла (страница 34)
Генератор, приведенный в строке П, имеет другой множитель, который специально выбран с плохими намерениями, как предложил Вотерман (%асегшап). Он гарантирует достаточно большое значение рз (см. упр. 11). Строка 10 интересна, поскольку указанный в ней генератор имеет большое значение рз при очень малом значении рз (см. упр. 8). Строка 11 табл. 1 — это воспоминание о старых добрых временах: данный генератор когда-то широко использовался, после того как его предложила О. Таусски (О. Тапээку) в начале 50-х годов.
Но компьютеры, для которых модуль равнялся примерно 2зэ, начали утрачивать популярность в конце 60-х и почти полностью пропали в 80-е годы, когда получили распространение машины с 32-разрядной арифметикой. Так, сравнительно малые размеры компьютерного слова были заменены сравнительно большими заботами. В строке 12 содержится, увы, генератор, который действительно использовался на таких машинах в последнее десятилетие (90-е годы) в научных компьютерных центрах мира. Его истинное имя — йай00 (похоже на егвпбошв — "случайный". — Прим.
ред.), и этого достаточно, чтобы вызвать испуг в глазах и спазмы в желудке у многих ученых, специализирующихся на компьютерах! Действительно, генератор определен следующим образом: Хе нечетное, Ха ы = (65539Х„) шоб 2з'. (37) Тнбли34а 1 ВЫБОРОЧНЫЕ РЕЗУЛЬТАТЫ ПРИМЕНЕНИЯ СПЕКТРАЛЬНОГО КРИТЕРИЯ а 1К и г "з г 14 г 15 г хв г Строка В упр. 20 показано, что 239 — подходящий модуль для спектрального критерия. Так как 9Մ— 6Л„+1+ Л' +3 = 0 (по модулю 23'), генератор ие удовлетворяет большинству трехмерных критериев случайности и его никогда не счедовало бы использовать.
Почти любой множитель 93 б (по модулю 8) был бы лучше. (Любопытный факт относительно ЕАй005.отмеченный Госпером (Собрег), состоит в том, что и4 = рз = рв = и? = 1'3 = рз = зг'1Г6. Следовательно, )43 равно эффективному значению 11.98.) Строки 13 и 14 — это множители Вороша-Нидеррейтера (Во!об)3-Н!05)езтег!ег) и Вотермана ( тта!егшап) для модуля 233. В строках 16 и 23 расположены генераторы ,Чаво ((атаих) и Йенсена (3апзВепз); параметры этих генераторов были найдены на компьютере, чтобы получить хороший множитель в смысле спектрального критерия, для которого рз принимает очень большое значение.
В строке 22 находится генератор с множителем, используемым при с = 0 и т = 243: он содержится в библиотеке компьютера С?ау Х-МР. В строке 26 содержится генератор, предложенный Хайиесом (Наупеб) (его превосходный множитель 6364136223846793003 настолько велик, что не поместился в столбце таблицы!). Генератор строки 10 предложен Дж.
Марсалья (к). Магэай))а) в качестве "кандидата на паллу*1ший множитель", 1 2 3 4 5 6 7 8 9 10 ы 12 13 !4 15 16 !7 18 19 20 21 22 23 24 25 26 27 28 29 23 21+ 1 213+! 314 Г592653 13? 3141592621 3!41592221 4219755981 4160984121 234 1 213,! 5 5'3 2'в+3 !812433253 1566083941 69069 1664525 314159269 62089911 16807 48271 40692 44485709377909 31167285 См. (38) См. (39) См. текст См.
текст 2-и-зво (гзг 5)-зоо 105+ 1 235 235 гвз 256 ! 013 1013 10'о 10'о 235 235 233 гзг гзг гзг гзг 231 231 231 — ! ! гзг 251 249 24в 243 См. (38) См, (39) 275 25?в 21вго 530 16642 34359738368 299?222016 274 4577114792 4293881050 10721093246 9183801602 8364058 33161685770 536936456 4326934538 4659748970 4243209856 4938916874 1432232969 !977289717 282475250 1990735345 !655838865 З.бх 1013 3.2х 10'4 2,4 х 1013 (231 - 1)г В.бх !О '" гвг+ ! !.Вх ю'гз 1,6 х !0414 530 16642 б 1026050 ЗО 1034718 276266 2595578 4615650 8364058 2925242 118 1462856 2079590 2072544 2322494 699290 !662317 408197 1433881 1403422 1180915002 411184!446 4,7 х 101' 1.4 х 10'г бм х 1013 428!084902 3.5х10",5 В бх10315 530 16642 4 27822 14 62454 97450 49362 16686 21476 113374 116 15082 44902 52804 63712 36985 48191 21682 47418 42475 1862426 17341ШО 1.9х103 643578623 4.1 х 103 2.2х 103 4 4 х 1033 1 х 1 Ого? 530 Ь3602 4 1!18 6 1776 3366 5868 6840 16712 !3070 116 4866 4652 6990 4092 3427 6101 4439 4404 6507 279928 306326 3!94548 12930027 45662836 1,8Х!03 2х !053 2 х 10 1"5 447 252 4 1118 542 2382 620 1344 1496 2256 116 906 662 242 !ОЗВ 1144 1462 895 1402 !435 26230 59278 1611610 837632 1846368 1862407 5х!03" В х !Огзт 1$ зт 1$ зз !$ из !8 из !б зз из из нз из из Верхиии граница из (40): 3.63 5.92 9.87 И.89 23.87 после компьютерных исследований для почти кубических решеток размерностью от 2 до 5.
Это предложение было сделано, в частности, потому, что множитель можно легко запомнить (см. книгу под редакцией с. к. зарембы [Арр)гсвг!опв ог" ь7шпьег 'ГЬеогу го Хшпегзса) Апа!увзв, 6111!ед Ьу Б. К. ЕагешЬа (ваези Ъог)с: Асадеш)с Ргевв, 1972), 275]). В строке 17 как множитель используется первсюбразный корень по модулю простого числа 23' — 1, В строке 18 приведен наилучший с точки зрения спектрального критерия первообразный корень для 23' — 1, найденный в исчерпывающем исследовании Дж.
С. Фишмана (С. 8. Р!ЯЬшап) и Л. Р. Мура 1П (Е. В. Мооге ГП; ЯАМ Х бей бгаа Сошриг, 7 (1986), 24-45. Похожий, но не менее выдающийся множитель 16807 = 7$ в строке 19 стал более часто использоваться для этого модуля„после того как его предложили Левис, Гудман и Миллер (см. работу Еен!в, Сообшап, апд М1йег в 1ВМ бувгешв Х 8 (1969), 136-146). Генератор с этим множителем является основным с 1971 года в популярной библиотеке программ 1МБЕ. Основная причина продолжительного использования а = 16807 состоит в том, что аз меньше модуля гн, поэтому операция ах шабаз может быть выполнена с высокой эффек- 4.5 4.5 4.5 7,0 7.0 7,0 1 7.5 !.3 1.0 15.7 10.0 7.4 4.0 зл !.9 16.0 10.0 8.0 16.0 9.0 8,3 16.7 10.7 ТД 16.5 11.1 7.0 11$ 11,5 7.2 17.$10.7 ЯА 14.5 3.4 3.4 16.0 10,2 6.9 16Л !ОД 7 7 16.0 10.5 7.8 16Л 10.6 8.0 15.2 9.9 7.6 15.4 10.3 7.8 14,0 9.3 7.2 !5.4 10.2 7.8 15.3 10.2 7.7 22.Я 15.1 !0.4 24,! 16.0 12.0 30.5 !9.4 ГЗА 31.0 20.2 14.6 31.5 21,3 16,0 31.0 16.0 15.5 288, 192.
144. 688. 458. 344. 4.5 4.4 7.0 4.0 1.0 1.0 5.1 5.1 1.3 1.0 $.4 4.5 5.9 5,6 6.3 4.6 6.4 5.2 7.0 5.3 6.8 5.6 34 ЗА 6.1 4.9 6.1 4.7 6,4 4.0 6,0 5.0 5,9 5.1 6,3 $.3 6.1 4.9 6.1 5,2 6.3 5.2 9,0 7.3 9.! 7.9 !0.8 10.3 1 1.В 9.8 12.7 10.4 16.4 1ОА 115, 95,9 275. 229. 2зз 5зз 0.01 2зз Зз~ 0 04 3Л4 2зз Ззз о.гт олз о,п 3.36 2.69 3.78 1.44 0.44 1.92 1.3$ 0.06 4.69 3.37 1.75 1.20 2.89 4.15 0.14 $44 2,95 0.07 3.03 0.61 1.85 3 !4 зз 44 3.16 !.73 0.26 3.4 1 2.92 2.32 3.10 2.91 3.20 3,61 ЗА5 4.66 2.!О 1.66 3.14 2.89 4.16 5.34 0,41 ОЛП 1.08 2.91 3.35 5.17 2А2 324 415 2АВ 2А2 0.25 3.60 3.92 5.27 1.65 0.29 З.ЯВ 3,14 1.49 0.44 1.50 3.68 4.52 бг 4ез Вгз 2.2Т 3.46 3.92 3.10 2.04 2.$5 0.34 4.62 4,66 2«з 54 з 0.01 0.21 1.81 1.29 0.07 О.ОВ 0.35 6.98 1.39 0.26 2.04 1.25 5.53 0.50 2.99 1.73 зз 0.02 2.02 0,89 !.81 0.35 5.01 0.02 !.31 1,3$ 1.69 3.60 7.13 7.52 3.22 1.73 ЗЛЗ 6.63 8.37 7.16 3.10 1,33 0.97 3.82 0.02 4.69 0.69 0,66 4.02 1.76 2 56 з4 2А9, 2.98 1.15 1.33 1 2 3 4 5 6 7 Я 9 1О 1) 12 13 14 1$ 16 17 18 19 20 21 22 23 24 25 26 27 28 29 тивностью на языках высокого уровня, использующих технику из упр, 3.2.1.1-9.
Однако такие малые множители имеют известные дефекты. С. К. Парк (Я. К. Раск) н К. В. Миллер (К. %. МШег) заметили, что эта же техника может быть применена к некоторым множителям, большим, чем ~/т, поэтому они попросили Дж. С. Фишмана найти наилучший "эффективно применимый" множитель из этого широкого класса. Результат поисков приводится в строке 20 (САСМ31 (1988), 1192-120Ц. В строке 21 содержится другой хороший множитель, предложенный П. Лекуером (см. Р. Ь'Есцуег, САСМ 31 (1988), 742-749, 774); этот генератор использует немного меньший простой модуль.
Если генераторы в строках 20 и 21 объединить с помощью вычитания, как показано в формуле 3.2.2-(15), то генерируемые числа (3„) будут удовлетворять рекуррентным соотношениям Х„+~ = 48271Х„шод (2~~ — 1), У„+~ = 40692У„шоб (2з' — 249), (38) (Х 1') ~(2зт Ц В упр. 32 показано, что разумно проверить (Я„) с помощью спектрального критерия для гп = (2м — 1)(2ээ — 249) и а = 1431853894371298687. (Это значение а удовлетворяет равенствам а шод (2з' — 1) = 48271 и а шос) (2э' — 249) = 40692.) Результат приведен в строке 24. Не следует особо заботиться о нижней грани значения пы так как иэ ) 1000. Длина периода генератора (38) равна (2з' — 2)(2зэ -250)/62 ш 7х 10ы. В строке 25 таблицы приведена последовательность Х = (271828183Л ~ — 314159269Л ) од (2з~ 1) (39) которая имеет длину периода (2э' — 1)з — 1, что легко показать, Она проверена с использованием обобщенного спектрального критерия в упр.
24, В последних трех строках табл. 1 содержатся генераторы, основанные на методах суммирования с переносом и вычитания с заимствованием. Они моделируют линейные конгруэнтные последовательности с крайне большими модулями (см. упр. 3.2.1.1-14). В строке 27 приведен генератор Хя = (Х -~ + 65430Хэ-з + Сч) щи 2э', С„+~ = ~(Хч ~ + 65430Х„з+ С„)/2~"~, который соответствует генератору Х„.~, -- (65430 2м+1)Х„щи (65430 2ю+2з' -1). Числа в таблице отвечают "супервеличинам" Хч — — (65430 ° 2 ' + 1) Хч ~ + 65430Хь-е + Сч лучше, чем величинам Х„, действительно вычисляемым и используемым как случайные числа.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
