|
Алгоритм БутаАлгоритм Бута, алгоритм умножения, который позволяет перемножить два двоичных числа в дополнительном коде. Алгоритм был разработан Эндрю Дональдом Бутом в 1951 при проведении исследований кристаллографии в колледже Birkbeck в Bloomsbury (Лондон). Бут пользовался настольными вычислителями, которые выполняли операцию сдвига быстрее, чем операцию сложения, и создал алгоритм для увеличения скорости их работы. А.Б. представляет интерес при изучении архитектуры компьютера. А.Б. включает в себя циклическое сложение одного из двух заранее установленных значений A и S с произведением P, а затем выполнение арифметического сдвига вправо над P. Пусть m и r — множимое и множитель соответственно, а x и y представляют собой количество битов в m и r.
Вычислить 3 × (−4). В этом случае m = 3, r = −4, x = 4, y = 4:
Вышеупомянутой техники недостаточно, когда множимое является наибольшим по модулю отрицательным числом, которое может быть представлено в текущей разрядной сетке (например, если размер множимого 4 бита, то это значение равно −8). Один из возможных способов решить эту проблему — добавить один дополнительный бит слева от A, S и P. Ниже мы покажем усовершенствованную технику на примере умножения −8 на 2 используя по 4 бита под множимое и множитель:
Рассмотрим положительный множитель, состоящий из блока единиц, окруженных нулями, например 00111110. Произведение определяется по формуле :
где M — множимое. Количество операций может быть уменьшено вдвое, если представить произведение слеюущим образом :
На самом деле, можно показать, что любая последовательность единиц в двоичном числе может быть разбита на разность двух двоичных чисел:
Таким образом, мы действительно можем заменить операцию умножения на последовательность единиц в исходном числе более простыми операциями: сложение с множителем, сдвиг частичного произведения, вычитание множителя. Алгоритм использует тот факт, что нам не нужно делать ничего кроме сдвига, когда очередной разряд в двоичном множителе равен нулю, а также простое математическое свойство: 99 = 100 − 1 при умножении на 99. Эта схема может быть распространена на любое количество блоков единиц в множителе (включая случай одной единицы в блоке). Таким образом,
А.Б. следует этой схеме путем выполнения сложения, когда встречается первая цифра блока единиц (0 1), и вычитания, когда встречается конец блока единиц (1 0). Схема работает в том числе и для отрицательного множителя. Когда единицы в можителе сгруппированы в длинные блоки, алгоритм Бута выполняет меньше сложений и вычитаний, чем обычный алгоритм умножения. |
Loading
|