1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 69
Текст из файла (страница 69)
строения асимптотически быстрого алгоритма, который восстанавливал бы целое число по его вычетам без предварительной обработки данных. Вспомним, что алгоритм 8.5, использующий предварительную обработку, тратит ОБ(М(ЬЬ) !ой й) времени на восстановление числа и по вычетам, взятым по й модулям, содержащим по Ь двоичных разрядов. Задача состоит в вычислении йг=(р/р!)-'шог( рь где ре, р, ..., р„, — модули, а р — их произведение.
С помощью очевидного алгоритма, основанного на приеме "разделяй и властвуй'", можно вычислить р, найдя сначала произведения пар чисел рь затем четверои чисел р, и т. д., за время ОБ(М (Ыг)1оЕ й). Техника алгоритма 8,5 позволяет вычислить е,=(р/р,) апой р! при 0<1(й за Оа(М (Ья) 1ОЕ й) шагов без предварительной обработки данных. Остается оценить время, необходимое для вычисления йг=е шоб рь Так как р/р! — произведение всех модулей, отличных от рг, оно должно быть взаимно просто с рь Если представить р/р! в виде ар,+ег, где а — некоторое целое число, то в силу предыдущего е, и р, будут взаимно просты, т. е. НОД(ег, р,)=1. Поэтому, если х и у таковы, что егх+р,у=1, то егх=1 (шоб р!).
Следовательно, х= ==е 'г=йг пюй р!. Но такие числа х и у вычисляются расширенным алгоритмом Евклида. Хотя процедура НОД была разработана, чтобы вычислять только НОД(р„р,), мы строили процедуру ПНОД так, чтобы она вычисляла матрицу )(о!!„гз!. Поэтому простая модификация НОД-алгоритма могла бы вычислять и )го,цо!. Тогда можно было бы получить х, поскольку это левый верхний элемент матрицы )тол!о>.
Сформулируем результат о времени работы китайского алгоритма без предварительной обработки данных. Теорема 8.21. В случае целых чисел китайский алгоритм имеет сложность Ои(М (Ьй) 1ОЕ /г)+Он(ЬМ (Ь) !ОЕ Ь), где й — числа используемых модулей, содержащих Ь двоичных разрядов каждый. Д о к а з а т е л ь с т в о. В силу анализа, проведенного выше„ первый член выражения для сложности соответствует вычислению чисел е; и выполнению алгоритма 8.5.
Второй соответствует вычислению чисел й!, поскольку вычисление чисел х и у можно вести по шоб р„используя везде Ь-битовые операции. П Следствие. Китайский алгоритм без предварительной обработки данных имеет временную сложность ОБ(Ьл 1ОЕе Ьй !ОЕ 1ОЕ ЬЬ) '). ')Интересно заметить, что при М (л)=я !оя я !оя !оя л зта величина наилучшая, которую можно получить из теоремы З.2! независимо от того. как соотносятся ьна. ъву гл, я лгифмятические опягхции 8.12. РАЗРЕЖЕННЫЕ 0ОЛИНОМЫ Представляя полипом от одной переменной в виде ~Завх!, мы г=-о предполагали до сих пор, что он плопвнмй, т.
е. отличны от нуля почти все его коэффициенты. увля многих приложений полезно предполагать, что полипом разрежен, т. е. число ненулевых коэффициентов много меньше его степени. В такой ситуации логично представлять полипом списком пар (ап у!), состоящих из ненулевого коэффициента и соответствующего ему показателя степени переменной х. Мы не можем углубляться в разнообразную технику, известную для выполнения арифметических операций над разреженными полиномами; упомянем лишь два интересных аспекта этой теории. Во-первых, поскольку неразумно применять преобразование Фурье для выполнения умножения, мы дадим один разумный алгоритм умножения разреженных полиномов. Во-вторых, на примере вычисления (р(х))в продемонстрируем удивительное различие между способом, которым следует выполнять арифметические операции над плотными полиномами и аналогичным способом для разреженных полиномов.
Наиболее разумная из известных стратегий умножения разрев женных полиномов состоит в том, что полипом Хавху! задается спиг=-, сном пар (а„у,), (а„у,),..., (а„, у„), где все у! различны и расположены в порядке убывания, т. е. у!)увв.! для !(У<п. Чтобы умножить два полинома, представленных таким образом, находим произведения пар и располагаем их по величине показателей (по вторым компонентам пар), объединяя все члены с одинаковыми показателями. Если это не делать, то придется расплачиваться ростом числа членов с одинаковыми показателями.
Поэтому по мере выполнения арифметических операций сложность начнет значительно превосходить ту, которая была бы, если бы приведение подобных членов выполнялось на каждом шаге. При умножении упорядоченных разреженных полиномов можно извлечь пользу из их упорядоченности и из того, что в одном из них может оказаться много больше членов, чем в другом, чтобы максямально упростить упорядочение множества мономов произведения. Приведем неформальный алгоритм умножения разреженных полииомов таким способом. Алгоритм 8.8.
Умножение упорядоченных разреженных полииомов и Вход. Полиномы У(х)=в,авхг! и Е(х)=~Ьвхв!, представленные 1=! списками пар (а„у,), (а„ув), ..., (а, у„) ВДЗ. РАЗРЕЖЕННЫЕ ПОЛИНОМЫ н (ь„д,), (ь„й,), ..., (ь„, й„), где последовательности 1„..., 1 и йь..., й„монотонно убывают.
Выход. Полинам ~З с,х' =~(х)8(х), представленный списком пар, в котором последовательность 1„..., 1 монотонно убывает. Метод. Не умаляя общности, предполагаем, что т-.п. !. Строим последовательности Я!, 1(1(п, в которых г-й член, 1(г(т, равен (а„8„1„+и!). Таким образом, 5! представляет произведение полииома у (х) на з-й член полинома а(х). 2. Сливаем Вз! ! с Яз! для 1(з(п/2, приводя подобные члены. Затем попарно сливаем полученные последовательности, приводя подобные члены, и повторяем процесс, пока не получим одну упорядоченную последовательность. П Теорема 8.22. Алгоритм 8.8 занимает 0(тп 1ой п) времени ') в предположении, епо т)п, Дои аз а тел ь ство.
Шаг 1, очевидно, имеет сложность 0(т, п). Шаг 2 надо повторить | !оа и ! раз, и ясно, что при каждом выполнении вся работа займет 0(тп) времени. П Посмотрим теперь, как алгоритм 8.8 и его временная сложность влияют на выбор способа выполнения арифметических операций над разреженными полиномами. Пример 8.13. Вычислим р'(х), где р(х) — полинам с п членами в случаях, когда он плотный и когда разреженный. Если полинам р плотный, то легко показать, что лучше всего вычислять рз(х), дважды возводя в квадрат. Иными словами, пусть М(п)=сп!пап, где М(п) — время умножения плотных полиномов. Тогда можно вычислить р'(х) за сп !од п шагов и результат возвести в квадрат за 2сп 1оя 2п шагов, всего затратив Зсп!оя п+2сп шагов.
Для сравнения укажем, что если вычислять р'=рХ(рХ(рХр)), то, как легко видеть, требуется бсп 1од п шагов в предположении, что на рХр* тратится 2М(п) шагов, а на рХр' тратится ЗМ(п) шагов. Таким образом, для плотных полиномов получаем, как и ожидали, что р' надо вычислять повторным возведением в квадрат. Теперь пусть р(х) — разреженный полинам с п членами. Если вычислять (р')' по алгоритму 8.8, то на первое возведение в квадрат уходит сп' !ода времени, а в предположении, что приводятся ие. много подобных членов, второе возведение в квадрат занимает '1 Заметим, что здесь фигурирует сложность нв РАМ, в не зрмфметнческзя, поскольку программа для алгоритма 8.8 неизбежно содержит разветвления, даже если !и и п фиксированы. гл. ь Агиеметнческия опеглцни сп' 1ой и' времени, так что всего тратится с(2п'+и') 1ой п шагов. С другой стороны, р х (р м (р х р)) вычисляется за сп'! оя и+ +сп' 1од и+сп' 1ой п=с(п4+и'+и') (од и шагов. Эта величина меньше времени повторного возведения в квадрат.
Таким образом, повторное возведение в квадрат разреженного полинома не всегда дает хороший способ вычисления р'. Особенно этот эффект проявляется при вычислении р" для больших значений й П УПРАЖНЕНИЯ 8.1. Используйте алгоритм 8.1 для нахождения числа, "обратного" к 429. 8.2. Используйте алгоритм 8.2 для нахождения 429'. 8.3. Используйте алгоритм 8.3 для нахождения полинома, "обратного" к х' — х'+ х' — Зх'+ х' — х'+ 2х+ 1. *8.4. Опишите алгоритм, аналогичный алгоритму 8.2, для вычисления квадратов полиномов. 8.5.
Используйте ваш алгоритм из упр. 8.4, чтобы вычислить (х' — х'+х — 2)'. 8.6. Используйте алгоритм 8.4, чтобы найти представление для числа 1 000 000 по модулям 2, 3, 5, 7, 11, 13, 17, 19. 8,7. Полностью напишите алгоритм нахождения вычетов поли- нома по набору полиномиальных модулей. 8.8. Найдите вычеты полинома х'+Зх'+х'+Зх"+х'+1 по модулям х+3, х* — Зх+1, х'+х — 2 и х' — 1, 8.9.
Полнномы в упр. 8.8 были тщательно подобраны, чтобы можно было легко провести вычисления вручную. Случайно выберите четыре полинома степеней 1, 2, 3 и 4 и найдите относительно иих вычеты полинома х' — 4. Что произойдету 8.10. Пусть 5, 6, 7, 11 — четыре модуля.
Найдите такое число и, меньшее их произведения, что и ++ (1, 2, 3, 4). *8.11, Обобщите лемму 8.3 так, чтобы применить ее к произвольным полиномиальным модулям, корни которых известны или могут быть найдены (например, пол нномы степени меньше 5). Какова сложность восстановления полиномов по их вычетам, если использовать ваш алгоритм (сложность рассматривается как функция от числа и наибольшей степени модулей)? 8.12. Найдите полипом, значения которого в точках О, 1, 2, 3 равны соответственно 1, 1, 2, 2. упРАжнения 8.13. Найдите наибольший общий делитель полиномов х'+ Зх'+ Зх' + х* — х' — х — 1, х' -1- 2х' -1- х' -1- 2х' -1- 2х' -1- х + 1.
8.14. Полиномы в упр. 8.13 были тщательно подобраны, чтобы можно было легко провести вычисления вручную. Выберите два произвольных полннома степеней 7 и 8 и попробуйте найти их НОД. Что произойдет? Каким по вашему предположению окажется НОД? *8.15. Полностью напишите алгоритм нахождения НОД целых чисел, который работал бы время Оз(л!ойзл 1оя 1оя л) на и-разрядных двоичных целых числах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
