(57)

Zq + Zi + Z2-\r <

(58)

команду машине M2 начать умножение последовательности (1x2,иг), (из,Уз), а М2 в конечном итоге дает команду машине Мз выполнить умножение (1x4, U4), (1x5, Us) и т. д. К счастью, этот процесс выполняется без потери времени. Дальнейшие подробности читатель может почерпнуть из приводимого ниже формального описания.

Любой автомат может принимать 2 состояний (с, Xq, уо, xi, yi,x, у, Z2, Zi, Zq), где О < с < 4 и каждое из х, у и z равно либо О, либо 1. Первоначально все устройства находятся в состоянии (0,0,0,0,0,0,0,0,0,0). Предположим, что при j > 1 в момент t машина Mj находится в состоянии (с,хо,уо,xi,yi, х,у, 22, Zj, Zq), ее соседка слева Mj-i находится в состоянии (с*,Xq,у,х[,y[,x,y,Z2,Zi,Zq), а соседка справа Mj+i -в состоянии {c,XQ,yQ,xl,yl,x,y,Z2,zl,ZQ). Тогда машина Mj перейдет в момент t+lB состояние {c,xo,yo,x[,y[,x,y,z2,z[,Zo), где

с = min(c + 1, 3), если с = 3, иначе 0;

{хо,уо) = {х,у), еслис = 0, иначе (хо,уо);

{xi,yi) = (х,у), еслис=1, иначе {xi,yi);

(х,у) = {х,у), если с > 2, иначе {х,у);

(22 2х 20)2-двоичная запись для

ху при с = 0; хоу + хуо при с = 1; хоу + a;i2/i -f хуо при с = 2;

Хоу + Х1У + ху1 + хуо при с = 3.

Крайняя слева машина Mi ведет себя почти так же, как и все остальные. Она функционирует так, как если бы в момент поступления (u,v,q) на ее вход слева от нее находилась машина в состоянии (3,0,0,0,0, и, v, q, 0,0). Выход всей конфигурации - компонента Zq машины Mi.

Пример такой конфигурации, работающей с вводом

u=v = {... 00010111)2, 9 = (• • • 00001011)2,

приведен в табл. 2. Выходная последовательность дается в нижней части состояний машины Ml:

О, 0,1,1, 1,0, О, 0,0,1,0,...,

что представляет собой число (... 01000011100)2, прочитанное справа налево.

В основу описанной конструкции положена похожая конструкция, предложенная А. Дж. Атрубиным (А. J. Atrubin) и описанная в IEEE Trans. ЕС-14 (1965), 394-399.

Скорее всего, итеративная конфигурация оптимальна только в том случае, когда входные биты появляются последовательно. Если же они появляются одновременно, то следует предпочесть параллельные схемы реализации, которые вычисляют произведение двух п-битовых чисел после 0(log п) задержек. Эффективные схемы такого рода описаны, например, К. С. Уоллесом (С. S. Wallace) в IEEE Trans. ЕС-13 (1964), 14-17, и Д. Э. Кнутом (D. Е. Knuth) в The Stanford GraphBase (New York: ACM Press, 1994), 270-279.

Ш. Виноград (S. Winograd) [JACM 14 (1967), 793-802] исследовал минимальное время умножения, достижимое в логической цепи, когда п задано и когда входные

данные поступают одновременно в произвольно закодированном виде. Аналогичные вопросы для случая, когда операции умножения и сложения должны поддерживаться одновременно, исследованы в работах А. С. Yao, STOC 13 (1981), 308-311; Mansour, Nisan and Tiwari, STOC 22 (1990), 235-243.

Умноженье - мое раздраженье, И деленье - совсем не песня: Золотое правило вызывает смятенье. Ну а практика просто бесит! - ИЗ РУКОПИСНОЙ КОЛЛЕКЦИИ дж. о. ХЭЛЛИУЭЛЛА (J. о. HALLIWELL) (с. 1570)

УПРАЖНЕНИЯ

1. [22] Идея, выраженная в неравенстве (2), при замене основания 2 основанием 10 может быть обобщена для десятичной системы. Используя это обобщение, вычислите произведение чисел 1234 и 2341 (сведите это произведение четырехзначных чисел к трем произведениям двузначных чисел, а каждое из последних-к произведениям однозначных чисел).

2. [М22] Докажите, что если на шаге Т1 алгоритма Т присвоить R <- [\/Q\, то значение R останется неизменным или увеличится на единицу. (Поэтому, как было отмечено при описании данного шага, нет необходимости вычислять квадратный корень.)

3. [М22] Докажите, что последовательности qk иг*,, определенные в алгоритме Т, удовлетворяют неравенству 2"+(2га,) < 2"-+" при к > 0.

► 4. [28] (К. Бейкер (К. Baker).) Покажите, что полином W{x) лучше вычислять в точках X = -г, ..., О, ..., г, чем в неотрицательных точках х = О, 1, ..., 2г, как это делается в алгоритме Т. Полином U{x) можно записать в виде

Щх) = Ueix) + xUoix).

Полиномы V{x) и W{x) могут быть выражены аналогично. Покажите, как использовать эту идею для повышения скорости вычислений на шагах Т7 и Т8.

► 5. [35] Покажите, что если на шаге Т1 алгоритма Т вместо Л <- [VQi присвоить R <- fVQ.l + 1 при соответствующих начальных значениях величин qo, qi, Го и п, то оценку (20) можно улучшить до tk < qfc+i2(Igqt+i).

6. [М23] Докажите, что шесть чисел в уравнении (24) попарно просты.

7. [М23] Докажите (25).

8. [М20] Истинно ли следующее утверждение: можно игнорировать бит, обратный (в* 1,..., во) (во,. • , «*-i) в (39), так как обратное преобразование Фурье в любом случае снова обратит биты.

9. [Afi5] Предположим, что в методе преобразования Фурье, изложенном в разделе, во всех случаях параметр ш заменяется на w, где q - некоторое фиксированное целое число. Найдите простую связь между числами (йо, ui,..., ), вычисленными при помощи обобщенного преобразования Фурье, и числами (йо, ui,..., йк-i), полученными при q = I.

10. [М26] В процессе вычислений по алгоритму умножения Шёнхаге-Штрассена значений us и t)s после масштабирования в (43) становится ясно, что все комплексные числа А\ вычисленные при выполнении прохода j подпрограммы преобразования, будут по абсолютной величине меньше 2~. Покажите, что при выполнении третьего преобразования Фурье (вычисленииi&r) все значения А- будут по абсолютной величине меньше 1.

► 11. Сколько должно быть автоматов в линейной итерационной конфигурации, определяемой (57) и (58) при фиксированном значении п, чтобы можно было вычислить произведение п-битовых чисел? (Заметим, что на автомат Mj влияет только компонента Zq машины, расположенной справа, поэтому можно убрать все автоматы, компонента zq которых всегда нулевая для любых п-битовых чисел.)

► 12. [М41] (А. Шёнхаге (А. Schonhage).) Назначение данного упражнения - доказать, что простая форма машины с указателем (разделяющей точкой) может выполнить умножение п-битовых чисел за 0{п) шагов. В машине отсутствуют встроенные возможности реализации арифметики; все, что она делает, - работает с указателями и узлами. Каждый узел имеет одно и то же конечное число полей связи, и имеется конечное множество связующих регистров. Операции, которые эта машина может выполнять, перечислены ниже:

i) считывание одного входного бита; если этот бит равен О, то выполнение перехода;

ii) вывод О или 1;

iii) загрузка в регистр содержимого другого регистра или содержимого поля связи узла, на который указывает регистр;

