7.4. ПРОИЗВЕДЕНИЕ ПОЛИНОМОВ

Задача умножения двух полиномов от одной переменной по существу совпадает с задачей нахождения свертки двух последовательностей, а именно

Как и раньше, и считаются нулями, если или Напомним, что коэффициент должен быть нулем. Поэтому имеем дополнительные следствия теоремы 7.4.

Следствие 3 теоремы 7.4. Коэффициенты произведения двух полиномов степени можно вычислить за шагов.

Доказательство. В силу следствия 1 теоремы 7.4 и соображений, приведенных выше.

Следствие 4 теоремы 7.4. Допустим, что произведение двух k-paзрядных двоичных целых чисел можно вычислить за шагов. Пусть

и целые числа между и со для всех степени числа 2. Тогда коэффициенты полинома можно вычислить за шагов.

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

Снова заметим, что в следствии 4 доминирует вторая величина.

Фактически теорема 7.1 допускает такую интерпретацию. Предположим, что полиномы степени Можно вычислить полиномы в любых или более точках, скажем затем перемножить чтобы получить значения в тех же точках. По этим значениям можно интерполяцией построить единственный полином степени Он и будет произведением

Когда преобразование Фурье применяют к вычислению свертки (или, что эквивалентно, к умножению полиномов), выбирают где — примитивный корень степени из единицы. Далее находят преобразования Фурье полиномов (т. е. вычисляют в точках попарно перемножают результаты этих преобразований (т. е. умножают на чтобы получить значение произведения в точке и вычисляют применяя обратное

преобразование. Лемма 7.1 гарантирует, что это обращение на самом деле дает формулу для интерполяции. Иными словами, мы действительно восстанавливаем полином по его значениям в точках