многочленов степени меньше га, требующих времени О(га1о&3). (Можно делить коэффициенты многочлена на старшую и младшую половины, а можно разделять коэффициенты при чётных и нечётных степенях.)

с. Покажите, как можно умножить два га-битных целых числа за O(ralog2 3) шагов, считая, что на каждом шаге обрабатывается 0(1) битов.

32-2 Теплицевы матрицы

Теплицевой матрицей (Toeplitz matrix) называется матрица А = (aij) размера га X га, для которой a8j = a8 i j i для г = 2, 3,... , га и j = 2,3,... ,га.

a.Обязательно ли сумма двух теплицевых матриц является теплицевой? А произведение?

b.Опишите, как представить теплицевы матрицы так, чтобы две теплицевы матрицы размера га X га можно было сложить за время О (га).

c.Напишите алгоритм умножения теплицевой матрицы размера га X га на вектор длины га за время О (га lg га) (используя представление пункта Ь).

d.Напишите эффективный алгоритм умножения двух теплицевых матриц размера га X га и оцените его время работы.

32-3 Вычисление значений всех производных многочлена в точке Многочлен А(х) степени меньше га задан своими коэффициентами (ao, ai,... , ara i). Мы хотим найти его значение вместе со всеми производными в заданной точке xq.

а. Пусть известны коэффициенты bo, Ь\,... , Ъп-\ в представлении многочлена А(х) по степеням (ж - ж0):

A(x) = J2b3

1=0

ХоУ,

Как тогда найти значение многочлена А(х) и всех его производных в точке жо за время 0(га)?

b.Объясните, как найти Ьо,Ь\,... ,Ъп-\ за время O(ralgra), если известны значения А(хо + oj%) при к = 0,1,... , га - 1.

c.Докажите, что

3=0

"/(-/)! при -(га- 1)/0, при 1 / (га - 1).

d. Объясните, как вычислить А(хо -\->кп) для к = 0,1,... , га - 1 за время О (га lgra). Покажите, что все производные многочлена А(х) в точке жо можно вычислить за время О (га lgra).

32-4 Вычисление значений многочлена в нескольких точках

Мы видели, что значение многочлена в точке можно найти за время О (га), используя схему Горнера. Кроме того, мы знаем, что с помощью быстрого преобразования Фурье можно найти значения многочлена в га комплексных корнях из единицы за время 0(ralgга). Сейчас мы покажем, как вычислить значения многочлена степени меньше га в га любых точках за время 0(ralg2 га).

При этом мы используем (без доказательства) тот факт, что можно найти остаток от деления одного многочлена на другой за время О (га lgra). Например, остатком от деления Зж3 + ж2 - Зж + 1 на ж2 + ж + 2 равен

га точкам жо, х\,... , жга 1 мы хотим найти га значении А(хо), A(xi),... , А(хп-\). Для Oijra- 1 определим многочлены Pij(x) = Ylk=i(x - хк) и Qij = А(х) mod Pij(x). Заметьте, что степень Qij(x) не больше j - г.

а.Докажите, что А(х) mod (ж - z) = A(z) для любой точки z.

б.Докажите, что Qkk(x) = А(хк) и что Qo,n-i(x) = А(х).

в.Докажите, что Qik{x) = Qij(x) mod Ргк{х) и Qk](x) = QtJ(x) mod Pkj(x) для i к j.

г.Укажите алгоритм, вычисляющий A(xo), A(xi),... , A(xn i) за время 0(ralg2 ra).

32-5 Быстрое преобразование Фурье в кольце вычетов

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

В этом случае можно использовать вариант преобразования Фурье, использующий кольцо вычетов (в котором вычисления проводятся точно). Мы уже видели (упр. 32.2-6), что возможно использование вычетов размером Г2(га) битов для работы с га-точечным дискретным преобразованием Фурье. В этой задаче рассматривается более практичный подход, использующий i7(lg га)-битовую арифметику вычетов, (мы используем материал главы 33).

Предполагается, что число га есть степень 2.

а. Будем искать наименьшее к, для которого число р = кп + 1 - простое. Найдите простой эвристический довод в пользу того,

(Зж3 + ж2 - Зж + 1) mod (ж2 + ж + 2) = 5ж - 3.

По коэффициентам многочлена

Еп - 1к

к=0 акхК и

что к примерно равно lg га. (Значение к может оказаться сильно большим или меньшим, но есть основания ожидать, что в среднем потребуется проверить O(lgra) кандидатов на роль к.)

Пусть g является образующей группы Z* и w = gk mod p.

b.Покажите, что дискретное преобразование Фурье и обратное к нему можно корректно определить для операций по модулю р, используя w в качестве главного значения корня степени га из единицы.

c.Убедитесь, что быстрое преобразование Фурье и обратное к нему можно выполнить в кольце вычетов по модулю р за время О (га lgra), если считать, что операции над 0(lg га)-битовыми числами выполняются за единичное время. (Считайте р и w известны-

d. Вычислите дискретное преобразование Фурье вектора (0,5,3,7,7,2,1,6), используя вычисления по модулю 17. Заметьте, что g = 3 является генератором Z*7.

Замечания

Пресс, Флэнери, Тьюкольски и Веттерлинг (Vetterling) [161, 162] дают хорошее описание быстрого преобразования Фурье и его приложений. Хорошее введение в теорию обработки сигналов (область, где быстрое преобразование Фурье применяется чаще всего) написали Оппенгейм и Уилски [153].

Обычно изобретение метода быстрого преобразования Фурье в 1960-х годах связывают с именами Кули и Тьюки [51]. На самом деле этот метод неоднократно встречался и раньше, но его важность стала очевидной лишь с появления современных цифровых вычислительных машин. Пресс, Флэнери, Тьюкольски и Веттерлинг указывают, что этот метод знали Рунге (Runge) и Кёниг (Konig) ещё в 1924 году.