Rl. [Начальное приближение.] Присвоить z <- i-[32/(4ui + Ivi + из)] и fc <- 0.

R2. [Итерация по Ньютону.] (Здесь имеем число z в двоичном виде [хх.хх.. .x)i с 2* + 1 знаками после разделяющей точки и 2 < 2.) При помощи программы быстрого умножения точно вычислить 2 = (ххх.хх... х),. После этого точно вычислить VifcZ, где Т4 = (0.uiU2. •. г2+1+з)2- Затем присвоить z <-22 - Vk +где г, удовлетворяющее неравенству О < г < 2~2 -i прибавляется при необходимости для округления 2, чтобы 2 было кратным 2" -i. И наконец присвоить fc <- fc + 1.

R3. [Завершено?] Если 2* < п, то вернуться к шагу R2; в противном случае выполнение алгоритма заканчивается.

Этот алгоритм основывается на алгоритме, предложенном С. А. Куком (S. А. Cook). Похожий алгоритм использовался при разработке арифметического блока компьютера [см. Anderson, Earle, Goldschmidt, Powers, IBM J. Res. Dev. 11 (1967), 48-52]. Конечно, нужно тщательно проверять точность алгоритма R, так как он находится на грани того, чтобы быть некорректным. По индукции докажем, что в начале и в конце шага R2 выполняются неравенства

2<2 и 2-1/и <2-2. (55)

Обозначим через Zk значение 2, вычисленное после fc итераций на шаге R2, и пусть 6и = l/v - Zk. При fc = О имеем

So = l/v - 8/v + (32/v - L32/uJ)/4 = щ+т,

где v = (viV2V3)2 и 7/1 = (v - 8v)/vv. При этом параметры rji и 772 удовлетворяют неравенствам -<77i <0и0<7?2< 4- Значит, \So\ < . Теперь предположим, что второе неравенство в (55) удовлетворяется при fc. Тогда

h+l = 1/и - Zk+l = l/v -Zk- 2fc(l - ZkVk) - r

= Sk- Zk(l - Zkv) - zl(v -Vk)-r = 5k-(l/v-5k)v5k-zl(v-Vk)-r = vSl - zl(v - Vk) - r.

Отсюда следует, что О < vSl < < (2~2)2 = 2~2" и

0 < zHv -Vk) + r< 4(2-2""-) + 2-2"-i = 2-2"",

так что <5a;+i < 2~\ Осталось еще проверить первое неравенство в (55). Чтобы убедиться в том, что Zk+i < 2, рассмотрим три случая:

а) Vk = тогда Zk+i = 2;

b) V* i = Vk-i; тогда Zk = 2, поэтому 22, - zlVk < 2 - 2-2"+-i;

с) Vk-i ф ; тогда Zk+\ = \/v - 6к+\ < 2 - 2 < 2, так как fc > 0.

Время, затрачиваемое на выполнение алгоритма R, ограничено сверху количеством циклов, равным

2Г(4п) + 2Г(2п) + 2Г(п) + 2Т(\п) + • • + 0(п),

где Г(п) - верхняя оценка времени, необходимого для выполнения операции умножения п-битовых чисел. Если для некоторой монотонно неубывающей функции f{n) выражение для Т{п) имеет вид nf{n), то

Г(4п) + Т{2п) + Tin) + < Т{8п), (56)

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

Р. П. Брент (R. Р. Brent) в работе JACM 23 (1976), 242-251, показал, что если для умножения п-битовых чисел затрачивается М{п) единиц времени, то для функций вида logx, ехрх и arctanx значения с п значащими битами можно вычислить за 0(A/(n)logn) шагов.

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

Линейная итерационная конфигурация автоматов - это ряд устройств Mj, М2, Мз, ..., каждое из которых может на каждом шаге находиться в некотором конечном множестве состояний. Все машины М2, Л/3, ... имеют одинаковые схемы, и их состояние в момент -Ь 1 является функцией их собственного состояния в момент t, а также состояний в момент t их соседок справа и слева. Первая машина Mj несколько отличается от остальных. Ее состояние в момент t + I есть функция ее собственного состояния и состояния в момент t машины Мз, а также состояния на входе в момент t. Выход линейной итерационной конфигурации - это некоторая функция состояний машины Mi.

Пусть и = (un-i.. «10)2, v = (f„ i ... viVo)2 и g = [Яп-х 9i9o)2 -двоичные числа и пусть uv + q = w = {w2n-i 10)2. Примечательно, что линейная итерационная конфигурация может быть построена независи.мо от п, и, если в моменты 0,1,2,. .. ввести (uo,vo,qo), {ui,vi,qi), («2,2,92), ..., то в моменты 1,2,3,... на ее выходе будет wq, wi, W2,

Это свойство можно сформулировать в терминах языка конструирования компьютеров, сказав, что можно сконструировать один модуль интегральной схемы, обладающий следующим -свойством: если последовательно так смонтировать достаточно много подобных чипов, чтобы каждый из них соединялся только со своим соседом слева и справа, то результирующая схема выдаст 2п-битовое произведение п-битовых чисел точно через 2п тактовых импульсов.

В основе этой конструкции лежит следующая идея. В момент О машина Mi обрабатывает (uq, vq, qo), поэтому в момент 1 она способна выдать результат (uqVo + qo) mod 2. Затем она обрабатывает (ui,ui,gi) и в момент 2 может выдать результат {uqVi + uiVq + qi + ki) mod 2, где fci - "перенос" влево, выполненный на предыдущем шаге. После этого машина обрабатывает («2, гз, 92) и выдает результат {uoV2 + U1V1+ U2V0 + 92-1- 2) niod 2. Кроме того, ее состояние регистрирует значения U2 и V2 с тем, чтобы машина М2 смогла обрабатывать эти величины в момент 3 и чтобы М2 в момент 4 могла вычислить значение U2V2 для Mi. А1ашина Mi Дс1ет

Время Вход

Таблица 2

УМНОЖЕНИЕ В ЛИНЕЙНОЙ ИТЕРАЦИОННОЙ КОНФИГУРАЦИИ

Модуль Мз

Модуль Ml

Модуль Мг

Хо XI X

УО уг у

Хо XI X с 1

уо У1 У

Хо Хх X

с 2:

уо У1 У

ООО ООО

о о о о

" о " о«

« 2 -° « о» S S ;

о о о о

о о о о

о о о о

о о о о

« 2 о" « «

ООО ООО

О о о о о

О О о J

о о о о