Составители:
33
3.5 Метод умножения без коррекции результата
3.5.1 Основные положения
Наряду с традиционными методами умножения, требующими кор-
рекции результата, достаточно широкое применение в ЭВМ находит метод
Бута, в котором не требуется выполнение коррекции результата.
Метод Бута относится к логическим методам ускорения умножения,
позволяющим уменьшить количество сложений в ходе умножения. В ос-
нове алгоритма
Бута лежит следующий прием, характерный для последо-
вательности двоичных цифр:
Рассмотрим положительный множитель, состоящий из блока единиц,
окруженных нулями, например 00111110. Произведение определяется по
формуле:
M×00111110 = M×(2
5
+ 2
4
+ 2
3
+ 2
2
+ 2
1
) = M×62
где M – множимое. Количество операций может быть уменьшено вдвое,
если представить произведение следующим образом, заменяя сумму сте-
пеней двойки (2
5
+ 2
4
+ 2
3
+ 2
2
+ 2
1
) разностью (2
6
- 2
1
):
M×00111110 = M×0(1)0000(-1)0 = M×(2
6
– 2
1
) = M×62.
Действительно, любая последовательность единиц в двоичном числе
может быть разбита на разность двух двоичных чисел
n n n
(.…01…...…..10…)
2
(…10…….…00…)
2
– (…00…...…..10…)
2
Таким образом, мы действительно можем заменить операцию умно-
жения на последовательность единиц в множителе более простыми опера-
циями, такими, как сложение с множителем, сдвиг частных произведений,
вычитание множителя. Алгоритм использует тот факт, что нам не нужно
делать ничего, кроме сдвига, когда очередной разряд в двоичном множи-
теле равен нулю.
Эта
схема может быть распространена на любое количество блоков
единиц в множителе (включая случай одной единицы в блоке). Алгоритм
Бута следует этой схеме путем выполнения сложения, когда встречается
начало блока единиц (01) и вычитания, когда встречается конец блока еди-
ниц (10). Схема работает, в том числе, и для отрицательного множителя.
3.5.2 Особенности реализации
Сдвиг
частных произведений реализуется как арифметический сдвиг
(при сдвиге СЧП вправо значение старшего разряда сохраняется). Опера-
ции, выполняемые на каждом шаге умножения, зависят от комбинации
значений текущего и предшествующего ему разрядов множителя (b
i
, b
i – 1
)
(см. табл. 3.12):
Страницы
- « первая
- ‹ предыдущая
- …
- 32
- 33
- 34
- 35
- 36
- …
- следующая ›
- последняя »