8.3. УМНОЖЕНИЕ И ДЕЛЕНИЕ ПОЛИНОМОВ

Вся техника предыдущего раздела переносится на арифметические операции над полиномами от одной переменной. В этом разделе функции и обозначают времена, требуемые соответственно для умножения, деления, обращения и возведения в квадрат полиномов степени Как и раньше, мы предполагаем, что для и подобные неравенства справедливы и для других функций.

Под "обратным" к полиному степени мы понимаем полином — это время нахождения полинома где имеет степень степень, не превосходящую Заметим, что подобно тому, как в предыдущем разделе мы изменяли

масштаб целых чисел с помощью степеней числа 2, можно "изменять масштаб" полиномов, умножая и деля их на степени переменной х.

Так как результаты настоящего раздела очень похожи на результаты для целых чисел, изложим в деталях только один из них: алгоритм обращения полиномов, аналогичный алгоритму 8.1 для целых чисел. Алгоритмы для полиномов в какой-то мере проще соответствующих алгоритмов для целых чисел — в основном благодаря тому, что в степенных рядах в отличие от целых чисел нет переносов. Поэтому в алгоритмах для полиномов не надо корректировать младшие значащие разряды, как это требовалось, например, в строках 5—7 алгоритма 8.1.

Алгоритм 8.3. Обращение полиномов

Вход. Полином степени где степень числа 2 (т. е. имеет 2 членов, где некоторое целое число). Выход. Обратный полином Метод. На рис. 8.2 приведена новая процедура

где степень числа Эта процедура вычисляет

Заметим, что при аргументом будет постоянная а ее обратным — другая постоянная Предполагается что каждую операцию над коэффициентами можно выполнить за один шаг, и

Рис. 8.2. Процедура для обращения полиномов.

поэтому для вычисления нет необходимости вызывать процедуру

Сам алгоритм состоит в вызове процедуры с аргументом

Пример 8.3. Вычислим где . В строке 2 обращаем полином т. е. находим Проверьте, что Поскольку строка 3 вычисляет Затем в строке 4 получаем результат Заметим, что -полином степени

Теорема 8.6. Алгоритм 8.6 правильно вычисляет полином, обратный к данному.

Доказательство. Докажем индукцией по где степень числа 2, что если имеет степень то где полином степени, меньшей Базис, т. е. случай тривиален, ибо и слагаемого нет.

Для шага индукции положим где Тогда по предположению индукции, если то где . В строке 3 вычисляем

Достаточно показать, что полином степени, меньшей Тогда деление на в строке 4 дает искомый результат.

В силу (8.14) и равенства имеем

Подставив вместо в (8.15), получим

Так как и степени полиномов не больше то степени всех членов в (8.16), отличных от не превосходят

Ясно, что время работы алгоритмов 8.3 и 8.1 оценивается схожим образом, если рассматривать две меры сложности (соответственно арифметическую и битовую). Аналогично можно показать, что и другие оценки времени, установленные в разд. 8.2, переносятся

на полиномы, если вместо битовых шагов рассматривать арифметические. Таким образом, верна следующая теорема.

Теорема 8.7. Пусть и арифметические сложности соответственно умножения, деления, обращения и возведения в квадрат полиномов от одной переменной. Все эти функции равны с точностью до постоянных множителей.

Доказательство. Аналогично доказательству теоремы 8.5 и результатов, на которые оно опирается.

Следствие. Полином степени можно разделить на полином степени за время

Доказательство. В силу теоремы 8.7 и следствия 3 теоремы 7.4.