7.5. АЛГОРИТМ ШЕНХАГЕ — ШТРАССЕНА ДЛЯ УМНОЖЕНИЯ ЦЕЛЫХ ЧИСЕЛ

Теперь изучим важное приложение теоремы о свертке — алгоритм быстрого битового умножения целых чисел. В разд. 2.6 мы видели, как умножить два -разрядных двоичных числа за шагов, разбивая каждое двоичное число на два -разрядных числа. Этот метод можно обобщить, разбивая числа на блоков по разрядов в каждом. Если рассматривать эти блоков как коэффициенты полинома, получатся выражения, аналогичные тем, что встречались в (2.4). Чтобы определить коэффициенты произведения полиномов, вычисляем полиномы на некотором подходящем множестве точек, перемножаем найденные значения и интерполируем. Выбрав в качестве точек, в которых вычисляются полиномы, примитивные корни из единицы, можно воспользоваться преобразованием Фурье и теоремой о свертке. Сделав функцией от и применив рекурсию, можно умножить два -разрядных двоичных числа за Об

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

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

Допустим, что и положим если четно, и в противном случае. Пусть Заметим, что и I делится на без остатка. Первый шаг состоит в разбиении на блоков по I битов в каждом. Таким образом,

Произведение представимо в виде

где

или берем Член равен и включен только для симметрии.)

Произведение можно вычислить с помощью теоремы о свертке. Перемножение преобразований Фурье требует умножений. Применяя обернутую свертку, можно уменьшить число умножений до Именно по этой причине мы вычисляем по модулю Так как то Отсюда в силу (7.8) и леммы 7.6, взяв по модулю находим, что

где

Так как произведение двух -разрядных двоичных чисел меньше и -это суммы, составленные из таких произведений соответственно, то удовлетворяет неравенствам Следовательно, может принимать не более значений. Если мы сможем вычислить все по модулю то сможем вычислить по модулю сделав дополнительных шагов для сложения экземпляров с необходимыми сдвигами.

Чтобы вычислить все по модулю вычисляем эти дважды — по модулю и по модулю Пусть это по модулю это по модулю Так как степень числа 2, а число нечетно, то взаимно просты. Поэтому можно получить из по формуле

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

Значения по модулю вычисляются так: берем по модулю по модулю и формируем два -разрядных числа и как показано на рис. 7.7. Произведение вычисляется с помощью алгоритма из разд. 2.6 не более чем за шагов, т. е. менее чем за шагов. Далее,

Рис. 7.7. Изображение составных чисел, используемых при вычислении по модулю В каждом блоке, состоящем из нулей, содержатся нулей.

где Заметим, что так что все легко восстановить по произведению Тогда по модулю можно найти, вычисляя по модулю

Вычислив все по модулю вычисляем по модулю с помощью обернутой свертки. Для этого надо взять преобразование Фурье, выполнить попарные умножения и найти обратное преобразование. Пусть По теореме 7.5 элементы со и имеют обратные по модулю примитивный корень степени из единицы. Поэтому отрицательно обернутая свертка векторов где корень степени из единицы), где для Значения по модулю 24-1 можно получить соответствующим сдвигом. Весь алгоритм таков:

Алгоритм 7.3. Алгоритм Шёнхаге — Штрассена для умножения целых чисел

Вход. Два -разрядных двоичных целых числа , где Выход. -разрядное произведение по модулю Метод. Если мало, умножьте и на по модулю вашим любимым алгоритмом. Для большого положим если четно, и если нечетно. Пусть Представим и в виде в виде где целые числа между и 2—1 (т. е. числа это блоки, составленные из I разрядов числа аналогично блоки из I разрядов числа и).

1. Вычисляем преобразование Фурье по модулю векторов

берется в качестве примитивного корня степени из единицы.

2. Вычисляем по модулю покомпонентное произведение преобразований Фурье, нолученных на шаге 1, при помощи алгоритма 7.3, который рекурсивно применяется для вычисления

произведения каждой пары соответствующих компонент. (Ситуация, когда одно из чисел равно рассматривается как легкий частный случай.)

3. Вычисляем обратное преобразование Фурье по модулю вектора, равного покомпонентному произведению, полученному на шаге 2. Результатом будет вектор по модулю где обозначает компоненту отрицательно обернутой свертки векторов Вычисляем по модулю умножая по модулю

4. Вычисляем следующим образом.

(а) Пусть по модулю по модулю для

(б) Построим числа и 9, выписывая в цепочки числа и вставляя между ними нулей, т. е.

(в) Вычисляем произведение с помощью алгоритма из разд. 2.6.

(г) Произведение имеет вид где

Числа по модулю можно восстановить по этому произведению, вычисляя по модулю для

5. Вычисляем точные значения по формуле

учитывая, что лежит

6. Вычисляем по модулю Это и есть искомый результат.

Теорема 7.7. Алгоритм 7.3 вычисляет по модулю

Доказательство. По теореме 7.2 шаги 1—3 алгоритма 7.3 правильно вычисляют значения по модулю В качестве упражнения предлагаем доказать, что шаг 4 вычисляет по модулю а шаг по модулю т. е. точное значение

Теорема 7.8. Алгоритм 7.3 тратит Об времени.

Доказательство. В силу следствия теоремы 7.6 шаги 1—3 выполняются за время где

время умножения двух -разрядных двоичных целых чисел путем рекурсивного применения этого алгоритма. На шаге 4 формируются и умножаются числа и длины за Об шагов. Так как для достаточно большого то временем, затрачиваемым на шаг 4, можно пренебречь, ибо шаги 1 и 3 занимают Об времени. Шаги 5 и 6 занимают оба времени, так что и ими можно пренебречь. Поскольку то

для некоторой постоянной с и достаточно больших Пусть Тогда (7.9) можно записать в виде

Поскольку то

откуда следует, что при подходящем выборе постоянной с. Чтобы убедиться в этом, подставим в вместо Очевидные преобразования дадут неравенство

Для больших выполняется и потому

Для больших и для достаточно большой постоянной с первые три слагаемых не больше абсолютной величины четвертого, а оно отрицательно. Таким образом, Отсюда заключаем, что

УПРАЖНЕНИЯ

(см. скан)

(см. скан)

(см. скан)

Замечания по литературе

Кули, Льюис, Уелч [1967] указывают, что способ быстрого преобразования Фурье описан еще в книге Руиге, Кёнига [1924]. Его применяли Даниелсон, Ланцош [1942] и Гуд [1958, I960]. В фундаментальной работе Кули, Тьюки [1965] проясняется природа этого метода. Николсон [1971] дал алгебраическое описание для него. Трактовка БПФ как задачи деления полиномов, принятая нами, принадлежит Фидуччиа [1972]. Ввиду важности этого алгоритма для вычислений много внимания уделялось его эффективной реализации (см., например, работу Джентльмена, Санде [1966] и многочисленные статьи в сборнике под редакцией Рабинера, Рейдера [1972]). Алгоритм умножения целых чисел разработан Шёнхаге, Штрассеном [1971]. Упр. 7.18 и 7.19 взяты у Рейдера [1968].