Пусть время, требуемое для выполнения этого процесса, равно tk- Нетрудно заметить, что на выполнение операции (а) необходимо 0{рк) циклов, ибо определение umod(2 - 1) осуществляется совсем просто (подобно "выбрасыванию девяток"), как описано в разделе 4.3.2. Аналогично на операцию (Ь) уходит 0{рк) циклов. Остается операция (d), которая, на первый взгляд, требует выполнения сложных вычислений. Но Шёнхаге нашел оригинальный способ выполнения операции (d) за 0{pklogpk) циклов. В этом и состоит сущность предложенного метода. Как следствие имеем

tk =6tk-i+0{pk logPk)-

Так как рк = 3*+2 + 17, можно показать, что время, затрачиваемое на умножение п-битовых чисел, равно

Т(п) = 0(п°8зб) = о(п1-«31). (25)

(См. упр. 7.)

Хотя модулярный метод сложнее, чем описанная в начале этого раздела процедура, на выполнение которой требуется O(ns) циклов, в действительности время, затрачиваемое на умножение согласно формуле (25), существенно меньше времени 0{п) на умножение п-битовых чисел. Таким образом, используя один из совершенно разных методов, рассмотренных выше, можно усовершенствовать классический метод умножения п-битовых чисел.

Теперь проанализируем упомянутую выше операцию (d). Предположим, что дан ряд положительных попарно взаимно простых целых чисел ei < вз < • • • < е. Пусть

mi=2"-l, m2 = 2"-l, = 2"" - 1. (26)

Пусть также даны числа Wi, ..., Wr, такие, что О <Wj < rrij. Задача состоит в том, чтобы определить двоичное представление чисел w, удовлетворяющих условиям

О < W < mim2 ... гПг,

(27)

W = wi (по модулю mi), ..., w = Wr (по модулю Шг).

Метод основан на использовании соотношений (24) и (25) из раздела 4.3.2. Вычислим* сначала

