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

Алгоритм

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

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

Пример

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

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

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

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

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

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

${\displaystyle M\times 00111110_{2}=M\times (2^{5}+2^{4}+2^{3}+2^{2}+2^{1})=M\times 62}$

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

${\displaystyle M\times (1000000_{2}-10_{2})=M\times (2^{6}-2^{1})=M\times 62.}$

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

${\displaystyle (\ldots 0\overbrace {1\ldots 1} ^{n}0\ldots )_{2}\equiv (\ldots 1\overbrace {0\ldots 0} ^{n}0\ldots )_{2}-(\ldots 0\overbrace {0\ldots 1} ^{n}0\ldots )_{2}.}$

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

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

${\displaystyle M\times 00111010_{2}=M\times (2^{5}+2^{4}+2^{3}+2^{1})=M\times 58}$

${\displaystyle M\times (1000000_{2}-110_{2})=M\times (2^{6}-(2^{2}+2^{1}))=M\times 58}$

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

Ссылки

• in

Источники

1. Оригинальная статья
2. Andrew D. Booth. A signed binary multiplication technique. The Quarterly Journal of Mechanics and Applied Mathematics, Volume IV, Pt. 2
3. Collin, Andrew. . Resurrection , Issue 5, Spring 1993. London: Computer Conservation Society.
4. 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.
5. Stallings, William. Computer Organization and Architecture: Designing for performance, Fifth Edition . ISBN 0-13-081294-3 . New Jersey: Prentice-Hall, Inc.. 2000.