Алгоритмы умножения

Умножение двоичных чисел со знаком удобнее всего проводить в прямом коде. Действительно, знак произведения не зависит от соотношения величин модулей сомножителей, а зависит только от их знаков:

(3.25)

а модуль произведения равен произведению модулей сомножителей. Обозначим — модули сомножителей и произведения соответственно. Тогда

(3.26)

Выражение (3.26) определяет процесс формирования произведения путем вычисления частичных сумм и суммы частичных произведений. Напомним, что b₁ — старший разряд множителя, а b_n — младший. Вычисляя непосредственно по формуле (3.26), следует на каждом шаге:

1. Проанализировать очередную цифру множителя b _i. Если b_i,= 1, то очередная частичная сумма равна A, и она добавляется к накопленной ранее сумме частичных произведений S (на первом шаге S=0), иначе добавления не производится.

2. Осуществить правый сдвиг частичного произведения S на один разряд. Умножение S*2 ^{- 1} соответствует делению на 2, что в двоичной системе счисления равносильно сдвигу числа на один разряд вправо.

3. Пункты 1 и 2 повторяются до тех пор, пока не будут исчерпаны все цифры множителя.

Очевидно, число шагов при использовании приведенного выше метода равно разрядности модуля множителя. Алгоритм умножения чисел, представленных в прямом коде, приведен на рис. 3.23.

В изображенном на рис. 3.23 алгоритме, в отличие от алгоритмов сложения/вычитания, значение OV=0 устанавливается безусловно. Действительно А и B — дробные числа; очевидно при всегда

(Страница64)

В результате вычисления по формуле (3.26) получается произведение разрядностью 2n. Если рассматривать сомножители как дроби, то младшие n разрядов можно просто отбросить (округление с недостатком) или округлить до п -разрядного модуля по правилам округления.

Очевидно, из выражения (3.26) легко получить

(3.27)

что позволяет производить умножение, начиная со старших разрядов множителя. При этом сдвиг суммы частичных произведений осуществляется влево на один разряд, чему соответствует умножение двоичного числа на 2.

Рис. 3.23. Умножение в прямом коде