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

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

Алгоритм

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

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

Пример

Вычислить 3 × (−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 \,^{\prime\prime} 0 \; 0 \; 1 \; 1 \; 1 \; 1 \; 1 \; 0 \,^{\prime\prime} = M \times (2^5 + 2^4 + 2^3 + 2^2 + 2^1) = M \times 62$

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

$M \times \,^{\prime\prime} 0 \; 1 \; 0 \; 0 \; 0 \; 0 \mbox{-1} \; 0 \,^{\prime\prime} = M \times (2^6 - 2^1) = M \times 62.$

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

$(\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.

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

$M \times \,^{\prime\prime} 0 \; 0 \; 1 \; 1 \; 1 \; 0 \; 1 \; 0 \,^{\prime\prime} = M \times (2^5 + 2^4 + 2^3 + 2^1) = M \times 58$

$M \times \,^{\prime\prime} 0 \; 1 \; 0 \; 0 \mbox{-1} \; 0 \; 1 \; 0 \,^{\prime\prime} = M \times (2^6 - 2^3 + 2^1) = M \times 58.$

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

Ссылки

• Booth’s Algorithm — Multiplication & Division document
• Radix-4 Booth Encoding
• Radix-8 Booth Encoding in A Formal Theory of RTL and Computer Arithmetic
• Booth’s Algorithm
• Booth’s Algorithm JavaScript Simulator
• Booth Multiplier Implementation in Verilog

Источники

1. Оригинальная статья Booth’s multiplication algorithm
2. Andrew D. Booth. A signed binary multiplication technique. The Quarterly Journal of Mechanics and Applied Mathematics, Volume IV, Pt. 2 [1]
3. Collin, Andrew. Andrew Booth’s Computers at Birkbeck College. 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.