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

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

• 1 Алгоритм
• 2 Типовая реализация
• 3 Пример
• 4 Как это работает
• 5 См. Также
• 6 Ссылки
• 7 Дальнейшее чтение
• 8 Внешние ссылки

Алгоритм Бута проверяет смежные пары битов '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 ⁱ, добавляется к P ; и где у я = 1 и у I-1 = 0, множимого раз 2 ^я вычитается из P. Конечное значение P - это подписанный продукт.

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

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

Арифмометр Walther WSR160 1960 года выпуска. Каждый поворот рукоятки кривошипа складывает (вверх) или вычитает (вниз) операнд, установленный в верхний регистр, из значения в регистре аккумулятора внизу. Сдвиг сумматора влево или вправо увеличивает эффект в десять раз.

Алгоритм Бута может быть реализован путем многократного добавления (с обычным беззнаковым двоичным дополнением) один из двух заранее установленных значений A и S к продукту Р, а затем выполняют вправо арифметический сдвиг на Р. Пусть 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. Заполните младший значащий (крайний правый) бит нулем.
2. Определить два наименее значимые (крайние справа) бит P.
   1. Если они 01, найдите значение P  +  A. Не обращайте внимания на переполнение.
   2. Если они 10, найти значение P  +  S. Не обращайте внимания на переполнение.
   3. Если они равны 00, ничего не делайте. Используйте P непосредственно на следующем шаге.
   4. Если им 11, ничего не делайте. Используйте P непосредственно на следующем шаге.
3. Арифметически сдвиньте значение, полученное на 2-м шаге, на одну позицию вправо. Пусть теперь 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
• А = 0011 0000 0
• S = 1101 0000 0
• Р = 0000 1100 0
• Выполните петлю четыре раза:
  1. Р = 0000110 0 0. Последние два бита - 00.
     • P = 0000 0110 0. Арифметический сдвиг вправо.
  2. Р = 0000 011 0 0. Последние два бита - 00.
     • P = 0000 0011 0. Арифметический сдвиг вправо.
  3. Р = 0000 001 1 0. Последние два бита - 10.
     • P = 1101 0011 0. P = P + S.
     • P = 1110 1001 1. Арифметический сдвиг вправо.
  4. Р = 1110100 1 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 битов для умножаемого и множитель:

• А = 1 1000 0000 0
• S = 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.
     • P = 0 1000 0001 0. P = P + S.
     • P = 0 0100 0000 1. Сдвиг вправо.
  3. Р = 0 0100 000 0 1. Последние два бита - 01.
     • P = 1 1100 0000 1. P = P + A.
     • P = 1 1110 0000 0. Сдвиг вправо.
  4. Р = 1 1110 000 0 0. Последние два бита - 00.
     • P = 1 1111 0000 0. Сдвиг вправо.
• Произведение равно 11110000 (после отбрасывания первого и последнего бита), что равно −16.

Рассмотрим положительный множитель, состоящий из блока единиц, окруженного нулями. Например, 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 M \ times \, ^ {\ prime \ prime} 0 \; 1 \; 0 \; 0 \; 0 \; 0 {\ t_dv {-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 в двоичном умножителе, и аналогично использованию математического свойства, которое 99 = 100-1 при умножении на 99.

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

${\ Displaystyle 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}$

${\ Displaystyle M \ times \, ^ {\ prime \ prime} 0 \; 1 \; 0 \; 0 {\ t_dv {-1}} \; 1 {\ t_dv {-1}} \; 0 \, ^ {\ prime \ prime} = M \ times (2 ^ {6} -2 ^ {3} + 2 ^ {2} -2 ^ {1}) = M \ times 58.}$

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

• Двоичный множитель
• Несмежная форма
• Избыточное двоичное представление
• Дерево Уоллеса
• Дадда множитель

• Коллин, Эндрю (весна 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