Page 38 - ЭВМ

Основные изменения обычного алгоритма умножения на каж-
дом шаге, которых n/2, состоят в следующем:
– в зависимости от значения очередной пары разрядов множителя
к частичному произведению умножения необходимо прибавить одно

множимое, удвоенное множимое, утроенное множимое или нуль;
– множитель сдвигается на два разряда вправо;
– частичное произведение умножения сдвигается на два разряда
вправо;
– прибавление одного множимого обычно, прибавление удвоен-
ного множимого достигается посредством передачи в сумматор мно-
жимого со сдвигом на один разряд влево.

Получение утроенного множимого посредством сложения мно-
жимого и удвоенного множимого приводит к дополнительным аппа-
ратным и временным потерям, поэтому обычно используют следую-
щий прием.
Обозначим r частичное произведение. Пусть очередное значе-
ние пары разрядов множителя есть 11(3). Вместо прибавления утро-

енного множимого к частичному произведению и его сдвига на два
разряда вправо П(2): (r +3М)/4 = 1/4 + 3М/4, вычтем из частичного
произведения множимое.
После сдвига полученного частичного произведения на два раз-
ряда вправо П(2) имеем (r – М)/4 = 1/4 + М/4.
Поэтому полученное частичное произведение имеет недостаток
на одно множимое М, что должно быть скорректировано на следую-

щем шаге за счет увеличения на 1 значения следующей пары разрядов
множителя:

Коррекция для b i+1 b i Действие Коррекция для сле-
текущей пары дующей пары
0 0 0 П(2) r 0
0 0 1 П(2) (r+М) 0
0 1 0 П(2) (r+2М) 0
0 1 1 П(2)(r–М) 1
1 0 0 П(2) (r+M) 0
1 0 1 П(2) (r+2М) 0
1 1 0 П(2) (r–М) 1
1 1 1 П(2) r 1

Деление. Пусть z = x/y, где частное z ≥ 0, делимое x ≥ 0 и дели-
тель y ≥ 0 целые, представленные в прямом коде. Операция деления
является обратной для операции умножения.

38