Алгоритм Бута

Алгоритм умножения Бута — это алгоритм умножения, который позволяет перемножить два двоичных числа в дополнительном коде. Алгоритм был разработан Эндрю Дональдом Бутом в 1951 году при проведении исследований в области кристаллографии в колледже им. Дж. Бирбека в Блумсбери (Лондон). Бут пользовался настольными вычислителями, которые выполняли операцию сдвига быстрее, чем операцию сложения, и создал алгоритм для увеличения скорости их работы. Алгоритм Бута представляет интерес при изучении архитектуры компьютера.

Алгоритм

Алгоритм Бута включает в себя циклическое сложение одного из двух заранее установленных значений $A$ и $S$ с произведением $P$ , а затем выполнение арифметического сдвига вправо над $P$ .
Пусть $m$ и $r$ — множимое и множитель соответственно, а $x$ и $y$ представляют собой количество битов в $m$ и $r$ соответственно.

Установить значения A и S, а также начальное значение P. Каждое из этих чисел должно иметь длину, равную (x+y+1).
1. $A$ : Заполнить наиболее значимые (левые) биты значением $m$ . Заполнить оставшиеся ( $y + 1$ ) бит нулями.
2. $S$ : Заполнить наиболее значимые биты значением ( $- m$ ) в дополнительном коде. Заполнить оставшиеся ( $y + 1$ ) бит нулями.
3. $P$ : Заполнить наиболее значимые $x$ бит нулями. Справа от них заполнить биты значением $r$ . Записать $0$ в крайний наименее значимый (правый) бит.
Определить значение двух наименее значимых (правых) битов P и вычислить по ним значение для следующего шага:
1. Если их значение равно $0 1_{2}$ , прибавить $A$ к $P$ . Переполнение игнорировать.
2. Если их значение равно $1 0_{2}$ , прибавить $S$ к $P$ . Переполнение игнорировать.
3. Если их значение равно $0 0_{2}$ , действие не требуется. $P$ используется без изменений на следующем шаге.
4. Если их значение равно $1 1_{2}$ , действие не требуется. $P$ используется без изменений на следующем шаге.
Выполнить операцию арифметического сдвига над значением, полученным на втором шаге, на один бит вправо. Присвоить $P$ это новое значение.
Повторить шаги 2 и 3 $y$ раз.
Отбросить крайний наименее значимый (правый) бит $P$ . Это и есть произведение $m$ и $r$ .

Пример

Вычислить $3 \times (- 4)$ . В этом случае $m = 3, r = (- 4), x = 4, y = 4$ :

$A = 0011 0000 0$
$S = 1101 0000 0$
$P = 0000 1100 0$
Выполним цикл 4 раза :
1. P = 0000 1100 0. Крайние два бита равны 00.
  - P = 0000 0110 0. Арифметический сдвиг вправо.
2. P = 0000 0110 0. Крайние два бита равны 00.
  - P = 0000 0011 0. Арифметический сдвиг вправо.
3. P = 0000 0011 0. Крайние два бита равны 10.
  - P = 1101 0011 0. P = P + S.
  - P = 1110 1001 1. Арифметический сдвиг вправо.
4. P = 1110 1001 1. Крайние два бита равны 11.
  - P = 1111 0100 1. Арифметический сдвиг вправо.
Произведение равно 1111 0100 (−12 в десятичной системе)

Вышеупомянутой техники недостаточно, когда множимое является наибольшим по модулю отрицательным числом, которое может быть представлено в текущей разрядной сетке (например, если размер множимого 4 бита, то это значение равно $(- 8)$ ). Один из возможных способов решить эту проблему — добавить один дополнительный бит слева от $A$ , $S$ и $P$ . Ниже мы покажем усовершенствованную технику на примере умножения $(- 8)$ на 2 используя по 4 бита под множимое и множитель:

$A = 1 1000 0000 0$
$S = 0 1000 0000 0$
$P = 0 0000 0010 0$
Выполним цикл 4 раза :
1. P = 0 0000 0010 0. Крайние два бита равны 00.
  - P = 0 0000 0001 0. Арифметический сдвиг вправо.
2. P = 0 0000 0001 0. Крайние два бита равны 10.
  - P = 0 1000 0001 0. P = P + S.
  - P = 0 0100 0000 1. Арифметический сдвиг вправо.
3. P = 0 0100 0000 1. Крайние два бита равны 01.
  - P = 1 1100 0000 1. P = P + A.
  - P = 1 1110 0000 0. Арифметический сдвиг вправо.
4. P = 1 1110 0000 0. Крайние два бита равны 00.
  - P = 1 1111 0000 0. Арифметический сдвиг вправо.
После отбрасывания крайних бит получаем значение произведения: 11110000 (−16 в десятичной системе).

Как это работает

Рассмотрим положительный множитель, состоящий из блока единиц, окружённых нулями, например 00111110. Произведение определяется по формуле :

M \times 0011111 0_{2} = M \times (2^{5} + 2^{4} + 2^{3} + 2^{2} + 2^{1}) = M \times 62

где $M$ — множимое. Количество операций может быть уменьшено вдвое, если представить произведение следующим образом :

M \times (100000 0_{2} - 1 0_{2}) = M \times (2^{6} - 2^{1}) = M \times 62 .

На самом деле, можно показать, что любая последовательность единиц в двоичном числе может быть разбита на разность двух двоичных чисел:

(\dots 0 \overset{n}{\overset{⏞}{1 \dots 1}} 0 \dots)_{2} \equiv (\dots 1 \overset{n}{\overset{⏞}{0 \dots 0}} 0 \dots)_{2} - (\dots 0 \overset{n}{\overset{⏞}{0 \dots 1}} 0 \dots)_{2} .

Таким образом, мы действительно можем заменить операцию умножения на последовательность единиц в исходном числе более простыми операциями: сложение со множителем, сдвиг частичного произведения, вычитание множителя. Алгоритм использует тот факт, что нам не нужно делать ничего кроме сдвига, когда очередной разряд в двоичном множителе равен нулю, а также простое математическое свойство: 99 = 100 − 1 при умножении на 99.

Эта схема может быть распространена на любое количество блоков единиц в множителе (включая случай одной единицы в блоке). Таким образом,

M \times 0011101 0_{2} = M \times (2^{5} + 2^{4} + 2^{3} + 2^{1}) = M \times 58

M \times (100000 0_{2} - 11 0_{2}) = M \times (2^{6} - (2^{2} + 2^{1})) = M \times 58

Алгоритм Бута следует этой схеме путём выполнения сложения, когда встречается первая цифра блока единиц (0 1), и вычитания, когда встречается конец блока единиц (1 0). Схема работает в том числе и для отрицательного множителя. Когда единицы в множителе сгруппированы в длинные блоки, алгоритм Бута выполняет меньше сложений и вычитаний, чем обычный алгоритм умножения.

Ссылки

Источники

Andrew D. Booth. A signed binary multiplication technique. The Quarterly Journal of Mechanics and Applied Mathematics, Volume IV, Pt. 2 [1]
Collin, Andrew. Andrew Booth’s Computers at Birkbeck College. Resurrection, Issue 5, Spring 1993. London: Computer Conservation Society.
Patterson, David and John Hennessy. Computer Organization and Design: The Hardware/Software Interface, Second Edition. ISBN 1-55860-428-6. San Francisco, California: Morgan Kaufmann Publishers. 1998.
Stallings, William. Computer Organization and Architecture: Designing for performance, Fifth Edition. ISBN 0-13-081294-3. New Jersey: Prentice-Hall, Inc.. 2000.

Алгоритм Бута

Содержание