На практике для перемножения целых со знаком применяют иные алгоритмы

Рассмотренные алгоритмы относились к представлению чисел с фиксированной запятой, то есть, как это принято в большинстве ВМ, к целым числам. При перемножении чисел со знаком необходимо принимать во внимание, что произведение двух n-разрядных чисел со знаком (знак и n-1 значащий разряд) может иметь 2*(n-1) значащих разрядов и для его хранения обычно используют регистр двойной длины (2*n разрядов). Поскольку число итераций в операции умножения определяется количеством цифровых разрядов множителя, окончательный результат может размещаться в разрядной сетке двойного слова неверно, что и имеет место при перемножении целых чисел.

Как видно, младший разряд произведения целых чисел, имеющий вес 2⁰, размещается в позиции двойного слова, соответствующий весу 2¹. Т.о., для правильного расположения произведения в разрядной сетке двойного слова необходим дополнительный сдвиг вправо. Такой сдвиг можно учесть как в аппаратуре умножителя, так и программным способом.

С другой стороны, при перемножении правильных дробей дополнительный сдвиг не нужен. Это обстоятельство необходимо принимать во внимание при построении умножителя для чисел в форме с плавающей запятой, где участвующие в операции мантиссы представлены в нормализованном виде, то есть правильными дробями. При умножении правильных дробей часто ограничиваются результатом, имеющим одинарную длину. В этом случае может применяться либо отбрасывание лишних разрядов, либо округление.

Ускорение целочисленного умножения. Логические методы ускорения умножения

Методы ускорения умножения можно условно разделить на аппаратные и логические. Те и другие требуют дополнительных затрат оборудования, которые при использовании аппаратных методов возрастают с увеличением разрядности сомножителей. На практике ускорение умножения часто достигается комбинацией аппаратных и логических методов.

Логические подходы к убыстрению умножения можно подразделить на две группы:

- методы, позволяющие уменьшить количество сложений в ходе умножения.

- методы, обеспечивающие обработку нескольких разрядов множителя за шаг.

Алгоритм Бута

В основе алгоритма Бута лежит следующее соотношение, характерное для последовательностей двоичных цифр:

, где m и k - номера крайних разрядов в группе из последовательностей единиц.

Например . Это означает, что при наличии в множителе групп из нескольких единиц (комбинаций вида 011, 110), последовательное добавление к СЧП множимого с нарастающим весом от (2^k до 2^m) можно заменить вычитанием из СЧП множимого с весом 2^k и прибавлением множимого с весом 2^m+1.

Алгоритм предполагает выполнение трех операций: сдвиг, сложение и вычитание.

Помимо сокращения числа сложений у него есть еще одно достоинство – он в равной степени применим к числам без знака и со знаком.

Алгоритм Бута сводится к перекодированию множителя из системы (0,1) в избыточную систему (-1,0,1), из-за чего его часто называют перекодированием Бута:

1 –означает добавление множимого к сумме частичных произведений (СЧП);

-1 – вычитание множимого;

0 –не предполагает никаких действий.

Реализация алгоритма предполагает последовательный справа налево анализ пар разрядов множителя b_ib_i-1 (для i=0 b_i-1считается равным 0).

Деление для компьютера является трудной операцией. Обычно оно реализуется путем многократного прибавления к делимому дополнительного кода делителя.