Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 60
Текст из файла (страница 60)
Так как Л кратно Л| и Лэ, отсюда следует, что Л' является делителем Л. (Это заметил Алан Дж. Вотерман (А!ап С. %аеегшан).) также справедливы соотношения и+ ь — д„ш и+ л'+ й — д„»1 (по модулю л|) для всех болыпих п из-за различия Х„. Предположение об ограниченности (9 ) обеспечивает равенство д„ех = 9» + с для всех больших и, где с эз Л' (по модулю Л,) и (с( < -'Л|.
Но с должно равняться О, так как (9 ) ограничено. Значит, Л' ш 0 (по модулю Л|) и 9 ел = Ч для всех больших и. Отсюда следует, что Л' кратно Лэ и Л|, поэтому Л' = Л, За»ее»анке. Из ответа к упр. 3.2.1.2-4 сэедует, что, если (У ) — линейная конгруэнтная последовательность максимального периода по модулю т = 2", длина периода Лэ будет не больше 2' 1, когда Ь вЂ” степень 2. 16. Существует несколы(о методов доказательства. (1) Использование теории конечных полей. Рассмотрим поле, содержащее 2" элементов. Пусть б удовлетворяет соотношению б» = а|6~ ' + + аы Пусть 1(Ь(б ' + . + Ье) = Ьы где каждое Ь| равно нулю или единице, — линейная функция.
Если слово 1 в порождающем алгоритме имеет вид (Ь| Ьэ... Ьь)1 до выполнения (10) и еоеи Ь|б" ' + + Ьесе = б", то слово 1 после выполнения (10) будет иметь вид б"е(. Значит, последовательность будет иметь вид У(с") У(с "»') 1(с"е ) . ' и У(»е"+") ы УЫ" »е") = 1(о(Г+~ 1+. +аьс )=а УЫ ~~ |)+ +оеИ ). (2) Использование грубой силы пли элементарной изобретательности. Рассмотрим последовательность Х, и > О, 1 < „1 < Ь, удовлетворяюп|уЮ соОтнпщвниям Х(»ецэ ш ааХм (по модулю 2). Х(»ец| = Л»(зец+о|Х 1, 1 < у < Ь( Необходимо показать, что Х„ь ев о|Х(,|„+ ..
+ оеХ(„ыь для и > Ь. В самом деле, получаем, что Х, ш о|Х(„ц„+ + аьХ(„Ы„, когда 1 < у < Ь < и. Это очевидно для 1 = 1, так как Хш сн а|Х(„ц| + Х(»-цэ ш о|Л(„ц, + оаХ(»-эр + Х(»-Юэ и т. д. Для !' > 1 по индукции получим Х„ж Х!„+00 П вЂ” а. йХ„! щ ~~ а,ХШй! 00 Ю вЂ” о! ! ~ а!Х<„0, !<ю3й й<!<й о!(Хщ+й-!)О-!) ог-йЛЫ-!3!) !<(<й щ о ХЫ-йц + . + ойХс„-йй. Доказательство не зависит от того, как будут рассматриваться операции: по модулю 2 либо по мсщулю, равному любому простому числу.
17. (а) Когда последовательность закончится, (й — 1)-мерная строка (Х„э!,..., Х„ъй !) появится (гл + 1)-й раз. Для данной (!г — 1)-мерной строки ( Х,+й, ..,, Х,+у, !) существу- ет толъко т предшественников Х„поэтому один нз них дочи!си появиться при !. = О. (Ь) Так как строка размерности (й — 1) (О,..., 0) встречаетгл (ел+ 1) раз, каждый возмож- ный предшественник появится обвзателъно. Поэтому строка размерности й (а!,О,...,О) появляется для всех а!, 0 < а! < йп. Пусть 1 < з < й, и предположим, что доказано, что все строки размерности й (ай,...,а.,О„,О) появились в последовательности при а, эй О. По построению эта строка размерности й (ой,..., а,,О,...,О, р) не может появиться раньше строки (ай,..., а„О,...,О, р) лля 1 < р < ий.
Следовательно, строка размерности (й — 1) (ай,..., а„О,..., О) появилась о! Раз, и все га возможных предшественников также псмвнлись. Это означает, что строка (а,ай,...,а„О,...,О) появилась для 0 < о < йп. Доказательство завершается по пи!!унции. Результат тел!же следует из теоремы 2.3.4.21), если испе~ъзовать ориентированные графы из упр.2.3,4.2-23.
Множество дуг из(х!,,х,,О,,О) в (хэ„...,х„0,0,...,0), где х ф 0 и 1 < у < йг, образуют ориентированное поддерево, четко связанное с десятичными обозначениями Девея. 18. Третий из старших двоичных разрядов П,+! полностью определяется первым и тре- тьим двоичными разряламн У . Поэтому появляются только 32 из 64 возможных пар ((6У„), (6У„е!)). [Замечание.
Если бы использовались, скажем, 11-разрядные числа У„ж (,Хы,Хы й! .. Лм .~!о)м то последовательность была бм удовлетворительной для многих случаев применения. Если другие, имеющие более одного двоичного разряда, постоянные появятся в регистре А, то последовательность будет удовлетворять обобщенному спектраль- ному критерию. (См. упр. 3.3.4-24; необходимо проверяты'! при 1 = 36, 37, 36,....) 21. (Л Ъопг(ол МаМ, Яос.
21 (1946), 169-172.) Любая последовательность с длиной пери- ода гл — 1 без к последовательных нулей приводит к образованию последовательности й с длиной периода ийй, если вставить нули в подходящие места, как в упр. 7. Обрат. но, можно начинать с последовательности с длиной периода глй и удалять подходящие нули из периода, чтобы сформировать последовательность другого типа.
Назовем эти (пй,й)-последовательности последовательностями типа А и В. Предположения обеспечи- вают су-шествование (р, к)-последовательностей типа А для всех простых чисел р н всех й > 1. Таким образом, существуют последовательности (р, й) типа В для всех таких р н й. Чтобы получить последовательность (р', й) тица В, возьмем е = йг, где 4 — сте- пень р, а г не кратно р.
Начнем с (р,дгк)-последовательности типа А, а именно — с Хе, Хг, Хм,; тогда с помощью системы счисления с основанием р сгруппированные циф- Ры (Хо . - Хе-! )р, (Хе... Хы й)ю... образуют последовательность (р", гй) типа А, так как 4 и рй" — 1 — взаиыно простые числа и последовательность имеет период длиной ры — 1. .й Это приводит к получению (рэ, гк)-последовательности (У„) типа В, а Щ1'! ...У, !)рй, (У,1'„е!... Уз !)рй, ... являются (р"", й)-последовательностями типа В. Доказывается ана- логично, так как г и ре — взаимно простые числа.
ВИОЕИ 371 1Р ЕИТб 24 РРА Т+31,6 АРР Т,б ВТА 7+31,6 РЕО6 1 16Р ° "4 ЕИТ6 31 ВРА Т,б АРР Т+24,6 ВТА Т,б РЕС6 1 16Р в-4 ЕИТ6 бб 1Е 1ИР ь ! Сейчас цена равна всего (12+ в )в. [Подобное обращение на языке С используется в Тйе Яапйгг) СгарЬВазе (Меж Уогй: АСМ Ргевз, 1994), СЕ Р1,1Р,) Действительно, во многих случаях предпочтительней генерировать весь массив случайных чисел одновременно.
Более того, приведенный выше подход обязателен, когда случайность усиливается методом Люшера (1л зсЬег) (см. программы на алгоритмических языках С и ИНП'ВАИ в разделе 3.6). 2Т. Пусть з„= [АХ„/т). Лемма. После того как (Аг + 71 — 2)/2 последовательных значений 0 +'10ьы 20" ... (А — Ц О Чтобы получить (т, А)-последовательность типа В для произвольного т, можно объединять (р', й)-последовательности для каждой степени простого множителя т, используя китайскую теорему об остатках, но существует более простой метод. Пусть (Х„) — зто (г,й)-последовательность типа В и пусть (У„) — (э, А)-последовательность типа В, где г и з — взаимно простые числа.
Тогда (зХ + 1' ) является (гз, А)-последовательностью типа В. Простая равномерная конструкции, которая производит (2, Й)-последовательности для произвольного А, была открыта А. Лемпелем (А. 1.егоре!, 1ЕЕЕ Тгалв. С-19 (1970), 1204- 1209). 22. С помощью китайской теоремы об остатках можно найти константы ап..., аы имеющие желаемые вычеты по модулю, равному каждому простому делителю т. Если т =ркрт.. ро длина периода равна!сгп(р, — 1, ..., р, — 1).
В самом деле, можно поз ь лучить приемлемо длинный период для произвольного т (необязательно свободного от квадратов), как показано в упр. 11. 23. Вычитание может происходить быстрее суммирования (см. упр. 3.2.1.1-5); длина периода вс» еще равна 2' '(2м — 1) согласно упр. 30. Р. Брент (К, Вгепт) отметил, что при использовании чисел с плавающей точкой вычисления можно произвести точно в [О .. 1) (см. упр. 3.6-Щ, 24. Обратите последовательность. Другими словами, если У = У „, то Я = (2 -ьы— 2„ь) щоб2 = (Яв-им+ Ее а) шод2.
23. Эта идея поможет избежать большинства затрат времени на обращение к программам. Например, предположим, что программа А вызывается командой 1ИР ВАИРИ, где ВАИРИ $71 1Р РРА Т„б Программа А. ЕИТ6 66 1И 1ИР ° Цена использования таких случайных чисел составляет 14+ Тзу единиц времени. Но предположим, что мы обращаемся не к втой программе, а к программе получения случайных чисел ВИОЕИ; РЕС6 1; 162 ВИОЕИ;И!1 Т,б. появятся в последовательности (»„), для алгоритма Б булут выполняться неравенства Ъ'(!) < т/lс, 0 < у < х, а также У < т,%.
Доказательство. Пусть ߄— множество позиций 1, таких, что г(!) < т/х точно перед тем, как генерируется Л'„, н пусть ӄ— такой индекс, что»г(1„] +- Х„, Если / ф 8„ и,!» ж О, то Я»~ —ж Я 0 (! ) и / ь» > О; если же у б Я и Х = О, то Я»~ ы Я„и ,! ь~ = О. После Л + 2 последовательных нулей должно выполняться 0 б Я„и у„»» -- О. Тогда после "1 О»+'" должно выполняться (О, Ц С Я и !' +~ = О; после "2 0»" выполняется (О, 1, 2) С К, и !»» = 0; и т. д.
Следствие. Пусть ! = (х~ + 7х — 2)/2. Если Л > !(г', то либо алгоритм В обеспечивает длину периода Л, либо последовательность (Л„) плохо распределена Доказательство. Вероятность того, что любая данная схема .! длиной ! не появляется в случайной последовательносуи длиной Л, меньше, чем (1 — !» ')"д < ехр(-Л 'Л/!) < е следовательно, фиксированные схемы могут появляться. После того как это произойдет, дальнейшее поведение алгоритма В будет таким же каждый раз, когда он достигнет этой части периода.
(Когда /с > 4, то требуется Л > 10м, поэтому данный результат чисто академический, но возможны также меньшие границы.) 29. Следующий алгоритм в худшем случае осуществляет около х~ операций. Но среднее время выполнения операций намного меньше; возможно, О(!об 1) или даже О(1). Х1. Присвоить (ав,а»,...,а»)»- (хц.,.,х», т-1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
