А. Цифровые методы. Ответ на поставленный вопрос звучит довольно неожиданно- "Нет". И в самом деле, нетрудно понять, почему. Для удобства будем далее полагать, что мы оперируем числами, выраженными в двоичной системе счисления. Два 2п-битовых числа и = (u2n-i • • гц"о)2 и и = {v2n-i ViVo)2 можно записать в виде

и = 2"t/i + Uo, v = 2"! + Vo, (1)

где Ui = (u2n-i. • • Un)2 - "наиболее значимая половина" числа и и Uo= {un-i - "0)2 - "наименее значимая половина" числа и. Аналогично Vj = (u2n-i • • • Vn)2 и Vo = (vn-i ...vo)2- Тогда

uv = (2" + 2")t/iri + 2"(?7i - UoWo - Ki) -f (2" + l)UoVo. (2)

Эта формула сводит задачу умножения 2п-битовых чисел к трем операциям умножения п-битовых чисел UiVi, {Ui - Uo){Vo - Vi) и UoVq и выполнению некоторых простых операций сдвига и сложения. Формула (2) пригодна и для умножения чисел с удвоенной точностью, когда требуется получить результат с учетверенной точностью. На многих компьютерах это реализуется немного быстрее, чем умножение традиционными методами. Но главное преимущество формулы (2) заключается в том, что ее можно использовать для определения рекурсивного процесса умножения, который значительно быстрее при больших п уже знакомого метода, имеющего время выполнения порядка п. Если Т{п) - время, затрачиваемое на выполнение умножения п-битовых чисел, то для некоторой константы с имеем

Г(2п) < ЗТ(п) + СП, (3)

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

Т(2*) < с(3* - 2"), к>1, (4)

если выбрать константу с достаточно большой, чтобы данное неравенство выполнялось при к = 1; поэтому имеем

Т(п) <Т(28"1) <с(38"1 -2Г8п1) <3с.з8" = 3сп83. (5)

Из соотношения (5) видно, что время порядка п, затрачиваемое на выполнение операции умножения, можно сократить до величины порядка п « п-*, так что рекурсивный метод при больших п обеспечивает гораздо более высокую скорость, чем традиционный. В упр. 18 рассмотрено применение этого метода.

(Похожий, но немного более сложный метод умножения со временем выполнения порядка был впервые предложен А. Карацубой в ДАН СССР 145 (1962), 293-294. Любопытно, что эта идея, по-видимому, до 1962 года не была известна; нет сведений о том, чтобы кто-нибудь из "вундеркиндов-счетчиков", прославившихся своими способностями умножать в уме большие числа, применял когда-либо подобный метод, хотя аналог формулы (2) для десятичной системы счисления, казалось бы, дает довольно легкий способ умножения в уме восьмизначных чисел.)

В пределе при п, стремящемся к бесконечности, время выполнения можно сократить еще больше, если учесть, что рассмотренный только что метод является

частным случаем г = 1 более общего метода, который для произвольного фиксированного г дает

Т((г -Ь 1)п) < (2г + 1)Т(п) + СП. (6)

Этот более общий метод можно получить следующим образом. Разобьем

и = (u(r+i)„-i... щио)2 и v = (г;(г+1)„ 1.. • t;it;o)2 на г -Ь 1 частей

u = Ur2 + --- + Ui2" + Uo, и = V;2" + --- + ri2" +Vo, (7)

где каждое Uj и каждое Vj является п-битовым числом. Рассмотрим полиномы

U{x) = UrX + --- + Uix + Uo, V{x) = VrX + --- + Vix + Vo (8)

и положим

Wix) = и{х)У{х) = W2rX + • • • + Wix + Wo. (9)

Так как и = t/(2") и v = V(2"), получаем uv = W(2"), поэтому при известных коэффициентах Wk в W{x) можно легко вычислить ш. Задача заключается в поиске хорошего способа вычисления этих коэффициентов в W(x), требующем только 2r-t-l умножений п-битовых чисел и несколько последующих операций, время выполнения которых пропорционально п. Это может быть достигнуто посредством вычисления

ЩО)Г(О) = W(0), = С/(2г)Г(2г) = W(2r). (10)

Коэффициенты полинома степени 2г могут быть выражены в виде линейной комбинации значений этого полинома в 2г -t-1 различных точках. Время, необходимое для выполнения этой операции, пропорционально п или меньше. (В действительности произведения t(i)(i) не являются в строгом смысле произведениями п-битовых чисел, но являются произведениями (п -f- *)-битовых чисел, где t есть фиксированное значение, зависящее от г. Программа умножения (n-f -битовых чисел строится легко. Для ее выполнения требуется лишь Т(п) -t-cin операций, где Т(п)-количество операций, необходимых для умножения п разрядов, так как при фиксированном i два произведения t- и п-битовых чисел можно получить за сп операций.) Таким образ.ом, получаем метод умножения, для которого выполняется неравенство (6).

Рассуждая так же, как при выводе неравенства (5), и учитывая неравенство (6), приходим к неравенству Т(п) < сзп°8-+(2+) < сзп"°-+2. Итак, доказана следующая теорема.

Теорема А. Для любого б > О существуют такая постоянная с{е) и такой алгоритм умножения, что число элементарных операций Т{п), которые необходимо выполнить, чтобы перемножить два п-битовых числа, удовлетворяет оценке

Т{п) < c(6)nl+ I (И)

Данная теорема - это еще не тот результат, который нам нужен, Для практических целей он неудовлетворителен, так как метод резко усложняется, когда б - О (т. е. г - оо). Это приводит к столь быстрому росту cic), что приходится иметь дело с очень большими значениями п прежде, чем будут внесены какие-либо существенные улучшения в соотношение (5). Теорема неудовлетворительна и с

теоретической точки зрения, так как в ней не в полной мере используется лежащий в ее основе полиномиальный метод. Если предположить, что г варьируется вместе с п, то, выбирая по мере увеличения п все большие и большие значения г, можно получить лучший результат. Эта идея предложена А. Л. Тоомом [ДАН СССР 150 (1963), 496-498]. Тоом использовал ее для доказательства того факта, что при возрастающем п можно построить автомат для умножения п-разрядных чисел, состоящий из довольно малого числа компонентов.

Позднее С. А. Кук (S. А. Cook) в работе On the Minimum Computation Time of Functions (Thesis, Harvard University, 1966), 51-77, показал, как применить идею Тоома для ускорения работы компьютерных программ.

Прежде чем продолжить обсуждение алгоритма Тоома-Кука, рассмотрим простой пример перехода от U{x) и V{x) к коэффициентам функции W{x). На этом примере нельзя огцутить эффективность метода, поскольку используемые в нем числа слишком малы. Но пример демонстрирует полезные упрощения, которые можно применять и в общем случае. Предположим, что нужно умножить и = 1234 на и = 2341 или в двоичной системе счисления число

и = (0100 1101 0010)2 на число v = (1001 0010 0101)2- (12)

Пусть г = 2. Полиномы U{x) и V{x) в (8) имеют вид

U{x) = 4x2 13д. 2, V{x) = 9х + 2х + 5.

Отсюда находим для W{x) = U(x)V(x):

?7(0)= 2, \J{\)= 19, Щ2)= 44, t/(3)= 77, t/(4) = 118; У(0)= 5, У(1)= 16, V{2)= 45, V{Z)= 92, F(4) = 157; W(0) = 10, W(X) = 304, W{2) = 1980, W{3) = 7084, И(4) = 18526. (13)

Теперь нужно найти пять коэффициентов полинома W(x), используя пять последних величин.

Чтобы найти коэффициенты полинома W{x) = Wm-ix" -t- •• -f Wx -t- Wq при заданных значениях И(0), W(l), ..., W{m - 1), можно воспользоваться одним интересным алгоритмом. Сначала запишем

W{x) = ат-1 а;- + а„ 2 х + • • • + Oix + ао, (14)

где х- = х{х - 1)... (х - /с-t-1), а коэффициенты uj неизвестны. Полиномы вида (14) обладают важным свойством:

W{x + 1) - W{x) = {т - 1)ат-1 + (т - 2)а„ 2х + • • + ai; отсюда по индукции получаем, что для всех к >0

(wix+k) - (W(x + A-1) + (Wix + k-2) - + (-l)*W(x)