AOP_Tom2 (1021737), страница 24
Текст из файла (страница 24)
(39) См. текст См, текст 2-м звг (232 5)-400 1ов+1 233 г" 233 256 1010 1010 !010 !Ого 233 233 226 гзг 232 гзг гзг гз! 231 — 1 231 231 1 231 249 246 246 с.. (зв) с ,(зд) 264 ~ гтв гзтв 2!зтв 530 16642 34359738368 29972220!б 274 4577114792 4293881050 !072!093248 9183801602 8364058 33161885770 536936458 4326934538 4659748970 4243209856 4938916874 1432232969 1977289717 282475250 1990735345 1655838865 5.
б х 10'" 3.2 х 10' 4 2.4х!0!в (гзг Вг В.В х 1О!в 262 ! 1 вх10мз го414 530 16642 б 1026050 30 1034718 276266 2595578 4615650 8364058 2925242 118 1462856 2079590 2072544 2122494 899290 1662317 40819Т 1433881 1403422 1160915002 4111841446 4.7 х 101! 1 4х 1012 6 4х10!2 4281084902 3.5 х 10114 В.бх10274 530 16642 4 27822 14 62454 97450 49362 16686 21476 113374 116 Ш0 82 44902 52804 63712 36985 48191 21682 4Т418 42475 1882426 17341510 1.дх 10' 643578623 4.1 х 106 2.2х100 4,.! х !Овв ! х !0202 030 15602 4 Ецв б 1776 3366 5868 6840 16712 130ТО 116 4866 4652 6990 4092 3427 6101 4439 4404 6507 279928 306326 3194548 12930027 45662836 1.8 х 106 2 х 1063 2 х 10163 447 гбг 4 1118 4 542 2382 820 1344 1496 2256 116 ООВ 662 242 шзв 1144 1462 895 1402 1438 гбгзо 59278 1611610 взтбзг 1846368 1862407 5х1037 Вх10'зт (е !е) Р2 Рз Р4 !и Ре Стреха !8 их !8 иа !8 ие !8 иа !8 ие ВерхнЯЯ граница из (40); 3.63 5.92 9.87 14.89 23.87 после компьютерных исследований для почти кубических решеток размерностью от 2 до 5.
Это предложение было сделано, в частности, потому, что множитель можно легко запомнить (см. книгу под редакцией С. К. Зарембы (Аррйсабопб оуХитбег ТИеогу го 7х'итег!са( Апа1уз!и, ей!ес( Ьу Б. К. ХагетЬа (Хе!н хог)с Асае(ет!с Рге68, 1972), 275]). В строке 17 как множитель используется первообразный корень по модулю простого чисиа 23' — 1. В строке 18 приведен наилучший с точки зрения спектрального критерия первообразный корень для 23' — 1, найденный в исчерпывающем исследовании Дж. С. Фишмана (С. Б.
Р!ВЬтап) и Л. Р. Мура П1 (1., В. Мооге П1); ЯАМ 2. Яс~'. акбаи Согприа Т (1986), 24 — 45. Похожий, но не менее выдающийся множитель !6807 = 7' в строке 19 стал более часто использоваться для этого модуля, после того как его предложили Левис, Гудман и Миллер (см. работу 1.ецчб, Соогйпап, апе( М!11ег в 1ВМ Яубсешэ Х. 8 (1969), 136 — 146). Генератор с этим множителем является основным с 1971 года в популярной библиотеке программ 1МВЕ. Основная причина продолжительного использования а = 16807 состоит в том, что ат меньше модуля т, поэтому операция ах тес(гп может быть выполнена с высокой эффек- 4.5 4.5 4.5 7.0 7.0 7.0 1 7.5 1.3 1.0 15.7 10.0 7.4 4.0 2,5 1.9 16.0 10.0 8.0 16.0 9.0 8.3 16.7 10.7 7.8 16.6 П .! 7.0 11 5 1!.5 7.2 17.5 !ОЛ 8.4 14.5 3.4 3.4 16.0 10.2 6.9 16.1 10.5 7.7 16.0 10.5 7.8 16,1 10.6 8,0 15.2 9.9 7.6 15.4 10.3 7.8 1 4.0 9.3 7.2 15.4 10.2 7.8 15.3 10.2 7.7 22.8 15.1 10.4 24.1 16.0 12.0 30.5 19.4 15.4 31.0 20.2 14.6 ЗК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 5.4 4.5 5.9 5.6 6.3 4.8 6.4 5.2 7.0 5.3 6.8 5 б 3,4 3.4 6.1 4.9 6.1 4.7 6.4 4.0 6.0 5.0 5.9 5.1 6.3 5.3 6.1 4 9 6.1 5.2 6.3 5.2 9.0 7.3 9.1 7.9 10.8 10.3 11.8 9.8 12.7 10.4 15.4 10.4 115. 95.9 275. 229. Зех 5е4 0 01 2ее Зее 0.04 3.1 4 2ее 2ее 0.27 0.13 0.11 3.36 2.69 3,78 1.44 0.44 1.92 1Д5 0.06 4.69 3.37 1.75 1.20 2.89 4.15 0.14 Ве" 2.95 0.07 3.03 0.61 1.85 3.14 ее 3.16 1.73 0.26 3.41 2.92 2.32 3.10 2,91 3,20 3.61 ЗЛ5 4.66 2.!О 1.66 3.14 2.89 4.18 5.34 0.41 0.51 1.08 2.91 3.35 5.17 2.42 3.24 4.15 2.48 2.42 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.27 3.46 3.92 3.10 2.04 2.85 0.34 4.62 4 бб 2еа 5ее ее О.О 1 0.21 1.81 1.29 007 008 0.35 6.98 1.39 0.28 2.04 1.25 5,53 0.50 2.99 1.73 еа 0.02 2.02 0.89 1.81 О.Зе 5,01 0.02 1.3! 1.35 1.69 3.60 7,13 7,52 3.22 1.73 3.15 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 256 е4 2.49, 2.98 1.15 1.33 1 2 3 4 5 б 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 тивностью на языках высокого уровня, использующих технику из упр.
3.2.1.1-9. Однако такие малые множители имеют известные дефекты. С. К. Парк (8. К. Раг!4) и К. В. Миллер (К. %. М1!!ег) заметили, что эта же техника может быть применена к некоторым множителям, большим, чем ~/т, поэтому они попросили Дж. С. !ришмана найти наилучший "эффективно применимыйп множитель из этого широкого класса. Результат поисков приводится в строке 20 (САСМ31 (1988), 1192 — 120Ц. В строке 21 содержится другой хороший множитель, предложенный П. Лекуером (см. Р.
Е'Еспуег, САСМ 31 (1988), 742-749, 774); этот генератор использует немного меньший простой модуль. Если генераторы в строках 20 и 21 объединить с помощью вычитания, как показано в формуле 3.2.2-(15), то генерируемые числа (Я„) будут удовлетворять рекуррентным соотношениям Хп4.1 — — 48271Хп шоб (22' — 1), Уп.11 = 406921'п пюп' (21' — 249), (38) Х„= (Хп - У.„) 6 (22! — Ц.
В упр. 32 показано, что разумно проверить (Я ) с помощью спектрального критерия для т = (22' — 1)(22' — 249) и а = 1431853894371298687. (Это значение а удовлетворяет равенствам а шос! (22' — 1) = 48271 и а шос! (22' — 249) = 40692.) Результат приведен в строке 24. Не следует особо заботиться о нижней грани значения 440, так как иэ > 1000. Длина периода генератора (38) ранна (22' — 2)(22' — 250)/62 е 7 х 10'0.
В строке 25 таблицы приведена последовательность Хп = (27182818ЗЛ'„1 — 314159269Лп 2) шо6 (22' — 1), (39) которая имеет длину периода (22' — 1)2 — 1, что легко показать. Она проверена с использованием обобщенного спектрального критерия в упр. 24. В последних трех строках табл. 1 содержатся генераторы, основанные на методах суммирования с переносом и вычитания с заимствованием. Они моделируют линейные конгруэнтные последовательности с крайне болыпими модулями (см. упр. 3.2.1.1-14).
В строке 27 приведен генератор Хп = (Лп 1+ 65430Хп 2+ С„) !по!!22', Си+1 — — '((Хп 1+ 65430Х„2+ Сп)/2~'), который соответствует генератору Хп+ ! —— (65430 22'+ 1) Хп шо6 (65430. 202+ 22' — 1). Числа в таблице отвечают исупервеличинамп Ап = (65430 2 +1)Хп-1+65430Л'и 2+Си лучше, чем величинам Хп, действительно вычисляемым и используемым как случайные числа. В строке 28 представлен более типичный генератор, основанный на методе вычитания с заимствованием !и = (Лп-10 11п — 24 — Сп) и!01! 2, Си+1 = (Хп-1О и- Хп-24 + Сп) но модифицированный так, что при генерировании 389 элементов последовательности используются только первые (или последние) 24.
Этот генератор называется ВА1!1,Бх и предложен мартином люшером (магг!и 1.йэсьег) и!иле того, как он прошел проверку такими строгими критериями, которые забраковали предыдущие генераторы (см. Сотригег РИуэ1сэ Соттип!сабопэ 79 (1994), 100-110). Подобная последовательность Х„= (Х„ю — Хь-ээ — С„) той(2" — 5), Сны = (Х„ээ < Л 4э+ С„], такая, что из 400 генерируемых чисел выбираются 43, приведена в строке 29. Она обсуждается в ответе к упр. 3.2.1,2 — 22. В обоих случаях элементы таблицы соответствуют спектральному критерию, примененному к числам Х„, которые имеют высокую точность, вместо того, чтобы соответствовать индивидуальным "цифрам" Х„, но большие значения р показывают, что процесс генерирования 389 или 400 случайных чисел для отбора 24 или 43 — это идеальный путь устранения смещения благодаря крайней простоте схемы генерирования.
Теоретические верхние грани для ро которые не могут быть превышены для любого т, приведены сразу под табл. 1. Известно, что для каждой решетки, на единицу объема которой приходится гп точек, выполняется неравенства 1/2 1/В (40) где П принимает соответствующие значения (4/3)'/э, 2'/э 2'/з 2э/ь (64/3) '/е, 4э/~ 2 (41) для 1 = 2, ..., 8. [См. упр. 9 и книги Дж. В.
С. Касселя (д. Ъ'. Б. Савэе1э, 1псгобисйоп Со 18е Сеошесгу оГг/итЬегэ (Вег1!и: Врг1пйег, 1959), 332); Дж. Х. Копией и Н. Дж. А. Слоан (3. Н. Сопиау апд 1ч. 3. А. 8)папе, БрИеге РасЫпйэ, йагбсеэ аЫ Сгопрэ (Хек Уогк: Врйпйег, 1988), 20).] Эти грани достигаются для решеток, порожденных векторами с произвольными действительными координатами. Например, оптимальная решетка для Г = 2 будет шестиугольной, порождается ана векторами длиной 2/~/Зтт, образующими две стороны равностороннего треугольника. Для размерности 3 оптимальная решетка порождена векторами 1'и Ую 1э, которые могут иметь вид (и, с, -с), (е, — с, е), ( — с, в, в), где с = 1/Г4т.
Л. К. Киллингбек провел исчерпывающие исследования множителей аэз1шад4, когда т = 2м. Он показал, что для множителя а = 2650845021 справедливы равенства из~ = 4938969760, иээ = 2646962, аз — — 68342, ил~ = 8778 и ив~ = 1506. Таким образом, он превосходит другие множители, приведенные в таблице для этого модуля. Действительно, замечательные значения рь (3.61, 4.20, 5.37, 8.85, 4.11) превышают все значения рю рэ, р4 и рь для всех модулей таблицы.
"г. Связь с критерием серий. В ряде значительных работ, опубликованных в 70-е годы, Гаральд Нидеррейтер (НагаЫ М1ес1егге1сег) показал, как проводить исследования г-мерных векторов (1) с помощью экспоненциальных сумм. Одним из основных результатов его теории было слелующее; он показал, что генератор случайных чисел проходит проверку с помощью критерия серий для нескольких измерений, если этот генератор выдерживает проверку спектральным критерием, даже когда вместо полного периода рассматривается балыпая его часть. Кратко рассмотрим этот интересный метод для линейной конгруэнтной последовательности (Хо,а,с,т) с длиной периода т.
Первое (в дальнейшем — необходимое) понятие — разброс в 1 измерениях, т. е. величина, которую определим как максимум разности между средним числом и реальным числом (-мерных векторов (х„,х„,.м...,х„+~ л), попадающих в гиперпрямоугольную область, по всем таким областям. Точнее, если (х„) — - последовательность целых чисел в области О < х„< т, определим (л) число (х„,..., х„и.~,) в Л для О < и < )у' объем Л Рн = швх Х ,л где Л вЂ” области вида (43) В = (Ьм,рл) ~ ал < рл < А, а~ < рл < А)' здесь а, и )11 — целые числа из областей О < а, < 31 < т для 1 < )' < й Объем В, очевидно, равен (Д вЂ” а,)... (Д вЂ” ал). Чтобы найти разброс Р,, окинем взглядом (О все эти множества В н найдем такое, у которого самое большее или самое меньшее число точек вида (хн, ..,,х„ел л). Верхняя грань разброса может быть найдена с помощью зкспоненциальных СУММ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
