Ускорение операции умножения

По времени выполнения операция умножения относится к длинным операциям. Затраты времени на умножение двух чисел в прямом коде можно оценить следующей формулой (для случая последовательного анализа разрядов множителя):

,

где tсдв - время выполнения сдвига числа на один разряд; tсл - время суммирования на сумматоре; pi - вероятность появления единицы в разрядах множителя; n - количество разрядов множителя.

Существуют несколько методов ускорения процедуры умножения: анализ двух разрядов множителя одновременно, анализ произвольного количества разрядов множителя, умножение в системе счисления с основанием q=2kи матричные методы умножения.

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

Если множимое X и множитель Y, а его два очередных младших разряда (y1y0), то в зависимости от результата анализа этих разрядов предусматриваются следующие действия.

Если y1y0 = 00, то выполняются только процедуры: ПС и SС = SС-1.

Если y1y0 = 01, то выполняются процедуры: Р = P + X, ПС и SС = SС-1.

Если y1y0 = 10, то выполняются процедуры: сдвиг множимого влево на 1 разряд, т.е. умножение его на два, P = P + X, ПС и SС = SС-1.

Если y1y0 = 11, то выполняются три раза P = P + X и ПС, SС = SС-1.

Когда SС = 0 - операция умножения заканчивается.

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

Рассмотрим пример ускоренного умножения 310 на 7810, т.е. когда X = 3, а

Y = 78. Если n = 10, то X = 0000000112, Y = 00010011102, а SС = 5.

512 256 128 64 32 16 8 4 2 1

X 00 00 00 00 11 множимое

Y 00 01 00 11 10 множитель

R 00 11 10 10 10 ответ = 234

В некотором регистре P будем формировать частные произведения.

1) Анализ 2-х младших разрядов Y. y1y0 = 10. Сдвинуть X на 1 разряд влево и прибавить к P.

P 00 00 00 00 00

+X 00 00 00 01 10

P 00 00 00 01 10 сдвиг на 2 разряда P и Y

P 00 00 00 00 01 ---- 10 00 01 00 11 Y

2) y1y0 = 11, _ 3 раза прибавляем X к P

P 00 00 00 00 01

+X 00 00 00 00 11

P 00 00 00 01 00

+X 00 00 00 00 11

P 00 00 00 01 11

+X 00 00 00 00 11

P 00 00 00 10 10 сдвиг на 2 разряда P и Y

P 00 00 00 00 10 ---- 10 10 00 01 00 Y

3) y1y0 = 00, сдвиг на 2 разряда P и Y

P 00 00 00 00 00 --- 10 10 10 00 01 Y

4) y1y0 = 01

P 00 00 00 00 00

+X 00 00 00 00 11

P 00 00 00 00 11 сдвиг на 2 разряда P и Y

P 00 00 00 00 00 --- 11 10 10 10 00 Y

5) y1y0 = 00, сдвиг на 2 разряда P и Y

P 00 00 00 00 00 --- 00 11 10 10 10 Y = 23410