Следовательно, к присваивается значение О или 1 в зависимости от того, произошел (1) или не произошел (0) перенос, т. е. вьшолняется присвоение к [Uj + Vj +А;>6].)

A3. [Цикл по j.] Увеличить j на единицу. Если теперь j < п, то вернуться к шагу А2, иначе - присвоить и;„ <- А; и завершить выполнение алгоритма.

По поводу формального доказательства корректности алгоритма А обратитесь к упр. 4.

Программа для компьютера MIX, реализующая эту процедуру сложения, могла бы выглядеть так.

Программа А {Сложение неотрицательных целых чисел). Пусть LOC(Uj) = + LOC(dj) = V -Н j, LOC{Wj) = 4 + j, ill = j - n, lA = k, размер слова = 6, N = п.

Время выполнения этой программы равно ЮЛ + 6 циклам независимо от числа переносов К. Величина К подробно анализируется в конце этого раздела.

Возможны многочисленные модификации алгоритма А, но лишь некоторые из них упоминаются в упражнениях к этому разделу. Главу, посвященную обобщениям данного алгоритма, можно было бы назвать "Разработка схем сложения для цифровой вычислительной машины".

Задача вычитания аналогична задаче сложения, но есть и заслуживающие внимания отличия.

Алгоритм S {Вычитание неотрицательных целых чисел). По данным неотрицательным п-разрядным целым числам (u„ i. ..uiUo)b > {vn-i • • viVo)b, записанным по основанию b, этот алгоритм находит неотрицательную разность {wn-i WiWo)b-

51. [Начальная установка.] Присвоить j +- О, А; 0.

52. [Вычитание разрядов.] Присвоить <- {uj - Vj + k) modbnk <- [{uj-Vj+k)/b\. (Другими словами, к присваивается - 1 или О в зависимости от того, происходит ли заимствование, т. е. оказывается ли, что Uj - Vj + k<0. Что касается вычисления Wj, примем во внимание тот факт, что должно выполняться неравенство -Ь = О - (Ь - 1) + (-1) < Uj - Vj + к < {Ь - 1) - О + О < Ь. Следовательно, 0<Uj - Vj + k + b<2bK это полагается в описываемой ниже программной реализации.)

S3. [Цикл по j.] Увеличить j на единицу. Если теперь j < п, то вернуться к шагу S2; в противном случае завершить выполнение алгоритма. (Когда выполнение алгоритма завершается, должно получиться к = Q; условие к = -1 соответствует единственному случаю, когда (vn-i ViVo)b > (u-i • • •uiUo)6i что противоречит сделанному раньше предположению; см. упр. 12.)

При реализации алгоритма в MIX-программе удобнее вместо значения к хранить значение 1+к, так что на шаге S2 можно вычислить величину Uj-Vj + {l+k) + {b-l). (Напомним, что Ь - размер машинного слова.) Проиллюстрируем алгоритм следующей программой.

Программа S {Вычитание неотрицательных целых чисел). Эта программа аналогична программе А, но в ней гА = 1+к. Как и в других программах этого раздела, в ячейке WM1 хранится константа Ь-1 - максимально допустимое значение, которое может храниться в машинном слове MIX (см. программу 4.2.3D, строки 38-39).

Время выполнения этой программы равно 12iV--3 циклов, что немного больше, чем для программы А.

Читатель, возможно, поинтересуется, не лучше ли было бы разработать одну комбинированную программу для сложения-вычитания вместо двух разных алгоритмов А и S. Но анализ программ показывает, что в общем случае для реализации этих операций предпочтительнее использовать две разные программы, чтобы внутренний вычислительный цикл выполнялся настолько быстро, насколько это возможно.

Наша следующая задача-умножение. Здесь идеи, использованные при построении алгоритма А, получают дальнейшее развитие.

Алгоритм М {Умножение неотрицательных целых чисел). По заданным неотрицательным п-разрядным целым числам («„ i...uiUo)6 и {v„-i... vivo)b по основанию b этот алгоритм строит их произведение {wm+n-i ...wiWo)b- (Общепринятый метод умножения при помощи карандаша и бумаги основан на нахождении сначала частичных произведений (u-i • • -UiUq) х vj для О < j < п, а затем - суммы этих произведений, сдвинутых на соответствующее число масштабирующих разрядов. Но на компьютере предпочтительнее вьшолнять сложение параллельно умножению, как это и делается в данном алгоритме.)

Таблица 1

УМНОЖЕНИЕ 914 НА 84.

Ml. [Начальная установка.] Присвоить всем параметрам w-i, Wm-2 • • •, uo значения "нуль". Присвоить j 0. (Если не обнулить все параметры Wm-i,- • • ,uo, можно получить более общий алгоритм с результатом

{Wm+n-l Wo)b («m-l • • • "о)б X {Vn-1 Vo)b + {Wm-1 Wo)b-

Этот алгоритм умножения и сложения часто используется в приложениях*.

М2. [Нулевой множитель?] Если vj = О, то присвоить Wj+m <- О и перейти к щагу Мб. (Эта проверка может сэкономить время, если достаточно велика вероятность того, что Vj равно нулю; в противном случае проверку можно опустить без ущерба для корректности алгоритма.)

МЗ. [Начальная установка г.] Присвоить i <- О, А; <- 0.

М4. [Умножить и сложить.] Присвоить сначала t i- щ х Vj + Wi+j + к, а затем - Wi+j <- t mod b и к <- [t/b\. (Здесь разряд переноса к всегда будет принадлежать интервалу О < А; < 6; см. ниже.)

М5. [Цикл по г.] Увеличить i на единицу. Если после этого г < т, то вернуться к щагу М4; в противном случае присвоить Wj+m i-

Мб. [Цикл по j.] Увеличить j на единицу. Если после этого j < п, то вернуться к шагу М2; в противном случае завершить выполнение алгоритма.

Работа алгоритма М для случая, когда b = 10, проиллюстрирована в табл. 1, в которой показано состояние вычислительного процесса в начале шагов М5 и Мб. Доказательство корректности алгоритма М приведено в упр. 14.

Два неравенства,

0<t<b, 0<k<b, (1)

являются критическими для эффективной реализации этого алгоритма, так как они накладывают ограничения на размер регистра, необходимый для вычислений. Их можно доказать по индукции, так как если в начале шага М4 справедливо неравенство к < Ь, то

Ui X Vj + Wi+j -I- А; < (6 - 1) X (6 - 1) + (6 - 1) + (6 - 1) = 6 - К 6

Следующая MIX-программа демонстрирует те моменты, которые нужно учитывать при реализации алгоритма М на компьютере. Шаг М4 можно было бы

* Его часто называют "умножение с накоплением". - Прим. перев.