iv) сохранение содержимого регистра в полях связи узла, на который указывает регистр;

v) переход в случае равенства двух регистров;

vi) создание нового узла и формирование в регистре указателя на него;

vii) остановка процесса.

Эффективно реализуйте метод преобразования Фурье на такой машине. [Указание. Покажите сначала, что для любого положительного N можно создать N узлов, представляющих целые числа {0,1,..., N-1], причем узлы, которые представляют числа р, имеют указатели на узлы, представляющие числа р + 1, [р/2] и 2р. Такие узлы могут быть созданы за 0{N) шагов. Покажите, что в этом случае арифметика по основанию N моделируется легко. Например, чтобы найти узел для (p+q) mod N и определить, являются ли р+д > N указателями на р и д, такой арифметике потребуется 0(jog N) шагов. Кроме того, операция умножения может быть смоделирована за 0(Iog N) шагов. Рассмотрим теперь алгоритм, приведенный в тексте раздела, при k = l,m = 6kKN = 2", так что все величины д.пя арифметики в формате с фиксированной точкой представляются 13-разрядными целыми числами по основанию N. Таким образом, покажите, что каждый проход быстрого преобразования Фурье может быть реализован за 0{К + (NlogN)) = 0{К) шагов с использЪванием следующей идеи. Каждая из К требуемых операций присвоения может быть "скомпилирована" для имитируемого компьютера наподобие MIX в виде ограниченного списка команд. При этом размер слова машины равен N, а команды для К машин, выполняющих операции параллельно, можно промоделировать за 0{K+{NlogN)) шагов при условии, что команды рассортированы таким образом, что все идентичные команды выполняются вместе. (Две команды идентичны, если у них одинаковый код, одинаковое содержимое регистров и операнды расположены в одинаковых ячейках памяти.) Обратите внимание на то, что N = 0(п*), а потому (NlogN) = 0{К).]

13. [М25] (А. Шёнхаге.) Основываясь на результатах этого раздела для m = п, получите хорошую верхнюю оценку для времени, необходимого, чтобы умножить т-битовое число на п-битовое число в случае, если оба числа очень большие, но число п значительно больше числа т.

14. [М42] Напишите программу реализации алгоритма Т с учетом сделанных в упр. 4 усовершенствований. Сравните ее с программой, разработанной для алгоритма 4.3.1М, и с программой, основанной на использовании (2), чтобы увидеть, насколько большим должно быть число п, чтобы проявилось усовершенствование алгоритма Т.