4. Целочисленное умножение

По сравнению со сложением и вычитанием, умножение — более сложная операция, как при программном, так и при аппаратном воплощении. В ВМ применяются различные алгоритмы реализации операции умножения и, соответственно, несколько схем построения операционных блоков, обеспечивающих выполнение операции умножения.

Традиционная схема умножения похожа на известную из школьного курса процедуру записи «в столбик». Вычисление произведения двух n-разрядных двоичных чисел без знака сводится к формированию частичных произведений (ЧП) по одному на каждую цифру множителя, с последующим суммированием полученных ЧП. Перед суммированием каждое ЧП должно быть сдвинуто на один разряд относительно предыдущего согласно весу цифры множителя, которой это ЧП соответствует. Поскольку операндами являются двоичные числа, вычисление ЧП упрощается: если цифра множителя равна 0, то ЧП тоже равно 0, а если 1 — ЧП равно множимому. Перемножение двух n-разрядных двоичных чисел приводит к получению результата, содержащего 2n битов. Таким образом, алгоритм умножения предполагает последовательное выполнение двух операций - сложения и сдвига (рис. 9).

В зависимости от способа получения суммы частичных произведений (СЧП) возможны четыре варианта реализации «традиционной» схемы умножения. Из них нам интересны только два:

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

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

Варианты 1 и 2 называются алгоритмами сдвига вправо и сдвига влево соответственно. Далее мы рассмотрим оба алгоритма подробнее.

4.1 Умножение чисел без знака

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

Алгоритм сдвига вправо

Алгоритм сводится к следующим шагам:

1. Исходное значение суммы частичных произведений принимается равным нулю.

2. Анализируется очередная цифра множителя (анализ начинается с младшей цифры). Если она равна единице, то к СЧП прибавляется множимое, в противном случае (цифра равна нулю) прибавление не производится.

3. Выполняется сдвиг суммы частичных произведений вправо на один разряд,

4. Пункты 2 и 3 последовательно повторяются для всех цифровых разрядов множителя.

Процедура умножения иллюстрируется примером умножения 10 на 11 (рис. 10).

Первоначально множимое и множитель заносятся в n-разрядные регистры множимого (РМн) и множителя (РМт) соответственно, а все разряды 2n-разрядного регистра суммы частичных произведений (РЧП) устанавливаются в 0. Умножение происходит за n шагов. На каждом шаге, в зависимости от состояния младшего разряда регистра множителя, управляющего мультиплексором, на один из входов n-разрядного сумматора подается либо множимое, либо 0. На второй вход поступает содержимое n старших разрядов РЧП. Новое частичное произведение из сумматора пересылается в старшие разряды РЧП. Далее содержимое РЧП сдвигается на один разряд вправо, причем в освободившийся старший разряд регистра заносится значение переноса из старшего разряда сумматора. Поскольку мультиплексор управляется младшим разрядом РМт, то содержимое этого регистра также сдвигается на один разряд вправо. Описанная последовательность повторяется n раз. Более экономичным в плане аппаратуры является иное решение, когда вместо двух регистров — n-разрядного РМт и 2n-разрядного РЧП — используется один комбинированный 2n-разрядный регистр (показан на рис. 11 справа). Множитель первоначально заносится в младшие n разрядов этого регистра, а старшие разряды обнуляются. По мере сдвигов вправо младшие, уже проанализированные разряды множителя выталкиваются из регистра, освобождая место для очередной цифры СЧП. Обычно такой регистр строится из двух n-разрядных регистров, объединенных цепями сдвига. Дополнительно отметим, что если очередная цифра множителя равна 1, то для вычисления СЧП требуются операции сложения и сдвига, а при нулевой цифре множителя в принципе можно обойтись без сложения, ограничившись только сдвигом. Это, естественно, требует некоторого видоизменения схемы.

Алгоритм сдвига влево

Процедура традиционного умножения со сдвигом влево включает в себя следующие шаги:

1. Исходное значение суммы частичных произведений принимается равным нулю.

2. Анализируется очередная цифра множителя (анализ начинается со старшей цифры). Если она равна единице, то к СЧП прибавляется множимое, в противном случае (цифра равна нулю) прибавление не производится.

3. Выполняется сдвиг суммы частичных произведений влево на один разряд.

4. Пункты 2 и 3 последовательно повторяются для всех цифровых разрядов множителя.

К преимуществу алгоритма сдвига влево следует отнести то, что он позволяет совмещать во времени операции сложения и сдвига. Однако, по сравнению с алгоритмом сдвига вправо, он имеет и ряд недостатков. В первую очередь, СЧП и множитель не могут совместно использовать один и тот же регистр. Для реализации алгоритма требуется 2n-разрядный сумматор. Кроме того, схема со сдвигом влево неудобна при выполнении умножения над числами с разными знаками.

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