Русская Википедия:Алгоритм Бута

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

Алгоритм

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

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

Пример

Вычислить <math>3\times(-4)</math>. В этом случае <math>m = 3,\ r = (-4),\ x = 4,\ y = 4</math>:

  • <math>A = 0011\ 0000\ 0</math>
  • <math>S = 1101\ 0000\ 0</math>
  • <math>P = 0000\ 1100\ 0</math>
  • Выполним цикл 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 бита, то это значение равно <math>(-8)</math>). Один из возможных способов решить эту проблему — добавить один дополнительный бит слева от <math>A</math>, <math>S</math> и <math>P</math>. Ниже мы покажем усовершенствованную технику на примере умножения <math>(-8)</math> на 2 используя по 4 бита под множимое и множитель:

  • <math>A = 1\ 1000\ 0000\ 0</math>
  • <math>S = 0\ 1000\ 0000\ 0</math>
  • <math>P = 0\ 0000\ 0010\ 0</math>
  • Выполним цикл 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. Произведение определяется по формуле :

<math> M \times 00111110_{2} = M \times (2^5 + 2^4 + 2^3 + 2^2 + 2^1) = M \times 62 </math>

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

<math> M \times (1000000_{2} - 10_{2}) = M \times (2^6 - 2^1) = M \times 62. </math>

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

<math> (\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. </math>

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

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

<math> M \times 00111010_{2} = M \times (2^5 + 2^4 + 2^3 + 2^1) = M \times 58 </math>
<math> M \times (1000000_{2} - 110_{2}) = M \times (2^6 - (2^2 + 2^1)) = M \times 58 </math>

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

Ссылки

Источники

  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.
Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Алгоритм_Бута&oldid=8940002