Ускорение операции умножения
По времени выполнения операция умножения относится к длинным операциям. Затраты времени на умножение двух чисел в прямом коде можно оценить следующей формулой (для случая последовательного анализа разрядов множителя):
,
где 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