Т5. [Выполнить рекурсию.] Величины

код-2, V{2r), U{2r), код-3, V{2r - 1), U{2r - 1), ...,

код-3, V{1), и{1), код-3, V{0), U{0)

поместить последовательно в стек С, одновременно освобождая стеки U и V. "Код-4" поместить в стек W. Вернуться к шагу ТЗ.

Т6. [Сохранить одно произведение.] (В этот момент алгоритм умножения сформировал в W одно из произведений W{j) = U{j)V{j).) Поместить w в стек W. (Число W содержит 2(д -I- qk-i) бит.) Вернуться к шагу ТЗ.

Т7. [Найти все а.] Присвоить г •<- г, g <- д, р <- qk-i + Як- (Сейчас в стек W последовательно от дна к вершине помещена последовательность чисел, оканчивающаяся W{0),W{1),... ,W{2r), где числа W{j) представлены как 2р-би-товые.)

Теперь для j = 1,2,3,..., 2г выполнить следующий цикл: для t = 2г,2г-1, 2г - 2,...,j присвоить W{t) <- {W{t) - W{t - (В цикле j должно

увеличиваться, а t - уменьшаться. Величина (И(0 - W{t- 1))/j всегда будет неотрицательным целым числом, занимающим 2р бит (см. табл. (16).)

Т8. [Найти все W(j).] Для j = 2г - 1,2г - 2,..., 1 выполнить следующий цикл: для = i, j + 1, • •, 2г - 1 присвоить W{t) <- W{t) - jW{t + 1). (В цикле j должно уменьшаться, а t - увеличиваться. Результатом этой операции снова будет неотрицательное целое число, занимающее 2р бит; см. табл. (18).)

Т9. [Сформировать ответ.] Сформировать в w 2{qk + д+О-битовое целое число (... (Ж{2г)2« + \У{2г - 1))2« + • • + 1У{1))2» + W{0).

Удалить W{2r), ..., 1У(0) из стека W.

Т10. [Возвратиться.] Присвоить к <- к + 1. Извлечь число из вершины стека С. Если это "код-3", перейти к шагу Т6. Если это "код-2", поместить w в стек W и перейти к шагу Т7. Закончить выполнение алгоритма, если это "код-Г {W является искомым результатом.)

Оценим время выполнения Т{п) алгоритма Т в некоторых единицах, называемых циклами, т. е. в количестве элементарных машинных операций. На выполнение шага Т1 уходит 0{qk) циклов даже в том случае, когда число qk представлено в виде длинной цепочки из бит, за которой следует некоторый разграничитель, так как qk +Як-1 -----Ь до равно 0{qk). Шаг Т2 вьшолняется за 0{qk) циклов.

Обозначим через tk объем вычислений, которые необходимо выполнить, чтобы от шага ТЗ перейти к шагу Т10 для некоторого конкретного значения к (после того, как в начале шага ТЗ значение к было уменьшено на 1). На выполнение шага ТЗ требуется не более 0{q) циклов. На шаге Т4 вьшолняется г умножений р-битовых чисел на lg(2r)-6HT0Bbix числа и г сложений р-битовых чисел. Все эти операции повторяются 0{rq\ogr) раз. Таким образом, общее количество циклов равно 0{rqlogr). На шаге Т5 вьшолняется перемещение Аг + 2 р-битовых чисел, и на каждой итерации перемещение повторяется 2г -Ь 1 раз. Для выполнения рекурсии, которая появляется, когда алгоритм повторяет сам себя (возвращаясь к шагу ТЗ), необходимо по tk-i циклов на каждой из итераций 2г + 1. На шаге Т7

требуется выполнить 0{г) вычитаний р-битовых чисел и делений р-битовых чисел на Ig(2r)-6HT0Bbie числа, на что затрачивается 0{rqlogr) циклов, как и на шаге Т8. Для шага Т9 необходимо 0{rq) циклов, а на выполнение шага Т10 время практически вовсе не затрачивается.

Суммируя, получаем Т{п) = 0{qk) + 0{qk) + tk-i, где (при q = qk и г = Гк) основной вклад во время выполнения алгоритма удовлетворяет равенству

tk = 0{q) + 0{rq\ogr) + 0{rq) + (2r + l)0{q) + Oirq\ogr)

+ Oirqlogr) + 0{rq) + 0{q) + (2r + l)tk-i

= 0{vq\ogr) + {2r+l)tk-i.

Следовательно, найдется константа с такая, что

tk < crlqklgTk + {2гк + l)tk-i-

Чтобы завершить оценку tk, докажем (довольно грубо), что для некоторой константы С

tk<Cqk+i2-"*K (20)

Выберем С > 20с, и пусть, кроме того, С настолько велико, что неравенство (20) справедливо для к < ко, где А;о будет уточнено ниже. Далее, для А; > А;о положим Qk =lgqk, Rk = Igrj:. По индукции имеем

tk < cqkrllgrk + {2rk+)Cqk2- = Cqk+i2{T]i + V2),

m = л,2«-2-5- < Rki-" < 0.05,

rj2 = (2 + lyMVO-Vo;) 2-1/" < 0.85,

так как

VoiTi-VQ~k = VQk + [y/Q~k\-VQ~k- \

при fc - 00. Отсюда следует, что можно найти fco, такое, что щ < 0.95 для всех fc > fco. На этом доказательство по индукции неравенства (20) завершается.

С учетом полученного результата теперь можно оценить Т{п). Поскольку п > qk-i + qk-2, то qk-i < п. Получаем

г, 1 = 2i-iJ < 2 и qk=rk-iqk-i<n2. Таким образом.

< Cgfc22- < c„2+2.5(vi+i) и, учитывая, что Т{п) = 0{qk) + tk-i, мы сформулировали следуюшую теорему.

Теорема В. Существует константа со, такая, что время выполнения алгоритма Т меньше, чем соп2- циклов.

Поскольку п2- = „i+3.5/v/Ig Qj, результат существенно сильнее, чем теорема А. Несколько усложнив алгоритм и распространив эти идеи вплоть до очевидных ограничений (см. упр. 5), можно улучшить время выполнения, добившись оценки

Г(п) = 0(n2/21ogn). (21)

*В. Модулярный метод. Существует еще один метод очень быстрого перемножения больших чисел, основанный на идеях модулярной арифметики, которые представлены в разделе 4.3.2. На первый взгляд, трудно поверить, что он может иметь какие-либо преимущества, так как алгоритм умножения, основанный на модулярной арифметике, кроме собственно операции умножения, должен включать процедуры выбора модуля и перевода чисел в модулярное представление и обратно. Несмотря на такие пугающие трудности А. Шёнхаге (А. Schonhage) обнаружил, что все эти операции можно очень быстро реализовать.

Чтобы лучше понять суть метода А. Шёнхаге, рассмотрим один частный случай- последовательность, определенную по правилам

90 = 1, Чк+1=гяк-1, (22)

так что Як = - 3~ - ... - i = 1(3*: -- i). Исследуем процедуру, выполняющ}Ю умножение р-битовых чисел, где рк = {18як + 8), в терминах метода умножения рй 1-битовых чисел. Итак, если известно, как умножать числа, состоящие из Ро = 26 бит, описываемая ниже процедура покажет, как умножать числа из pi = 44, 98, 260 бит и т. д., увеличивая количество битов почти в три раза на каждом шаге. При умножении р-битовых чисел идея состоит в использовании шести модулей:

mi = 2««*-1 - 1, тг = 2««+i - 1, тз = 2««+2 i т4 = 2б«*+з 1, т5 = 2««+5-1, = 24"+ - 1.

Эти модули взаимно просты согласно соотношению 4.3.2-(19), так как показатели степени в (23)

6qk-l, 6qk + l, 6qk + 2, 6qk+3, 6qk + 5, 6qk + 7 (24)

всегда взаимно просты (см. упр. 6). При помощи шести модулей в (23) можно представлять числа вплоть до m = т1т21Пгттьт > 2"+ = 2", и поэтому при умножении р-битовых чисел и и v возможность переполнения совершенно исключена. Таким образом, при А; > О можно использовать следующий метод.

a) Вычислить ui = и mod mi, ue = u mod me и Vi = i; mod mi, ve - V mod me.

b) Умножить щ на vi, иг на «г, ue на vq. Эти числа состоят не более чем из 6qk + 7 = 18qk-i + 1 < Pk-i бит, поэтому операции умножения могут быть выполнены при помощи процедуры, используемой для умножения р 1-битовых чисел.

c) Вычислить wi = UiVi mod mi, гиг = U2V2 mod тг, ..., We = щь mod me.

d) Вычислить w, такое, чтобы выполнялось неравенство О < w < т, w mod mi = wi, ..., w mod me = w-