Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм Бута

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

Алгоритм

Алгоритм Бута включает в себя циклическое сложение одного из двух заранее установленных значений A и S с произведением P, а затем выполнение арифметического сдвига вправо над P. Пусть множимое и множитель соответственно, а x и y представляют собой количество битов в m и r.

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