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

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

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

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

Розглянемо додатній множник, який містить блок одиниць, поміж нулів, наприклад 00111110. Добуток визначається по формулі:

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

${\displaystyle M\times \,^{\prime \prime }0\;1\;0\;0\;0\;0{\mbox{-1}}\;0\,^{\prime \prime }=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}.}$

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

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

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

Алгоритм Бута виконує циклічне додавання одного з двох заздалегідь заданих значень A і S до добутку 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:

• 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.]
• in
• Booth's Algorithm JavaScript Simulator [ 11 лютого 2021 у Wayback Machine.]
• Implementation in Python [ 30 жовтня 2020 у Wayback Machine.]

Джерела

1. 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.]
2. Collin, Andrew. Andrew Booth’s Computers at Birkbeck College [ 25 лютого 2021 у Wayback Machine.]. Resurrection, Issue 5, Spring 1993. London: Computer Conservation Society.
3. Patterson, David and John Hennessy. Computer Organization and Design: The Hardware/Software Interface, Second Edition. . San Francisco, California: Morgan Kaufmann Publishers. 1998.
4. Stallings, William. Computer Organization and Architecture: Designing for performance, Fifth Edition. . New Jersey: Prentice-Hall, Inc.. 2000.