Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Алгоритм Бута
В основе алгоритма Бута лежит следующее соотношение, характерное для последовательностей двоичных цифр: , где m и k - номера крайних разрядов в группе из последовательностей единиц. Например . Это означает, что при наличии в множителе групп из нескольких единиц (комбинаций вида 011, 110), последовательное добавление к СЧП множимого с нарастающим весом от (2k до 2m) можно заменить вычитанием из СЧП множимого с весом 2k и прибавлением множимого с весом 2m+1. Алгоритм предполагает выполнение трех операций: сдвиг, сложение и вычитание. Помимо сокращения числа сложений у него есть еще одно достоинство – он в равной степени применим к числам без знака и со знаком. Алгоритм Бута сводится к перекодированию множителя из системы (0, 1) в избыточную систему (-1, 0, 1), из-за чего его часто называют перекодированием Бута: 1 –означает добавление множимого к сумме частичных произведений (СЧП); -1 – вычитание множимого; 0 –не предполагает никаких действий. Реализация алгоритма предполагает последовательный справа налево анализ пар разрядов множителя bibi-1 (для i=0 bi-1считается равным 0).
Деление для компьютера является трудной операцией. Обычно оно реализуется путем многократного прибавления к делимому дополнительного кода делителя.
|