AOP_Tom2 (1021737), страница 168
Текст из файла (страница 168)
Выше был рассмотрен только частный случай для д(х) = 1. Но обе части этого сравнения можно умножить на полинам Хенселя Ь(х) и получить, что 1 — х = 0 по модулям /(х) и р'. л Замечание, Более "элементарное" доказательство результата в (с) можно получить без помощи производящих функций, если использовать метод, аналогичный примененному в ответе к упр. 8. Если Ах+ = А + р'В» для и = г, г + 1, ..., г+ Ь вЂ” 1 и некоторых целых чисел В„, то такое же соотношение имеет место для всех и > г, если определить В +ыВ,+ьап...
заданным рекуррентным соотношением. Так как полученная последовательность для В„является линейной комбинацией смещений последовательности А„, получим Вхэ„ш В (по модулю р') для всех достаточно больших значений и. Теперь Л(р'т') должно быть кратным Л = Л(р'). Для всех достаточно больших и справедли- вы соотношения А»е!! = А + р'(В + В»»! + В»чю + + В +О-!Ы) = А» + ур'В» (по модулю рм) при 1' = 1,2,3,,... Никакией последовательных В„не кратны р, отсюда немедленно следуют соотношения Л(р" ') = рЛ(р') ф Л(р'еэ) прн е > 2.
Необходимо еще доказать, что Л(р'т ) ~ рЛ(р'), когда р нечетно и е = 1. Положим Вле = В„+ рС„ и заметим, что С»»! еэ С„(по модулю р), когда и достаточно велико. Тогда А ер ьз А» + р (В„+ (г!) С„) (по модулю рз), и доказательство окончено. Историю решения этой задачи можно найти в работе Моргана Варда (Могбап Руагс), Тгаоя. Ашег. Ма!Ь.
Яос. 36 (1933), 600-628); см. также работу Д. В. Робинсона (П. Ч~. НоЬ|пеоп, АММ 73 (1966), 619-621). 12. Длина периода по модулю 2 не может быть больше 4. Длина периода по модулю 2'+ ч.! не может быть больше удвоенной длины максимального периода шоб 2'. Это следует из предыдущего упражнения. Поэтому длина максимального возможного периода равна 2'»'. Она достигается, например, в тривиальном случае при а = О, Ь = с = 1. 13, 14. Очевидно, что 2'„ьх = с„, поэтому Л' является делителем Л. Пусть наименьшее общее кратное Л' и Л! равно Л'„а Л! определяется аналогично, Справедливы соотношения Х» + У вЂ” = Я!! = Я»»! = Х„+ У„ех, поэтому Л! кратно Ль Аналогично можно показать, что Л~э кратно Л!.
Это дает желаемый результат. (Он является "наилучшим из возл!ожных» в том смысле, что последовательности, для которых Л' = Ле. могут быть построены так же, как по<шедовательности, для которых Л' = Л.) 16. Алгоритм М генерирует (Х„чю У„) на шаге М1 и дает на выходе о» = Х»е! ш на !ваге МЗ для всех достаточно больших и. Таким обрезом, (Я») имеет период ллиной Л', где ! Л вЂ” наименьшее положительное целое число, такое, что Х»еь-г„= Л»е! еь-ы,„, тля всех больших и. Так как Л кратно Л! и Лэ, отсюда следует, что Л' является делителем Л.
(Это заметил Алан Дж. Вотерман (А!ап С. ЪЧа!егшап).) Также справедливы соотношения и+ Ь вЂ” д„= и+ Л + Ь вЂ” й„е! (по модулю Л!) для всех больших и из-за разли гня Х . Предпачожение об ограниченности (д») обеспечивает равенство 9»ех — — 9 + с для всех больших п, где с вз Л' (по модулю Л,) и (с( < -'Л! Но с должно равняться О, так как (д ) ограничено. Значит, Л ш 0 (по модулю Л!) и 9„,.! = 9 для всех больших и. Отсюда следует, что Л' кратно Л! и Л!, поэтому Л' = Л. Замечанье. Из ответа к упр. 3.2.1.2- 4 следует, что, если (У„) -- линейная конгруэнтная последовательность максимального периода по лшдулю т = 2', длина периода Лэ будет не больше 2', когда й — степень 2.
16. Существует несколько методов доказательства. (1) Использование теории конечных нолей Рассмотрим поле, содержащее 2" элементов. Пусть б удовлетворяет соотношению б = а!б + . + аь, Пусть ь ! — ! /(Ь|б" ' + . + Ь!) = Ьы где каждое Ь, равно нулю или единице, — линейная функция. Если слово 1 в порождающем алгоритме имеет вид (Ь|Ьэ... Ьь)! до выполнения (10) и если Ь|б~ ' + + Ьгб~ = б", то слово 1 погле выполнения (10) будет иметь вид б"'ь'.
Значит, последовательность будет иметь вид Дб"), 1(с"+'), 1(б"э ~), ...; и Дб"+~) = У(б"б~) = Х(о!с"+" ' + -!- аьб") = а!У(б"~" ') + + аь/(б" ). (2) Использование грубой силы или элементарной изобретательности Рассмотрим последовательность Л ,,и > О, 1 < 2 < )!, удовлетворявшую соотношениям Х<„»мь ш аьХ ! (по модулю 2).
Х!»»!!! = Х»(,„.!)+ а,Х»м 1 < Т < Ь; Необходимо показать, что Х»» = а!Х!„Пь + - + аэХ!» вш для и > Й В самом деле, получаем, что Х»! ш а!Х!„П + + аьХш ь!!, когда 1 < 1 < )с < и. Это очевидно для у = 1, так как Х ! = а!Х1» Ю! + Х!» !>э = о!Х!„,!, + аэХ<„е>э + ХЬ -э!з и т. д. Для 7' > 1 по индукции получим Л й = Х~„й.цб ц — а ~Х„~ щ ~~| аЛ1 е, 01 ц — аз ~ ~ ~аХЫ цй 1«й 1«й Ш ~ а,(ХШйг цб ц — о, ~Хм ц~) 1«й ъз о~Х1„Ц + + айх(„йб, Доказательство ке зависит от того, как будут рассматриваться операции: по модулю 2 либо по модулю, равному любому простому числу.
17. (а) Когда последовательность закончится, (й — 1)-мерная строка (Х ец..., Х„+й ~) появится (гп+ 1)-й раз. Для данной (к — 1)-мерной строки (Х,й.ц...,Х,йй й) супйеству- ет только пй предшественников Л„поэтому один из них должен появиться при г = О. (Ь) Так как строка размерности (й — 1) (О,..., 0) встречается (гп+ 1) раз, кйждый возмож- ный предшественник появится обязательно. Поэтому строка размерности й (ам О,,О) появляется для всех ац 0 < а~ < нь Пусть 1 < й < й, н предположим, что доказано, что все строки размерности йй (ой,..., а.,0,...,О) появились в последовательности при а. ф О.
По построению зта строка размерности й (ац..., а„0,..., О, у) не может появиться раньше строки (ац...,а„О,...,О, у) для 1 < у < гп. Следовательно, строка размерности (й — 1) (ац, .., о,, О,..., 0) появилась т раз, и все гп возможных предшественников также появились. Это означает, что строка (а,ац...,а„0,...,0) появилась для 0 < а < т. Доказательство завершается по индукции. Результат также следует из теоремы 2.3.4.211, если использовать ориентированные графы нз упр. 2.3.4.2-23. Множество дуг иэ (хй,..., х„, О,..., 0) в (хз,, хй, О, О,..., 0), где х. К 0 и 1 < у < (г, образуют ориентированное поддерево, четко связанное с десятичными обозначениями Девея. 18. Третий иэ старших двоичных разрядов Г„, ~ полностью определяется первым и тре- тьим двоичными разрядами (7„.
Поэтому появляются только 32 нз 64 возможных пар ((8с7„), (8(7„~.~)). [Замечание. Если бы исполъзовались, скажем, 11-разрядные числа Г„= (.Хп„Хп„й~ ... Хп„.й~е)м то последовательность била бм удовлетворительной для многих случаев применения. Если другие, имеющие более одного двоичного разряда, постоянные появятся в регистре А, то последовательность будет удовлетворять обобщенному спектраль- ному критерию.
(См. упр. 3.3.4-24; необходимо проверять ш при Г = 36, 37, 38, 21. (з. 7 олс(ол Маей. Яос. 21 (1946), 169 — 172.] Любая последовательность с длиной пери- ода т" — 1 без й последовательных нулей приводит к образованию последователъности с длиной периода пй~, если вставить нули в подходнщие места, как в упр. 7. Обрат- но, можно начинать с последовательности с длиной периода т и удалять подходящие нули нз периода, чтобы сформировать последовательность другого типа. Назовем зти (т,й)-пошйедавательности последовательностями типа А и В. Предположения обеспечи- вают существование (р, йг)-последовательностей типа А для всех простых чисел р и всех к > 1.
Таким образом, существуют последовательности (р, й) типа В для всех таких р и lс. Чтобы получить последовательность (р', й) типа В, возьмем е = уг, где д — сте- пень р, а г не кратно р. Начнем с (р,угк)-последовательности типа А, а именно — с Ле, Хц Лз,,; тогда с помощью системы счисления с основанием р сгруппированные гшф- ры (Хе. Хд-))р,(Хй...Хы ~)ю... образуют последовательность (рй,гк) типа А, так как д н рщ ' — 1 — взаимно простые числа н последовательность имеет период длиной рй" — 1. .й. д й Это приводят к получению (рй, гк)-последовательности (К,) типа В, а (Уе11 ..
У, ~)ры (111'„й~... Уг -!)рй..... являются (рй", й)-погдедователъностями типа В. Доказывается ана- логично, так как г н рй — взаимно простые числа. ЕМТ6 65 3ИР 1Н 1 Цена использования таких случайных чисел составляет 14+ гг единиц времени. Но предположим, что мы обращаемся не к втой программе, а к программе получения случайных чисел НИОЕМ: 0ЕС6 1; 162 ЕИОЕИгЕОА Т,б.
НЕСЕМ ЗТД 1Р ЕИТ6 24 СОА у+31,6 А00 Т,б 3ТА Т+31,6 ОЕС6 1 36Р «"4 ЕМТ6 31 ЕОА Т,б А00 Т+24.6 ЗТА Т,б 0ЕС6 1 36Р «-4 ЕМТ6 66 1Н ЛР 1 Сейчас цена равна всего (12+ «г)п. [Подобное обращение на языке С используется в Тйе БсапГоггГ СгарЬВазе (кТен Ъогй: АСТИ Ргем, 1994), СВ.Рь1Р.[ Действительно, во многих случаях предпочтительней генерировать весь массив случайных чисел одновременно. Более того, приведенный выше подход обязателен, когда случайность усиливается методом Люшера (ЬйвсЬег) (см. программы на алгоритмических языках С и РОКТКАМ в разделе 3 6).
27. Пусть Г« = [l«Х Г'ти[. Лемма. После того как (А~ + 7А — 2)/2 последовательных значений О~ 10+ 20 ... (А — ЦО Чтобы получить (гп, А)-последовательность типа В для произвольного гп, можно объединить (р', /с)-последовательности для каждой степени простого множителя пг, используя китайскую теорему об остатках, но существует более простой метод. Пусть (Х ) — зто (г, 1)-последовательность типа В и пусть (У«) — («,А)-последовательность типа В, где г и в — взаимно простые числа. Тогда («Х + 1 ) является (г«, А)-последовательностъю типа В.
Простая равномерная конструкция, которая производит (2, А)-последовательности для произвольного А, была открыта А. Лемпелем (А. Ьегпре!, РЕЕЕ Тгапв. С-19 (1970), 1204 1209). 22. С помощью китайской теоремы об остатках можно найти константы аг,, ам имеющие желаемые вычеты по модулю, равному каждому простому делителю пъ Если гп = Ргрг Рн длина периода равна !сш(рг — 1,,, р, — 1). В самом деле, можно поь лучить приемлемо длинный период для произвольного т (необязательно свободного от квадратов), как показано в упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
