1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 65
Текст из файла (страница 65)
Затем возвратной индукцией по ! в строке 6 доказываем, что иы —— и шод оы. Строки 8 и 9 позволяют сделать это легко. Полагая 1=0, получаем и,=и глод рь Детали оставляем в качестве упражнения. С! Теорема 8,9. Алгоритм 8.4 тратит Оа(М(Ьй) !ой й) времени, если для представления каждого из чисел р8 достаточно Ь битов, Д о к а з а тел ь с т в о. Легко видеть, что больше всего времени требуют циклы в строках 3, 4 и 7 — 9. Каждый из них занимает Ьей(п 1. 1ог 1 — 0 цпИ1 й — 1 бо дм — р;, 2. 1ог ! -1 нп(И ! — 1 Йо 3.
1ог 1 0 е(ер 2г цп1И й — 1 бо 4. 9и — В»- и48,ЫГ1 5. и„и; 6. 1ог !' — ! 8!ер — 1 пп1И 1 до 7. !ог 1 -0 81ер 2/ пп1И й — 1 до Ьед!и 8. иь г, - ОСТАТОК (и;~!а,»,); 9, ичее~-, г 1 — ОСТАТОК(и, (4,ее~- г 1) епд; 10. 1ог 1 0 нпИ! й — 1 е(о ие — ие, епб рис. З.З. Вычисление иычечси. В.В. МОДУЛЬНАЯ АРИФМЕТИКА ПОЛИИОМОВ Ое (2»-/М (2! 'Ь)) шагов').
Поскольку мы предположили, что М (ап))аМ (и) для а-ь1, то сложность выполнения этих циклов ограничена величиной Ов(М(2 Ь))=ОЕ(М()ВЬ)). Так как каждый из циклов повторяется не более 1=!Ой й раз, получаем нужный результат. П Следствие. Если для представления «аждого из модулей р„ р„..., р, требуется Ь битов, то вычеты по этим модулям можно вычислить за время Оа(ЬЬ !ОЕ й 1ОЕ ЬЬ!ОЕ 1од ЬЬ).
8.5. МОДУЛЬНАЯ АРИФМЕТИКА ПОЛИНОМОВ И ВЫЧИСЛЕНИЕ ИХ ЗНАЧЕНИЙ Результаты, аналогичные результатам для целых чисел, спр໠— 1 ведливы и для полиномов. Пусть р„..., р»,— полнномы н р=Пр!. »=о Тогда каждый полинам и можно представить последовательностью и„и„..., и„, остатков от деления и на каждый полинам р,. Полинам и,— это тот единственный полинам, для которого СТ (и!)( (СТ(р!) и и=р»д!+и! для некоторого полинома дь В такой ситуации мы будем писать и,=и !под ро что совершенно аналогично модульной записи целых чисел. По аналогии с леммой 8.1 можно показать, что соответствие и»~(им и„ ..., и» !) взаимно однозначно, если полиномы р! попарно взаимно просты и степень полинома и меньше степени полинома р, т.
е. РАЗМЕР (и)(РАЗМЕР(р). Более того, алгоритм 8.4 для вычисления вычетов применим к полиномам, если в качестве р! взять полиномы, а не целые числа. Вместо Ь (числа битов в каждом р,) надо рассматривать наибольшую степень полиномов рь Разумеется, сложность измеряется числом арифметических, а не битовых операций. Тогда справедлива теорема, аналогичная теореме 8.9. Теорема 8.10. Перенеся алгоритм 8.4 на полиномы, можно найти вычеты полинома и(х) относительнополиномовре, р», . р» »за время ОА (М (с(я) 1ОЕ )В), где с( — верхняя граница степеней полиномсв »-! р, и степень полинома и меньше степени полинома П р!.
»=В Д о к а з а тел ь с т в о. Аналогично теореме 8,9; оставим его в качестве упражнения. П Следствие 1. Для нахождения вычетов полинома и относительно полиномсв р„р„..., р», требуется не болев ОА(сй 1ОЕ )В 1ОЕ дй) !) Напомним, что 0(п) и А) (л) по существу соапааанп, ГЛ. Е АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ времени, где д — верхняя граница степеней полиномов р, и степень ь — 1 полинома и меньше степени полинома П рь к=ь Пример 8.5. Рассмотрим четыре полиномиальных модуля р„=х — 3, р, =х'+х+1, р,=х' — 4, р,=2х+2 и положим и=х'+х'+Аь+х'+к+1.
Сначала вычисляем произведения р,р, = х' — 2х' — 2х — 3, р,р, = 2х'+2х' — 8х — 8. Затем вычисляем и' = и вод р,р, = 28х'+ 28х+ 28, й=и юод р,р,=21х+21. В самом деле, и = р,р,(х'+ Зх+ 9) + 28х'+ 28х+ 28 и и рзрз~ — х'+ — )+21х+21. l! 52 !А~2' 2) Далее, и щод р,=и' щод р,=364, и щод р, = и' щод р, = О, и щод р,=и !под р„=21х+21, и юод р,=и' вод р, = О. П Заметим, что алгоритм БПФ из равд.
7.2 в действительности является реализацией этого алгоритма, когда в качестве р„ р„ ... ..., рь ! берутся х — ыь, х — ы!, ..., х — в"-!. Алгоритм БПФ из- влекает выгоду из выбора в качестве р! полинома х — ы!. Благодаря подходящему упорядочению множества полиномов р! каждое про- изведение равно разности степени х и степени ы и потому деление выполняется особенно легко. Как было отмечено в равд. 7.2, если р! — полипом первой степени х — а, то и п!од р,=и(а). Поэтому случай, когда все полиномы р, имеют степень 1, особенно важен.
Из теоремы 8.10 вытекает следу- ющий результат. Следствие 2, Значения полинома и-й степени в и точках можно вычислить за время ОА (п 1оя'и). До к а з а тел ь ство. Чтобы вычислить и(х) в и точках а„а„..., а„„вычисляем и(х) пюд(х — а!) для Ъ=!(и. Это за- нимает время ОА(п!ои' и) в силу следствия 1, ибоздесьд=1.
С) ззь О.О. ПРИМЕНЕНИЕ КИТАйСКОй ТЕОРЕМЫ ОВ ОСТАТКАХ 8.6. ПРИМЕНЕНИЕ КИТАЙСКОЙ ТЕОРЕМЫ ОБ ОСТАТКАХ Изучим задачу преобразования модульного представления це. лого числа в его позиционное представление '). Пусть даны попарно взаимно простые модули р„р„..., р», и вычеты и„и„..., и» „ где А=2', надо найти такое целое число и, что и+-»(и„и„..., и»,).
Это можно сделать с помощью целочисленного аналога интерполяг(ионной формулы Лагранжа для пол иномов. Лемма 8.2. Пусть сг — произведение всех рм кроме р, (т. е. с,= я — 1 =р(рг, где р=Яуг). Положим й,=с, шой рг (т. е, й»с»=1(пюй р») г о и 0 .й»(рг). Тогдга и= — ~с»йгиг (шойр).
(8.20) г о Д о к а з а те л ь с т в о. Поскольку числа ру попарно взаимно просты, то, как известно (упр. 7.9), числа йг существуют н единственны. Кроме того, с» делится на р при /чь(, так что сгйгиг~ =0 (гной Рг) пРн (чь(. ПозтомУ »-! ~~.",сгйгиг =суй»и (шойр ). г=о Гак как сгй»=1(гной рг), то »-г ~сгйги, иг (той р ). г=о Так как рг делит р, то эти соотношения выполняются даже тогда, когда все арифметические операции производятся по модулю р, Таким образом, (8.20) верна П Наша задача состоит в эффективном вычислении (8.20). Сразу трудно увидеть, как можно вычислять йг по ри не прибегая к методу проб и ошибок.
Позже мы увидим, что зта задача не так уж трудна, если использовать алгоритм Евклида из равд. 8.8 и его быструю реализацию из равд 8.10. В данном разделе мы изучим только ту форму китайской задачи об остатках, которая основана на "предваритель. ной обработке". Если часть входных данных фиксирована для ряда задач, то все величины, зависящие только от втой фиксированной части, можно вычислить заранее и считать частью входа, Алгоритм, в котором сделаны такие предварительные вычисления, называют алгоритмом с предварительной обработкой данных ') Проне:с восстановления числя по его остаткам был известен китайиам более 2000 лет навал, и потому огогветсгвуюи»ую теорему называют китааскгят теоремой об осмюмклл, ГЛ. О.
АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ Для китайского алгоритма с предварительной обработкой данных входом будут служить не только вычеты и модули р„но и обратные к ним (числа с(с). Эта ситуация не является нереальной. Если часто применять китайский алгоритм для перевода чисел, представленных вычетами по фиксированному множеству модулей, то разумно заранее вычислить те функции от этих модулей, значения которых используются в алгоритме. В следствии теоремы 8.21 мы увидим, что на оценку сложности наличие предварительной обработки (или ее отсутствие) влияет весьма скромно.
Анализируя (8.20), замечаем, что слагаемые с!с!си! при разных / имеют много общих сомножителей. Например, ссс(сис имеет сомножителем число р, р,... росс ! если с)й/2, и число росс рос! ...ро „если с(л/2. Поэтому можно записать (8.20) в виде ,саго-! ! о-! о-! ~ осо-! и = 1 ~ ссс(сис( х П рс + ( П ссс(сис '/х Д р„ с а с=о/оа! с=А!о+с с с=о гДе сс — это пРоизвеДение Р, Р,, Роса ! без Рс, а с", — пРоизведение роса роса,!...р„, без рс. Это наблюдение должно подсказать прием "разделяй и властвуй", аналогичный тому, что применялся при вычислении вычетов. Находим произведения с+ос- ! йс/= Ц р.
ав= с (как в алгоритме 8.4), а затем — целые числа !+о~+! зс/ = П с)Асс(„и„/р„. и=с Если 1 О, то оса=с(сис. Если /)О, то вычислЯем зс! по фоРмУле ас/ — — зс,/ сстс+ос-с,/ с+а,+,с-!./,с/с,г !. Наконец, получаем з„=и, что и нужно для (8.20). Алгоритм 8.8. Быстрый китайский алгоритм с предварительной обработкой данных Вход. 1. Попарно взаимно простые целочисленные модули р„р„...
..., ро „где А=2' для некоторого 2. Множество "обратных" к ним чисел с(„с(с,..., с(о „т. е. о †! таких, что с(с=(р/рс)-сгной р„где р=Др!. с=о 3. Последовательность вычетов (и„и„..., ио,). Выход. Единственное целое число и, 0(и(р, для которого ио-о(ио, ис,..., и,,). эзв О.О. ПРИМЕНЕНИЕ КИТАЙСКОЙ ТЕОРЕМЫ ОБ ОСТАТ АХ ЬЕ61п 1. 1ог 1 -0 пп(11 /г — 1 до ам г(г»и11 2. 1ог / -1 нпН! 1 йо 3. 1ог 1 -0 в(ер 2/ ИПИ /с — 1 6о 4. 2// — ЗГ,/,аОГ+2/-Ч /-1+ЗГЬ2/гь /-1Нб/ /,', 5. Ит)(е зо1 п1ой дог епй Рис. 8.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
