Алгоритм умножения Бута - это алгоритм умножения, который умножает два двоичных числа со знаком в системе дополнения до двух . Алгоритм был изобретен Эндрю Дональд Бут в 1950 году во время проведения исследований по кристаллографии в Биркбекском колледже в Блумсбери , Лондон . [1] Алгоритм Бута представляет интерес для изучения архитектуры компьютеров .
Алгоритм
Алгоритм Бута проверяет смежные пары битов 'N' -разрядного умножителя Y в дополнительном представлении до двух со знаком , включая неявный бит ниже младшего значащего бита , y −1 = 0. Для каждого бита y i , для i от 0 до N - 1 рассматриваются биты y i и y i -1 . Если эти два бита равны, аккумулятор продукта P не изменяется. Если y i = 0 и y i −1 = 1, множимое, умноженное на 2 i , добавляется к P ; и где у я = 1 и у I-1 = 0, множимого раз 2 я вычитается из P . Конечное значение P - это подписанный продукт.
Представления множимого и произведения не указаны; как правило, они оба представлены в виде дополнения до двух, например множитель, но также подойдет любая система счисления, поддерживающая сложение и вычитание. Как указано здесь, порядок шагов не определен. Обычно он переходит от LSB к MSB , начиная с i = 0; затем умножение на 2 i обычно заменяется инкрементным сдвигом аккумулятора P вправо между шагами; низкие биты могут быть сдвинуты, и последующие дополнения и вычитание могут быть сделаны только на самых высоких N битого P . [2] Есть много вариантов и оптимизаций по этим деталям.
Алгоритм часто описывается как преобразование строк с единицами в множителе в старшие +1 и младшие -1 на концах строки. Когда строка проходит через MSB, старшего разряда +1 нет, и результирующий эффект интерпретируется как отрицательное значение соответствующего значения.
Типовая реализация
Алгоритм Бута может быть реализован путем многократного добавления (с обычным беззнаковым двоичным дополнением) один из двух заранее установленных значений A и S к продукту Р , а затем выполняют вправо арифметический сдвиг на Р . Пусть m и r - множимое и множитель соответственно; и пусть x и y представляют количество бит в m и r .
- Определение значений A и S , а также начальное значение P . Все эти числа должны иметь длину, равную ( x + y + 1).
- A: Заполните самые старшие (крайние левые) биты значением m . Заполните оставшиеся ( y + 1) биты нулями.
- S: заполнить наиболее значимые биты значением (- m ) в дополнительном формате до двух. Заполните оставшиеся ( y + 1) биты нулями.
- P: Заполните самые старшие биты x нулями. Справа от него добавьте значение r . Заполните наименьший значащий (крайний правый) бит нулем.
- Определить два наименее значимые (крайние справа) бит P .
- Если они 01, найдите значение P + A . Не обращайте внимания на переполнение.
- Если они 10, найти значение P + S . Не обращайте внимания на переполнение.
- Если они равны 00, ничего не делайте. Используйте P непосредственно на следующем шаге.
- Если им 11, ничего не делайте. Используйте P непосредственно на следующем шаге.
- Арифметически сдвиньте значение, полученное на 2-м шаге, на одну позицию вправо. Пусть теперь P равно этому новому значению.
- Повторите шаги 2 и 3, пока они не будут выполнены y раз.
- Отбросьте наименее значимый (правый) бит от P . Это произведение m и r .
Пример
Найдите 3 × (−4), где m = 3, r = −4, x = 4 и y = 4:
- m = 0011, -m = 1101, r = 1100
- А = 0011 0000 0
- S = 1101 0000 0
- Р = 0000 1100 0
- Выполните петлю четыре раза:
- Р = 0000110 0 0 . Последние два бита - 00.
- P = 0000 0110 0. Арифметический сдвиг вправо.
- Р = 0000 011 0 0 . Последние два бита - 00.
- P = 0000 0011 0. Арифметический сдвиг вправо.
- Р = 0000 001 1 0 . Последние два бита - 10.
- P = 1101 0011 0. P = P + S.
- P = 1110 1001 1. Арифметический сдвиг вправо.
- Р = 1110100 1 1 . Последние два бита - 11.
- P = 1111 0100 1. Арифметический сдвиг вправо.
- Р = 0000110 0 0 . Последние два бита - 00.
- Произведение 1111 0100, что равно −12.
Вышеупомянутый метод неадекватен, когда множимое является самым отрицательным числом, которое может быть представлено (например, если множимое имеет 4 бита, это значение равно -8). Одним из возможных исправлений этой проблемы является добавление еще одного бита слева от A, S и P. Затем это следует за реализацией, описанной выше, с изменениями в определении битов A и S; например, значение m , первоначально назначенное первым x битам A, будет назначено первым x +1 битам A. Ниже улучшенный метод демонстрируется путем умножения −8 на 2 с использованием 4 битов для умножаемого и множитель:
- А = 1 1000 0000 0
- S = 0 1000 0000 0
- Р = 0 0000 0010 0
- Выполните петлю четыре раза:
- Р = 0 0000 001 0 0 . Последние два бита - 00.
- P = 0 0000 0001 0. Сдвиг вправо.
- Р = 0 0000 000 1 0 . Последние два бита - 10.
- P = 0 1000 0001 0. P = P + S.
- P = 0 0100 0000 1. Сдвиг вправо.
- Р = 0 0100 000 0 1 . Последние два бита - 01.
- P = 1 1100 0000 1. P = P + A.
- P = 1 1110 0000 0. Сдвиг вправо.
- Р = 1 1110 000 0 0 . Последние два бита - 00.
- P = 1 1111 0000 0. Сдвиг вправо.
- Р = 0 0000 001 0 0 . Последние два бита - 00.
- Произведение равно 11110000 (после отбрасывания первого и последнего бита), что равно −16.
Как это работает
Рассмотрим положительный множитель, состоящий из блока единиц, окруженного нулями. Например, 00111110. Товар определяется по:
где M - множимое. Количество операций можно сократить до двух, переписав так же, как
Фактически, можно показать, что любую последовательность единиц в двоичном числе можно разбить на разность двух двоичных чисел:
Следовательно, умножение может быть фактически заменено строкой единиц в исходном числе более простыми операциями: сложением множителя, сдвигом полученного таким образом частичного произведения на соответствующие места и последующим вычитанием множителя. Он использует тот факт, что нет необходимости делать что-либо, кроме сдвига при работе с 0 в двоичном умножителе, и аналогично использованию математического свойства, которое 99 = 100 - 1 при умножении на 99.
Эта схема может быть расширена до любого количества блоков единиц в умножителе (включая случай единственной единицы в блоке). Таким образом,
Алгоритм Бута следует этой старой схеме, выполняя сложение, когда он встречает первую цифру блока единиц (0 1) и вычитание, когда он встречает конец блока (1 0). Это также работает для отрицательного множителя. Когда единицы умножителя сгруппированы в длинные блоки, алгоритм Бута выполняет меньше сложений и вычитаний, чем обычный алгоритм умножения.
Смотрите также
Рекомендации
- ^ Бут, Эндрю Дональд (1951) [1950-08-01]. «Метод знакового двоичного умножения» (PDF) . Ежеквартальный журнал механики и прикладной математики . IV (2): 236–240. Архивировано (PDF) из оригинала на 2018-07-16 . Проверено 16 июля 2018 . Перепечатано в Бут, Эндрю Дональд . Знаковое двоичное умножение . Издательство Оксфордского университета . С. 100–104.
- ^ Чен, Чи-хау (1992). Справочник по обработке сигналов . CRC Press . п. 234. ISBN 978-0-8247-7956-6.
дальнейшее чтение
- Коллин, Эндрю (весна 1993 г.). «Компьютеры Эндрю Бута в Биркбекском колледже» . Воскресение . Лондон: Общество сохранения компьютеров (5).
- Паттерсон, Дэвид Эндрю ; Хеннесси, Джон Лерой (1998). Компьютерная организация и дизайн: аппаратно-программный интерфейс (второе изд.). Сан-Франциско, Калифорния, США: Издательство Морган Кауфманн . ISBN 1-55860-428-6.
- Столлингс, Уильям (2000). Компьютерная организация и архитектура: проектирование для производительности (Пятое изд.). Нью-Джерси: ISBN Prentice-Hall, Inc. 0-13-081294-3.
- Савард, Джон Дж. Г. (2018) [2006]. «Продвинутые арифметические методы» . квадиблок . Архивировано 3 июля 2018 года . Проверено 16 июля 2018 .
Внешние ссылки
- Кодирование камеры Radix-4
- Кодирование Radix-8 Booth в формальной теории RTL и компьютерной арифметики
- Симулятор JavaScript алгоритма Бута
- Реализация на Python