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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Як працює алгоритм[ред.ред. код]

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

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

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

Дійсно, будь-яка послідовність одиниць у двійковому числі може бути розбита на різність двох двійкових чисел.

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

Цю схему можна застосувати для будь-якої кількості блоків одиниць в множнику (включаючи випадок з однією одиницею в блоці). Алгоритм Бута використовує цю схему за допомогою додавання, коли зустрічається початок блоку одиниць (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.

Посилання[ред.ред. код]

Джерела[ред.ред. код]

  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.