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