Алгоритм умножения Бута

Алгоритм умножения Бута — это алгоритм умножения , который умножает два двоичных числа со знаком в записи дополнения до двух . Алгоритм в 1950 году во время был изобретен Эндрю Дональдом Бутом исследования кристаллографии в Биркбек-колледже в Блумсбери , Лондон . ^[1] Алгоритм Бута представляет интерес для изучения компьютерной архитектуры .

Алгоритм

Алгоритм Бута исследует соседние пары бит 'N'-битного множителя Y в представлении дополнения до двух со знаком , включая неявный бит ниже младшего бита , y ₋₁ = 0. Для каждого бита y _i , для i от 0 до N биты y _i и y _{i −1} − 1, рассматриваются . Если эти два бита равны, аккумулятор произведения P остается неизменным. Где y _i = 0 и y _{i −1} = 1, множимое, умноженное на 2 ^я добавляется к P ; и где y _i = 1 и y _i−1 = 0, множимое, умноженное на 2 ^я вычитается П. из Конечное значение P — это подписанное произведение.

Представления множимого и произведения не указаны; обычно они оба также представлены в виде дополнения до двух, например, множитель, но подойдет любая система счисления, поддерживающая сложение и вычитание. Как указано здесь, порядок шагов не определен. Обычно он переходит от LSB к MSB , начиная с i = 0; умножение на 2 ^я затем обычно заменяется постепенным сдвигом аккумулятора P вправо между шагами; младшие биты могут быть смещены, а последующие сложения и вычитания могут выполняться только для старших N битов P . ^[2] Существует множество вариаций и оптимизаций этих деталей.

Алгоритм часто описывается как преобразование строк из единиц в множителе в старший +1 и младший -1 на концах строки. Когда строка проходит через старший бит, старшего +1 нет, и конечным эффектом является интерпретация как отрицательное значение соответствующего значения.

Типичная реализация

Алгоритм Бута может быть реализован путем многократного добавления (обычным двоичным сложением без знака) одного из двух заранее определенных значений и S к продукту P , а затем выполнения арифметического сдвига вправо P. A Пусть 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 . Заполните младший значащий (крайний правый) бит нулем.
Определите два младших (крайних правых) бита P .
1. они равны 01, найдите значение P + A. Если Игнорируйте любое переполнение.
2. их 10, найдите значение P + S. Если Игнорируйте любое переполнение.
3. Если они равны 00, ничего не делайте. Используйте P непосредственно на следующем шаге.
4. Если их 11, ничего не делайте. Используйте P непосредственно на следующем шаге.
Арифметически сдвиньте значение, полученное на 2-м шаге, на одну позицию вправо. Пусть P теперь равно этому новому значению.
Повторяйте шаги 2 и 3, пока они не будут выполнены y раз.
Отбросьте младший (крайний правый) бит из P . Это произведение m и r .

Пример

Найдите 3 × (−4), где m = 3 и r = −4, x = 4 и y = 4:

м = 0011, -м = 1101, г = 1100
А = 0011 0000 0
С = 1101 0000 0
Р = 0000 1100 0
Выполните цикл четыре раза:
1. Р = 0000 110 0 0 . Последние два бита — 00.
  - P = 0000 0110 0. Арифметический сдвиг вправо.
2. П = 0000 011 0 0 . Последние два бита — 00.
  - P = 0000 0011 0. Арифметический сдвиг вправо.
3. Р = 0000 001 1 0 . Последние два бита равны 10.
  - Р = 1101 0011 0. Р = Р + С.
  - P = 1110 1001 1. Арифметический сдвиг вправо.
4. Р = 1110 100 1 1 . Последние два бита равны 11.
  - P = 1111 0100 1. Арифметический сдвиг вправо.
Произведение: 1111 0100, что равно −12.

