Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 207
Текст из файла (страница 207)
Далее, предположим, что каждое значение х; извлекается независимым образом из множества 2„, и что все они распределены в этом множестве равномерно. В соответствии с анализом парадокса о днях рождения, проведенном в разделе 5.4.1, математическое ожидание количества шагов, предпринятых перед зацикливанием последовательности, равно 9 (~/й). Теперь перейдем к требуемой модификации.
Пусть р — нетривиальный множитель числа и, для которого справедливо уравнение ясс1 (р, и/р) = 1. Например, если разложение числа и имеет вид и = р" р" . р',", то в качестве множителя р можно выбрать величину р". (Если е1 = 1, то толь р будет играть наименьший простой множитель числа и; это полезно взять на заметку.) Последовательность (хс) порождает соответствующую последовательность (х',) по модулю р, где х', = х, пюс1 р для всех г. Кроме того, поскольку в определении функции г„содержатся только арифметические операции (возведение в квадрат и вычитание) по модулю и, нетрудно показать, что величину х';+1 можно вычислить на основании величины х';.
Рассмотрение последовательности "по модулю р" — уменьшенная версия того, что происходит по модулю и: ! хс+с — — х,+1 пюс1 р = У„(хс) пюс1 р = ((х~ — 1) шос1и) тпос1 р = (х~ — 1) тпос1 р = ((хс пюс1 р) — 1) шос1 р = ~(х';) — 1) тос1 р = Ь( с) где четвертое равенство следует из упражнения 31.1-6. Таким образом, хотя мы и не вычислили явным образом последовательность (х,'), эта последовательность вполне определена и подчиняется тому же рекуррентному соотношению, что и последовательность (х;). Глава 31. Теоретико-числовые алгоритмы 1011 Рассуждая так, как и ранее, момсно прийти к выводу, что математическое ожидание количества шагов, выполненных перед зацикливанием последовательности (х',), равно Э ( сгр). Если значение р мало по сравнению с п, то последовательность (х',) может начать повторяться намного быстрее, чем последовательность (х,).
В самом деле, последовательность (х';) начнет повторяться, как только два элемента последовательности (хс) окажутся эквивалентными по модулю р, а не по модулю и. Вышесказанное проиллюстрировано на рис. 31.3б и в. Обозначим через 1 индекс первого повторившегося значения последовательности (х',), а через и > Π— длину цикла, полученного таким образом. Другими словами, 1 и и > Π— наименьшие значения, для которых при всех 1 > О выполняется равенство х'+, — — х',+„+,. Согласно приведенным выше рассуждениям, математическое ожидание величин 8 и и равно 9 ( /р). Заметим, что если х',+, —— = х',+„+,, то р ~ (хн.„+с — хс+,). Таким образом, ксс1 (хс+„а; — хс+;, и) > 1. Поэтому после того как в процедуре Роьс.Ако Кно в переменной у будет сохранено любое значение хы у которого сс > т, величина у спос1 р всегда будет находиться в цикле по модулю р.
(Если в переменной у будет сохранено новое значение, оно также окажется в цикле по модулю р.) В конце концов переменной к будет присвоено значение, превышающее и, после чего в процедуре будет пройден полный цикл по модулю р, не сопровождающийся изменением значения у. Множитель числа п будет обнаружен тогда, когда х, "натолкнется" на ранее сохраненное значение у по модулю р, т.е. когда х; = у (пюс1р).
Скорее всего, найденный мнохситель будет равен р, хотя это случайно может оказаться число, кратное р. Поскольку математическое ожидание величин с и и равно О ( /р), математическое ожидание количества шагов, необходимых для получения множителя р, равно 9 (,/р). Есть две причины, по которым этот алгоритм может оказаться не таким эффективным, как ожидается.
Во-первых, проведенный выше эвристический анализ времени работы нестрогий, и цикл значений по модулю р может оказаться намного длиннее, чем /р. В этом случае алгоритм работает правильно, но намного медленнее, чем хотелось бы. Практически же это представляется сомнительным. Во-вторых, среди делителей числа и, которые выдаются этим алгоритмом, всегда может оказаться один из тривиальных множителей 1 или п. Например, предположим, что п = рс1, где р и в — простые числа. Может оказаться, что значения т и и для множителя р идентичны значениям т и и для множителя д, и поэтому множитель р будет всегда обнаруживаться в результате выполнения той же операции ясс1, в которой обнаруживается множитель сг. Поскольку оба множителя находятся одновременно, процедура выдает тривиальный множитель рс1 = п, который бесполезен.
На практике и эта проблема кажется несущественной. При необходимости нашу эвристическую процедуру можно перезапустить с другим рекуррентным соотношением, которое имеет вид хс+с — (х1 — с) (пюс1п). (Значений параметра 1012 Часть т'11. Избранные темы с, равных О и 2, следует избегать по причинам, вникать в которые мы здесь не станем; другие значения вполне подходят.) Конечно же, этот анализ нестрогий и эвристический, поскольку рекуррентное соотношение на самом деле не является "случайным".
Тем не менее, на практике процедура работает хорошо, и, по-видимому, ее эффективность совпадает с полученной в ходе эвристического анализа. Она представляет собой вероятностный метод поиска небольших простых множителей, на которые раскладывается большое число. Все, что нужно для полного разложения 13-битового составного числа и, — найти все его простые множители, меньшие 1п1~з~, поэтому можно ожидать, что процедуре Ро~ьАкп Кно понадобится не более из/4 = 2д/4 арифметических операций и не более п1~413з = 2Д/413з битовых операций. Зачастую наиболее привлекательной особенностью этой процедуры оказывается ее способность находить небольшой множитель р числа п, выполнив при этом операции, математическое ожидание количества которых равно 8 ( /р).
Упражнения 31.9-1. Когда процедура Роымкп Кно выведет множитель 73 числа 1387, если история вычислений в ней имеет вид, показанный на рис. 31.3а? 31.9-2. Пусть задана функция Г': Е„- Е„и начальное значение хо е Е„. Определим рекуррентное соотношение яч = г'(х; 1) для 1 = 1, 2,.... Пусть 1 и и > Π— наименьшие значения, для которых выполняется уравнение хс+; — — хс+„+; для 1 = 1, 2,... (в терминах р-алгоритма Полларда, 1 — это длина хвоста, а и — длина цикла р). Сформулируйте эффективный алгоритм, позволяющий точно определить значения 1 и и, и проанализируйте время его работы. 31.9-3.
Чему равно математическое ожидание количества шагов, которые понадобится выполнить процедуре Роь1.Апп Кно, чтобы обнаружить множитель вида р', где р — простое число, а е > 1? * 31.9-4. Как уже упоминалось, одним из недостатков процедуры Роы.лиз Кно является то, что на каждом шаге рекурсии в ней необходимо выполнять операцию йод. Было высказано предположение, что вычисления йод можно объединить, накопив произведение нескольких величин х, и используя это произведение при вычислении кос) вместо величины х;.
Приведите подробное описание того, как можно было бы реализовать эту идею, почему она работает и какой размер группы можно было бы выбрать для достижения максимального эффекта при обработке б-битового числа и. Глава 31. Теоретико-числовые алгоритмы 1013 Задачи 31-1. Бинарный алгоритм ясб На большинстве компьютеров операции вычитания, проверки четности (нечетное или четное) и деления пополам выполняется быстрее, чем вычисление остатка. В этой задаче исследуется бинарный алгоритм йсй (Ьшагу ясд а!яопйп~), позволяющий избежать вычисления остатков, которые используются в алгоритме Евклида.
а) Докажите, что если числа а и 6 — четные, то справедливо уравнение ясс! (а, 6) = 2 ясй (а/2, 6/2). б) Докажите, что если а — нечетное, а 6 — четное, то справедливо уравнение ясс! (а, Ь) = ясс1 (а, Ь/2). в) Докажите, что если числа а н Ь вЂ” нечетные, то справедливо уравнение ась(а,Ь) = ясд((а — 6)/2,6). г) Разработайте эффективный бинарный алгоритм поиска ясс1 для целых чисел а и Ь, где а > 6, время работы которого равно О (1яа).
Предполагается, что на каждое вычитание, проверку на четность и деление пополам затрачивается единичный интервал времени. 31-2. Анализ битовых операций в алгоритме Евклида а) Рассмотрим обычный алгоритм деления "на бумаге" а на 6, в результате которого получается частное д и остаток т. Покажите, что в этом методе требуется выполнить О ((1+ !я а) 1я 6) битовых операций. б) Определим функцию а(а,Ь) = (1+ 1яа) (1+1яЬ).
Покажите, что количество битовых операций, которые выполняются в алгоритме Епсыгз при сведении задачи вычисления величины ясб(а,6) к вычислению величины ясс! (Ь, а пюс1 Ь), не превышает с(р (а, 6)— -а (6, а шод 6) ) для некоторой достаточно большой константы с > О. в) Покажите, что выполнение алгоритма акын(а, 6) требует в общем случае О (а (а, 6)) битовых операций, и О (,9з) битовых операций, если оба входных значения являются !3-битовыми числами. 31-3. Три алгоритма вычисления чисел Фибоначчи В этой задаче производится сравнение производительности работы трех методов вычисления и-го числа Фибоначчи Р'„при заданном и. Считаем, что стоимость сложения, вычитания или умножения двух чисел независимо от их размера равна О (1). Часть Ч11.
Избранные темы 1014 а) Покажите, что время работы прямого рекурсивного метода вычисления числа Р'„на основе рекуррентного соотношения (3.21) увеличивается экспоненциально с ростом п. б) Покажите, как с помощью запоминания вычислить число Г„за время 0(п). в) Покажите, как вычислить число Р'„за время 0(1йп), используя только сложения и умножения целых чисел. (Указание: рассмотрите матрицу и ее степени.) г) Теперь предположим, что для сложения двух Д-бнтовых чисел требуется время 6 (13), а для их умножения — время 9 (Дз). Чему равно время работы перечисленных выше алгоритмов с учетом такой стоимости выполнения элементарных арифметических операций? 31-4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
