Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 58
Текст из файла (страница 58)
е. когда Л = Л~Лз. Теперь, поскольку (а~аз) и 1, получаем 1 щ (о~аз) "' щ оз"', отсюда следует, что ЛЛ~ кратно Лт. Это влечет, что Л кратно Лт, так как Л~ и Лз — взаимно простые числа. Аналогично Л кратно Лы значит, Л кратна Л~Лз. Очевидно, что (а~аз)~'"' щ 1; таким образом, Л = Л~Ль (Ь) Если а~ имеет порядок Л(т), аз — порядок Л, нз (а) следует, что Л(гп) кратно Л, С другой стороны, можно найти элемент более высокого порядка, а именно — порядка 1сщ(Л, Л(щ)). 16.
(а) /(х) =(х — о)(х" '+(а+са)х" з+ +(а" + +с -~))+/(а). (Ь) Утверждение очевидно, когда и ж О. Если а является корнем, то /(х) щ (х- а) 6(х); поэтому, если а' — какой-нибудь другой корень, то 0 щ /(о ) ат (а — а)9(а'). Поскольку а' — а не кратно р, то о должно быть корнем 9(х).
Итак, если /(х) имеет более л разлнчнык корней, то о(х) имеет более и — 1 различных корней. (с) Л(р) > р — 1, так как /(х) должен иметь степень > р — 1 для того, чтобм иметь так много корней. Но по теореме 1.2.4Р Л(р) < р-1. 17. Согласно лемме Р 11з щ 1 (по модулю 25), 11з ф 1 (по модулю 125), и т. дл таким образом, порядок 11 есть о' ' (по модулю 5').
Однако максимальное значение Л(5') = 4 5' Но согласно лемме Я общая длина периода является наименьшим общим кратным периода по модулю 2' (а именно — 2' з), периода по модулю 5' (а именно — 5" ') н равна 2' 5' = Л(10'). Период по модулю о' может быть равен 5" ' или 2 5' ', или 4. 5' не влияя на длину периода по модулю 10'. так как найдено наименьшее общее кратное. Значения первообразных элементов по модулю 5' сравнимы с 2, 3, 8, 12, 13, 17, 22, 23 по модулю 25 (см.
упр. 12), а именно — 3, 13, 27, 37, 53, 67, 77, 83, 117, 123, 133, 147, 163, 173, 1Л7. 197. 18. В соответствии с теоремой С а шог(8 должно быть равно 3 или 5. Знание цериода а по модулю 5 и модулю 25 позволяет применыть лемму Р, чтобы определить допустимые значеыия а пмк1 25.
Период = 4 5' 1: 2, 3, 8, 12, 13, 17, 22, 23; период = 2 5' '. 4, 9, 14, 19; период = 5' '. 6, 11, 16, 21. Каждое из втих 16 значений дает одно значение а, 0 < а < 200, такое, что а пнн1 8 = 3, и другое значение а, такое, что а пмк1 8 = 5, 19. Некоторые примеры можно найти в строках 17-20 табл. 3.3.4 — 1. 20. (а) АУ» + Хо ьд АУ.~» + Хо (по м»щулю т) тогда и только тогда, когда г„ш 1'„» (по модулю т'). (ь) (1) Очевидно. (8) теорема А. (ш) (а" — 1)/(а — 1) ш О (по модулю 2') тогда и только тогда, когда а" ш 1 (по модулю 2'~'), если а зь -1, порядок а по модулю 2'41 равен удвоенному порядку по малулю 2'. (1гт) (а" — 1)/(а — 1) = О (по мозулю р') тогда и только тогда, когда а" ш 1. 21.
Х„44 ш Х„+ Л; согщ»сно равенству 3.2.1 — (6), ы з является делителем т, так как з— степень р, когда т — степень р. Следовательно, заданное целое число «кратно т/з тогда н только тогда, когда Хо, ш О, а «кратно ш/боб(Х„ш). 22. Алгоритм 4.5.4Р позволяет проверять за приемлемое время, будут лн числа вида т = Ь шЬ' ш 1 простыми, когда, скажем, Ь - 2»з н 1 < Ь 100. Вычисления могут производиться в Ь-ичной системе счисления, так как особый вид т содействует ускорению операции возведения в квадрат шос( т.
(Рассмотрим, например, возведение в квадрат шоо( 9999998999 в десятичной системе счислении.) Алгоритм 4.5.4Р следует, конечно, использовать только тогда, когда известно, что т не имеет малых делителей. Марсалья и Заман (Аппа(з оГ Арр(гес( РгобаЫ)гзу 1 (1991), 474- 475) показали, что ш = 641 — Ьгг + 1 является простым числом с первообразным корнем Ь, когда Ь равно простому числу 2зз — 5. Разложение на множятели гп — 1 = Ьгг(Ь-1)(Ь +Ьз+Ь4+Ьз+Ьг+Ь+1)(Ь'4+Ьг+1) требуется для того, чтобы установить первообразность Ь; один из 17 простых множителей т — 1 имеет 99 десятичных цифр. В результате можно бьгтЬ увврснщ»М, Чта ПОСЛЕдаоательность х„= (к гг — г„-»з -с ) шоб6 = х -гз -х„-»з-с +6с»41 имеет период длиной т — 1 - 1О лля каждого ненулевого выбора начальных значений О < х 1,, Х-зз < Ь, 414 когда со = О.
Тем не менее 43 является, скорее всего, малым значением Ь с точки зрения шагового критерия "день рождения" (см. раздел 3.3,21) и 22 примерно равно 43/2, Рассмотрев "смесь", можно прийти к выводу, что мы предпочитаем значения Ь и Г, для которых несколько первых частичных отношений в цепной дроби 1/Ь мюпо.
Чтобы избежать возможных проблем с етым генератором, Люшером (ЬбзсЬег) была предложена хорошая идея — отбросить несколько чисел (см. раздел 3.2.2). Здесь приведено несколько простых чисел вцда Ь ш Ь ш 1, удовлетворяющих ограни» чению Ь = 2зз и 50 < Ь < 100.
для вычитания с заимствованием: Ьз" — Ьг — 1, 6гз — 6'г — 1, Ьзз Ьш 1 Ьы Ьш 1 Ьоз Ьш 1 Ьзз Ьзз+1 Ьш Ьм+1 Ьоо Ьы+1 Ьго Ьзг+1 Ьз4+1 Д „„„„, (,зз+Ьгг 1 (,41+1,44 1 Ьг»+Ьгг 1 Ьоо+(,зз (Непа зходяп»не с точки зрения "смеси" простые числа: Ьзз - Ьз — 1, Ьзз — Ьзг — 1, 644 -Ьзг — 1, Ь Ь" 16 6 16 Ь 16 Ь 164 64+16 Ь'+16 Ь+1 Ь"-Ь" +1, Ь'з-Ьы+1;6" +Ь'-1, Ь" +Ьп — 1, Ьзз+Ьзо — 1,6оз+6"-1.) Для вычислению периода полученной последовательности необходимо знать множители т — 1, но зто неосуществимо для таких больших чисел (разве что нам крайне повезет).
Предположим, что удалось найти простые множители «1,..., «1; тОГда ВЕроятнОСть, чта Ь~ Ого шоо(п» = 1, является крайне малой, только 1/«, за исключением очень малых простых «. Следовательно, можно быть совершенно уверенным, что период Ь" шоо(т является очень длинным, нес»гагры на то что множитель ш — 1 неизвестен. Действительно, период является почти безусловно очень длинным, даже если т— не простое число. Рассмотрим, например, случай для Ь = 10, Г = 3, 6 = 10 (кото- рый мало подходит для генерирования случайных чисел, но значения Ь, ! и Ь настолько малы, что можно получить точные результаты).
(10" шос(ш) имеет период длиной )сш(219„11389520) = 2494304880, где т = 9999И8999 = 439 ° 22779041; 4И9999500, где т = 9999999001; 5000000499, где т 10000000999; !сш(1, 16, 2686, 12162) 130668528, где ш = 10000001001 = 3 17 . 2687 72973. Некоторые редко встречающиеся наборы начальных значений могут сократить период, когда ш — не простое число. Но можно быть твердо уверенным в получении хорошега результата, если выбрать, скажем, Ь = 1000, ! = 619 и Ь = 2ш.
РАЗДЕЛ 3.2.1.3 1. с = 1 и В' — всегда взаимно простые числа, и каждый простой делитель ш = Вз является делителем В. Таким образом, по крайней мере квадрат этого делителя делит число Ь = Вз. 2. Только 3. Таким образом, генератор не рекомецлучтся, несмотря на его длиннмй период.
3. Потенциал равен 18 в обоих случаях (см. следующее упражнение). 4. Так как из того, что о шоб 4 = 1, следует, что а шоб 8 = 1 или 5, получаем Ь шаб 8 = О или 4. Если Ь кратно 4, но не кратно 8, а Ь~ кратно 8, ясно, что Ь' ш 0 (по модулю 2)' влечет Ь( ьз О (по модулю 2)'. Таким образом, Ь~ не может иметь потенциал, выше Ь. 5.
Потенциал равен наименьшему из значений з, таких, что ~1з > е для всех 71 6. Модуль должен делиться на 2е или на р4 (для нечетных простых р) для того, чтобы потенциал был равен 4. Такими будут только величины т = 2з" + 1 и 10з — 1. 7. а' = (1-5+Ьз —... ) шодгл, где члены Ь',Ь'+' и т д. опускаются (если з — потенциал), 8. Так квк Х„ всегда нечетно, Х е~ =(2" +3 2' +9)Х„шо62 =(2' +ОХ„~~ — 9Х )шо62 Если даны У„и У„«ц то возможности для у«42 (о + 6(1 «+1 + щ) 9(У«+ ез)) шаб 10 0 < щ < 1 и 0 < ез < 1, ограниченм и неслучайны. За««ечаиве. Если множители, предложенные в упр.
3, были бы, скажем, равны 2 + 2'з + 2з + 1, а не 2зз + 2'з + 2з + 1, можно было бы аналогично показать, что Х ьз — 10Х««~ + 25Х«щ сопзсапс (по модулю 2 ). Вообще говоря, а*б не должно делиться на высокие степени 2, когда б малб, В противном случае получится "несостоятельность второго порядка". Более подробно этот вопрос обсуждается в разделе 3.3.4. Генератор из етого упражнения рассматривался в работе Мак-Ларена и Марсалья (Мас1лгеп, Мвгеаб!!а, ЯАСМ 12 (1965), 83-89). Недостатки таких генераторов, впервые были продемонстрированы М.
Грннбергером (М. Сгеепбегбег), САСМ 8 (1965), 177-179). Даже через десять лет после появления этой работы подобные генераторы широко исполь. завались (см. обсуждение 84890 в разделе 3.3.4). РАЗДЕЛ 3.2.2 1. Метод следует применять с большой осторожностью. Прежде всего, аС«, вероятно, будет настолько большим, что добавлять с/ш не имеет смысла, и операции по "шоб Г почти уничтожат любые следы оставшихся от добавления значений.
Мы заключаем, что необходимо использовать арифметические операции с плавающей запятой с двойкой точностью. Даже с двойной точностью нужна уверенность, чта нет округления и т. д., иначе последовательность чисел будет вести себя совершенно по-другому, так как нарушатся теоретические основы хорошего поведения последовательности (на см. упр. 23). 2. Х„тх равно либо Х -х +Хп, либо Хэ-1+Хе — иь Ясли Л ех < Хн, то должно быть Х„ьх м Х„х + Մ— ип отсюда Хээх < Хэ-х. 3. (а) Подчеркнутые числа — это Щ] после шага МЗ. Таким образом, потенциал может быть сведен к 1! (См. комментарии, приведенные в ответе к упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