Вышеупомянутый метод неадекватен, когда множимое является самым отрицательным числом , которое может быть представлено (например, если множимое имеет 4 бита, то это значение равно -8). Это происходит потому, что тогда происходит переполнение при вычислении -m, отрицания множимого, которое необходимо для установки S. Одним из возможных решений этой проблемы является расширение A, S и P на один бит каждый, при этом они все еще представляют одно и то же число. То есть, хотя ранее -8 было представлено в четырех битах по 1000, теперь оно представлено в 5 битах по 11000. Далее следует реализация, описанная выше, с изменениями в определении битов A и S; например, значение m , первоначально присвоенное первым x битам A, теперь будет расширено до x +1 битов и присвоено первым x +1 битам A. Ниже улучшенный метод демонстрируется путем умножения −8 на 2, используя 4 бита для множимого и множителя:

А = 1 1000 0000 0
С = 0 1000 0000 0
Р = 0 0000 0010 0
Выполните цикл четыре раза:
1. п знак равно 0 0000 001 0 0 . Последние два бита — 00.
  - P = 0 0000 0001 0. Сдвиг вправо.
2. Р знак равно 0 0000 000 1 0 . Последние два бита равны 10.
  - Р = 0 1000 0001 0. Р = Р + С.
  - P = 0 0100 0000 1. Сдвиг вправо.
3. п знак равно 0 0100 000 0 1 . Последние два бита — 01.
  - Р = 1 1100 0000 1. Р = Р + А.
  - P = 1 1110 0000 0. Сдвиг вправо.
4. П знак равно 1 1110 000 0 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\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}}\;1{\mbox{-1}}\;0\,^{\prime \prime }=M\times (2^{6}-2^{3}+2^{2}-2^{1})=M\times 58.$

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

См. также

Ссылки

^ Бут, Эндрю Дональд (1951) [1950-08-01]. «Техника знакового двоичного умножения» (PDF) . Ежеквартальный журнал механики и прикладной математики . IV (2): 236–240. Архивировано (PDF) из оригинала 16 июля 2018 года . Проверено 16 июля 2018 г. Перепечатано в Бут, Эндрю Дональд . Техника знакового двоичного умножения . Издательство Оксфордского университета . стр. 100–104.
^ Чен, Чи-хау (1992). Руководство по обработке сигналов . ЦРК Пресс . п. 234. ИСБН 978-0-8247-7956-6 .

Дальнейшее чтение

Коллин, Эндрю (весна 1993 г.). «Компьютеры Эндрю Бута в Биркбек-колледже» . Воскресение (5). Лондон: Общество охраны компьютеров .
Паттерсон, Дэвид Эндрю ; Хеннесси, Джон Лерой (1998). Организация и дизайн компьютера: аппаратно-программный интерфейс (второе изд.). Сан-Франциско, Калифорния, США: Издательство Morgan Kaufmann . ISBN 1-55860-428-6 .
Столлингс, Уильям (2000). Компьютерная организация и архитектура: проектирование для повышения производительности (Пятое изд.). Нью-Джерси: Prentice-Hall, Inc. ISBN 0-13-081294-3 .
Савард, Джон Дж. Г. (2018) [2006]. «Продвинутые арифметические методы» . четырехблок . Архивировано из оригинала 3 июля 2018 года . Проверено 16 июля 2018 г.

Внешние ссылки

[Booth_1951-1] Бут, Эндрю Дональд (1951) [1950-08-01]. «Техника знакового двоичного умножения» (PDF) . Ежеквартальный журнал механики и прикладной математики . IV (2): 236–240. Архивировано (PDF) из оригинала 16 июля 2018 года . Проверено 16 июля 2018 г. Перепечатано в Бут, Эндрю Дональд . Техника знакового двоичного умножения . Издательство Оксфордского университета . стр. 100–104.

[Chen_1992-2] Чен, Чи-хау (1992). Руководство по обработке сигналов . ЦРК Пресс . п. 234. ИСБН 978-0-8247-7956-6 .

[1]

[2]