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



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

23 января 2011


Оглавление:
1. Алгоритм Бута
2. Пример
3. Как это работает



Алгоритм умножения Бута это алгоритм умножения, который позволяет перемножить два двоичных числа в дополнительном коде. Алгоритм был разработан Эндрю Дональдом Бутом в 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.


Просмотров: 4622


<<< Строка подключения