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

Алгоритм добутку Бута це алгоритм добутку, який дозволяє здійснювати операцію добутку пари знакових двійкових чисел у додатковому коді. Алгоритм був розроблений Ендрю Дональдом Бутом в 1951 році при проведенні досліджень в області кристалографії у коледжі ім. Дж. Бірбека в Блумсбері, Лондон. Бут використовував настільні калькулятори, в яких операція зсуву виконується значно швидше ніж операція додавання, і створив алгоритм, який збільшив швидкість їх виконання. Алгоритм Бута становить інтерес у вивченні архітектури комп'ютера.

Як працює алгоритм

Алгоритм Бута, використовує логічний метод прискорення операції добутку, завдяки зменшенню кількості операцій додавання в ході множення. В його основі лежить наступний прийом для послідовності двійкових чисел:

Розглянемо додатній множник, який містить блок одиниць, поміж нулів, наприклад 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 – множник. Кількість операцій можна зменшити вдвічі, якщо представити добуток в наступному вигляді, замінюючи суму степенів двійки : $(2^{5}+2^{4}+2^{3}+2^{2}+2^{1})$ різницею $(2^{6}-2^{1})$ :

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}.

Таким чином, ми дійсно можемо замінити операцію множення на послідовність одиниць в множнику більш простими операціями, такими як, додавання з множником, зсув часткових добутків, і віднімання множника. В алгоритмі використовується той факт, що нам не потрібно виконувати нічого, крім зсуву, коли черговий розряд множника в двійковому коді рівний нулю.

Цю схему можна застосувати для будь-якої кількості блоків одиниць в множнику (включаючи випадок з однією одиницею в блоці). Алгоритм Бута використовує цю схему за допомогою додавання, коли зустрічається початок блоку одиниць (0 1) і віднімання, коли зустрічається кінець блоку одиниць (1 0). Схема працює в тому числі і для від’ємних множників.

Типова реалізація алгоритму

Алгоритм Бута виконує циклічне додавання одного з двох заздалегідь заданих значень A і S до добутку 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. Якщо їх значення дорівнює 01, знайти значення P + A. Переповнення ігнорувати.
2. Якщо їх значення дорівнює 10, знайти значення P + S. Переповнення ігнорувати.
3. Якщо їх значення дорівнює 00, дія не потребується. P залишається без змін і використовується на наступному кроці.
4. Якщо їх значення дорівнює 11, дія не потребується. P залишається без змін і використовується на наступному кроці.
Виконати операцію арифметичного зсуву над значенням, яке було отримане на другому кроці, на один біт вправо. Присвоїти P це нове значення.
Повторити кроки 2 і 3 y разів.
Відкинути крайній найменш значимий (правий) біт P. Це і є добуток m і r.

Приклад

Порахуємо добуток 3 × (−4), приймемо m = 3 і r = −4, а x = 4 і y = 4:

m = 0011, -m = 1101, r = 1100
A = 0011 0000 0
S = 1101 0000 0
P = 0000 1100 0

Виконаємо цикл чотири рази:
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. Потім виконується приведений вище алгоритм, із змінами у визначенні бітів A і S, значення, яке m раніше задавалося для x перших бітів A, тепер буде задаватися для x+1 бітів A.

Нижче приведений приклад більш точної методики з множенням числа −8 на число 2, з використанням 4-ох бітів для обидвох множників:

A = 1 1000 0000 0
S = 0 1000 0000 0
P = 0 0000 0010 0

Виконаємо цикл чотири рази:
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.

Посилання

Radix-4 Booth Encoding [Архівовано 3 березня 2021 у Wayback Machine.]
Radix-8 Booth Encoding in A Formal Theory of RTL and Computer Arithmetic
Booth's Algorithm JavaScript Simulator [Архівовано 11 лютого 2021 у Wayback Machine.]
Implementation in Python [Архівовано 30 жовтня 2020 у Wayback Machine.]

Джерела

Andrew D. Booth. A signed binary multiplication technique. The Quarterly Journal of Mechanics and Applied Mathematics, Volume IV, Pt. 2 [1] [Архівовано 17 липня 2012 у Wayback Machine.]
Collin, Andrew. Andrew Booth’s Computers at Birkbeck College [Архівовано 25 лютого 2021 у Wayback Machine.]. 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.