WikiDer > Алгоритм умножения Бута - Википедия

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

Алгоритм

Алгоритм Бута исследует соседние пары биты N-битного умножителя Y в подписанном два дополнения представление, включая неявный бит ниже младший бит, у₋₁ = 0. Для каждого бита у_я, за я бег от 0 до N - 1, биты у_я и у_я−1 считаются. Если эти два бита равны, аккумулятор продукта п оставлен без изменений. Где у_я = 0 и у_я−1 = 1, множимое, умноженное на 2^я добавлен к п; и где у_я = 1 и у_я-1 = 0, множимое, умноженное на 2^я вычитается из п. Окончательное значение п подписанный продукт.

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

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

Типовая реализация

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

Алгоритм Бута может быть реализован путем многократного добавления (с обычным беззнаковым двоичным сложением) одного из двух заранее определенных значений. А и S к продукту п, затем выполняя правую арифметический сдвиг на п. Позволять м и р быть умножаемое и множитель, соответственно; и разреши Икс и у представляют количество бит в м и р.

1. Определите значения А и S, а начальное значение п. Все эти числа должны иметь длину, равную (Икс + у + 1).
   1. A: Заполните наиболее значимые (крайние левые) биты значением м. Заполните оставшиеся (у + 1) биты с нулями.
   2. S: заполнить наиболее значимые биты значением (-м) в записи с дополнением до двух. Заполните оставшиеся (у + 1) биты с нулями.
   3. P: Заполните самые важные Икс биты с нулями. Справа от него добавьте значение р. Заполните младший значащий (крайний правый) бит нулем.
2. Определите два наименее значимых (крайних правых) бита п.
   1. Если они равны 01, найдите значение п + А. Не обращайте внимания на переполнение.
   2. Если они равны 10, найдите значение п + S. Не обращайте внимания на переполнение.
   3. Если они равны 00, ничего не делайте. Использовать п прямо на следующем шаге.
   4. Если им 11, ничего не делайте. Использовать п прямо на следующем шаге.
3. Арифметически сдвиг значение, полученное на 2-м шаге, на одну позицию вправо. Позволять п теперь равно этому новому значению.
4. Повторяйте шаги 2 и 3, пока они не будут выполнены. у раз.
5. Удалите младший (крайний правый) бит из п. Это продукт м и р.

Пример

Найдите 3 × (−4), где м = 3 и р = −4, и Икс = 4 и у = 4:

• m = 0011, -m = 1101, r = 1100
• А = 0011 0000 0
• S = 1101 0000 0
• Р = 0000 1100 0
• Выполните петлю четыре раза:
  1. Р = 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. Р = 1110 1001 1. Последние два бита - 11.
     • P = 1111 0100 1. Арифметический сдвиг вправо.
• Произведение 1111 0100, что равно −12.

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

• А = 1 1000 0000 0
• S = 0 1000 0000 0
• Р = 0 0000 0010 0
• Выполните петлю четыре раза:
  1. Р = 0 0000 0010 0. Последние два бита - 00.
     • P = 0 0000 0001 0. Сдвиг вправо.
  2. Р = 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. Товар определяется по:

${ 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 { mbox {-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 { 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). Это также работает для отрицательного множителя. Когда единицы умножителя сгруппированы в длинные блоки, алгоритм Бута выполняет меньше сложений и вычитаний, чем обычный алгоритм умножения.

Смотрите также

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

Рекомендации

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

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

внешняя ссылка

• Кодирование камеры Radix-4
• Кодировка камеры Radix-8 в Формальная теория RTL и компьютерной арифметики
• Симулятор JavaScript алгоритма Бута
• Реализация на Python