ния многочленов А(х) и В(х) в точках, являющихся корнями степени 2га из единицы.

3.Поточечное умножение. Поточечно умножить полученные значения многочленов А(х) и В(х) друг на друга. В результате получаются значения многочлена С(х) = А(х)В(х) в корнях степени 2га из единицы.

4.Интерполяция. Получить коэффициенты многочлена С(ж) при помощи обратного быстрого преобразования Фурье, примененного его значениям в корнях из единицы.

Шаги 1 и 3 требуют времени О(га), а шаги 2 и 4 - времени в (га lgra), как мы увидим в следующем разделе. Тем самым будет доказана следующая теорема:

Теорема 32.2

Произведение двух многочленов степени меньше га может быть вычислено за O(ralgra) операций. (Многочлены на входе и выходе задаются векторами коэффициентов.)

Упражнения

32.1-1

Найдите произведение многочленов А(х) = 7х3 - х2 + х - 10 и В(х) = 8х3 - 6х + 3, используя формулу (32.2). 32.1-2

Значение многочлена А(х) степени меньше га в данной точке жо можно найти, разделив А(х) на многочлен (ж - жо) и получив частное q(x) (которое является многочленом степени меньше га - 1) и остаток г, для которых

А(х) = q(x)(x - жо) + г.

Ясно, что А(хо) = г. Покажите, как вычислить остаток г и коэффициенты многочлена q(x) за время О(га), если даны жо и коэффициенты многочлена А. 32.1-3

Многочлен А(х) = 5j=o азх3 задан набором своих значений в га отличных от 0 точках. Укажите га пар аргумент-значение, задающих многочлен Arev(x) = 2~j=o an-i-jX3 (Другими словами, надо указать га различных точек и найти значения многочлена Arev в этих точках.)

32.1-4

Покажите, как использовать формулу (32.5) для интерполяции за время 0(га2). (Указание: Сначала вычислите Па:(ж - хк), для вь1 числения j-oro слагаемого надо разделить полученный многочлен на (ж - Xj). См. упражнение 32.1-2.)

32.1-5

Почему не удаётся делить многочлены тем же методом, деля их значения поточечно? Рассмотрите отдельно случаи, когда многочлены делятся друг на друга нацело и и когда имеется остаток.

32.1-6

Рис. 31.3 32.2 Значения ш$,и>1,... ,и>1 на комплексной плоскости, где uig = е2тгг/8 - главное значение корня степени 8 из единицы.

Рассмотрим два множества, А и В, каждое из которых содержит га целых чисел в диапазоне от 0 до Юга. Мы хотим найти их декартову сумму (Cartesian sum) А и В, определяемую как

С = {х + у : х £ А п у е В}.

Заметьте, что С может содержать целые числа от 0 до 20га. Нас интересуют элементы множества С, а также их «кратности» (сколькими способами данный элемент можно получить, сложив элемент А с элементом В). Покажите, что эта задача может быть решена за время в (га lgra). (Указание: представьте А и В многочленами степени не больше Юга.)

32.2 Дискретное преобразование Фурье. Быстрый алгоритм В разделе 32.1 мы собирались использовать комплексные корни из единицы как точки, в которых вычисляются значения многочлена, и говорили, что вычисление значений в них и интерполяция проводятся за время О (га lgra). Мы сейчас объясним, как это делается с использованием дискретного преобразования Фурье и быстрого алгоритма его выполнения. Комплексные корни единицы

Комплексным корнем степени га из единицы (complex rath root of unity) называют такое комплексное число ш, что

Имеется ровно га комплексных корней степени га из единицы. Они имеют вид е2жгк1п для к = 0,1,... , га - 1. Вспоминая формулу для экспоненты комплексного числа, можно написать

еги = cos и + г sin и.

На рисунке 32.2 видно, что комплексные корни единицы равномерно распределены на окружности единичного радиуса с центром в нуле. Значение

ип = е2™1п(32.6)

называется главным значением корня степени га из единицы (the principal rath root of unity). Остальные корни из единицы являются его степенями.

Комплексные корни степени га из единицы образуют группу по умножению (см. раздел 33.3). Эта группа имеет ту же структуру, что и аддитивная группа (Zra, +), поскольку равенство oj™ = oj® = 1

j иj + k(j + k) mod n . i

показывает, что 0Jnn = un = Аналогично, ujn =

cj™-1. Докажем некоторые свойства корней из единицы.

Лемма 32.3 (Лемма о сокращении) Для любых целых га О, fc 0 и rf > О

32.7

Доказательство Согласно (32.6),

dk / 2iri/dn\dk

dn Vе)

2Tri/n\k

= LO,

n

к

Следствие 32.4

Для любого чётного га > О

,гг/2

= CJ2 = -1.

п

Доказательство

оставляется читателю в качестве упр. 32.2-1. Лемма 32.5 (Лемма о делении пополам)

Если га > 0 четно, то, возведя в квадрат все га комплексных корней степени га из единицы, мы получим все га/2 комплексных корней степени га/2 из единицы (каждый - по два раза).

Доказательство

тт-hк-\-п/2

Легко проверить, что корни Lon и ujn отличаются знаком и при возведении в квадрат дают одно и то же число иа = ип/2

Лемма о делении пополам позволит свести вычисление значений многочлена в корнях из единицы степени га к вычислению значений других многочленов в корнях из единицы степени га/2.

Лемма 32.6 (Лемма о сложении)

Для любого целого га 1 и неотрицательного целого к, не кратного га, выполнено равенство

Доказательство

По формуле (3.3) (которая верна и для комплексных чисел) имеем

(знаменатель не обращается в нуль, так как к не кратно га). Дискретное преобразование Фурье

Вспомним, что мы хотим вычислить значение многочлена

п-1

= о.

3=0

п-1