wj = {... {{wj - w[) cij - Ц) C2j-----Wj i) C(j i)j mod mj (28)

для j = 2, ..., r, где ml = Wi mod mi. Затем вычислим

w = {... {wTn i + tUr-i) +----h Ц) mi -b tuJ. (29)

В этом равенстве су -такое число, что Cy-mi = 1 (по модулю rrij); числа Cjj должны быть определены по числам ej.

При любых j для вычисления по формуле (28) требуется (j) операций сложения по модулю rUj, на каждую из которых затрачивается 0{ег) циклов, плюс {) операций умножения на c,:j по модулю rrij. Вычисление w по формуле (29) требует г операций сложения и г операций умножения на rrij. Но операция умножения на TUj выполняется легко, ибо это просто сложение, вычитание и сдвиг, поэтому ясно, что на выполнение вычислений по формуле (29) затрачивается 0{гег) циклов. Как вскоре будет видно, каждая операция умножения на Cjj по модулю rrij требует

для выполнения только 0(6 loge) циклов, а потому весь процесс перехода можно выполнить за 0{гег loge) циклов.

После этого остается решить следующую задачу. Для заданных положительных целых чисел е и / (е < /) и неотрицательного целого числа и < 2 найти значение (си) mod (2/ - 1), где число с таково, что (2* - 1)с = 1 (по модулю 2-1), причем вычисления должны быть выполнены за 0{/log/) циклов. В ответе к упр. 4.3.2-6 приведена формула для с, которая наводит на мысль о необходимости использовать здесь ту же процедуру. Прежде всего найдем наименьшее положительное целое число Ь, такое, что

бе = 1 (по модулю /). (30)

При помощи алгоритма Евклида это можно сделать за 0((log/)) циклов, так как данному алгоритму для обработки чисел ей/ требуется 0{log/) итераций и каждая итерация вьшолняется за 0((log/)2) циклов. Число b можно было бы найти и путем простого перебора, не изменяя общее время выполнения, а просто применяя 6=1,2 и т. д. до тех пор, пока не будет удовлетворяться (30). Этот процесс существенно не сказывается на общем времени выполнения, поскольку на него потребовалось бы всего 0(/log/) циклов. После того как b найдено, в силу упр. 4.3.2-6 имеем

с = с[Ь] = ( Y1 2J - 1). (31)

Прямого умножения (си) mod {2 - 1) может оказаться недостаточно для решения задачи, потому что нам неизвестно, как умножить /-битовые числа общего вида за 0(/log/) циклов. Но специальная форма числа с дает ключ к решению: двоичное представление числа с имеет некоторую регулярную структуру битов, и из формулы (31) видно, что число с[26] может быть простым способом получено из числа с[Ь]. Это свойство наводит на мысль, что можно быстро умножить число и на с[Ь], если подходящим образом получить число с[Ь]и за lg6 шагов. Например, это можно выполнить следующим образом. Пусть в двоичной системе счисления число b имеет вид

Ь= {bs.. .626160)2-

Можно вычислить четыре последовательности чисел а, dk, Uk, Vk, которые определены правилами

(32)

Индукцией no A; легко доказать, что

йк = (2*е) mod /; Uk = (c[2*]u) mod (2 - 1);

dk = {{bk ... 6160)2 e) mod /; Vk = {c[{bk .. 6160)2]) mod (2 - 1).

(33)

Следовательно, искомый результат (c[6]u) mod (2 - 1) будет равен v,. Для вычисления ак, dk, Uk ч Vk по ak-i, dk-i, Uk-i, Vk-i требуется O(log/) + 0(log/) 4-

0(/) + 0{f) = 0{f) циклов, поэтому весь объем вычислений можно выполнить, как и требовалось, за sO{f) = 0(/log/) циклов.

Тщательный анализ оригинального метода, представленного формулами (32) и (33), принесет читателю много пользы. Подобные методы рассматриваются в разделе 4.6.3.

В работе Шёнхаге, опубликованной в Computing 1 (1966), 182-196, показано, что эти идеи могут быть распространены на операции умножения п-битовых чисел с использованием модулей г и 2", в результате чего будет создан метод, аналогичный алгоритму Т. Мы не будем здесь останавливаться на деталях этого метода, поскольку алгоритм Т всегда имеет приоритет. К тому же сейчас будет рассмотрен еще лучший метод.

С. Умножение при помощи дискретного преобразования Фурье. Основной проблемой при умножении с высокой точностью является вычисление "свертки", например

UrVo + Ur-lVi Н-----h UoVr, (34)

а между свертками и важным математическим понятием, называемым "преобразование Фурье", имеется тесная связь. Если ui - exp{2ni/K) есть корень К-й степени из единицы, то можно определить одномерное преобразование Фурье последовательности комплексных чисел {uo,ui,... ,Uf(-i) как последовательность (uo,ui,... ...,UK-i), где

Us= "t 0<s<K. (35)

0<f<A-

Положив, что {vo,vi,...,vii-\)-такое же преобразование Фурье для последовательности {vo,vi,... ,Vf(-i), нетрудно заметить, что {uoVo,uiVi,... ,uii-iVK-\) будет преобразованием Фурье для {wo,wi,.. .,wii-i), где

Wr = UrVo + Ur-lVi +----h UoVr + Uf(-lVr+l +----h Ur+lVK-1

UiVj. (36)

i-{-j~r (no модулю К)

В случае, когда К > 2п - 1 и Un = Un+\ = • • • = ик-\ = Vn = Vn+i = • • • = Vfc-i = О, числа w -это как раз то, что необходимо для операции умножения, поскольку в (36) члены Uf(-iVr+i + + Ur+iVf(-i при О < г < 2п - 2 исчезают. Другими словами, преобразование от свертки есть обычное произведение преобразований компонентов. Это частный случай идеи Тоома, связанной с использованием полиномов (см. выражения (9) и (10)), причем X заменяется корнями из единицы.

Для К, равного степени 2, дискретное преобразование Фурье (35) может быть получено очень быстро, если вычисления выполняются в определенной последовательности; именно таким образом выполняется обратное преобразование Фурье (определение чисел wu3w). Такое свойство преобразования Фурье было использовано в 1968 году Ф. Штрассеном (V. Strassen), который предложил способ умножения больших чисел, более быстрый, чем это было возможно с использованием любых известных к тому времени методов. Позже вместе с Шёнхаге он уточнил метод и опубликовал модифицированные алгоритмы в Computing 7 (1971), 281-292. Похожие идеи, но для произвольных целых чисел, были независимо от Ф. Штрассена