Матричный метод умножения

4. Матричный метод умножения

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

			А=	а4	а3	а2	а1
			В=	b4	b3	b2	b1
				a4b1	a3b1	a2b1	a1b1
			a4b2	a3b2	a2b2	a1b2
		a4b3	a3b3	a2b3	a1b3
	a4b4	a3b4	a2b4	a1b4
c8	c7	c6	c5	c4	c3	c2	c1

Эту схему умножения можно представить в виде матрицы (таблица 3), каждый элемент которой равен 0 или 1 для р=2. Для получения произведения двух чисел элементы матрицы надо суммировать в соответствии с порядком.

Таблица 3

	аi
bi	а4	а3	а2	а1
b1	a4b1	a3b1	a2b1	a1b1
b2	a4b2	a3b2	a2b2	a1b2
b3	a4b3	a3b3	a2b3	a1b3
b4	a4b4	a3b4	a2b4	a1b4

a3b2

a4b1

a2b2

a3b1

a1b2

a2b1

a1b1

С

м

С

м

С

м

a3b3

a4b2

a2b3

a1b3

C1

С

м

С

м

С

м

C2

a4b4

a3b4

a4b3

a2b4

a1b4

С

м

С

м

С

м

C3

П

а

р

а

л

л

е

л

ь

н

ы

й

с

у

м.

C8

C7

C6

C5

C4

Рисунок 1- Схема устройства для реализации матричного метода

Элементы, составляющие каждый і-й столбец матрицы, просуммируем с помощью обычных трехвходовых двоичных сумматоров. 3начения переносов с этих сумматоров должны быть слагаемыми для (i+1)-гo столбца. Это приведет к тому, что в каждом (i+1)-м столбце появление слагаемых будет происходить с запаздыванием по времени относительно i-гo столбца.

Схема устройства для реализации этого дерева спуска, которое представляет собой одну из разновидностей матричного алгоритма умножения, представлена на рис. 1.

Для одноразрядных сумматоров время образования суммы больше, чем время образования переноса τ_п, поэтому наибольшее время спуска по дереву данного вида есть Т_уск= (n-1)(τ_смì+τ_n); если только все конъюнкции вида a_ib_jпоступают на дерево спуска одновременно. Это время складывается из спуска по самой длинной вертикали, а затем последовательного распространения переноса через сумматоры нижнего ряда вплоть до самого левого. Рассмотренная структура дерева спуска не единственная Время спуска можно еще уменьшить, преобразовав дерево спуска.

5. Выполнение операции деления в ЭВМ

Операция деления встречается сравнительно редко (Р=0,02), однако, реализация ее по подпрограмме занимает достаточно большое время. Поэтому в большинстве современных ЭВМ деление реализуется специальными операционными блоками.

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

Знак частного при делении определяется сложением по модулю 2 знаковых разрядов делимого и делителя и присваивается частному в конце операции деления.

Частное определяется путем деления модулей исходных чисел. При этом во избежание переполнения разрядной сетки должно соблюдаться условие:

|А|<|В|

где А - делимое, В - делитель. Кроме того: В¹0.

Известны два основных алгоритма выполнения операции деления:

- деление с восстановлением остатков ;

- деление без восстановления остатков.

5.1 Деление чисел с восстановлением остатков

Пусть необходимо разделить А на В. Тогда частное от деления

Y_i=А/В = 0,у₁у₂у₃... у_і-1у_і= у₁ 2^-1 +у₂2^-2 +у₃2^-3 ... у_і-12^{-і -1}+у_і2^-і (1.1.)

При любом значении і должно выполняться неравенство:

0 ≤ А - ВY_i ≤ В2^-і

т.е. остаток от деления должен быть меньше делителя, умноженного на 2^-і , или:

0 ≤ (А - В Y_i )2^і ≤ В, обозначим (А - В Y_i ) 2^і =R_і и получим:

0 ≤ R_і ≤ В. (1.2)

При делении цифры частного определяются последовательно, начиная со старшего разряда. Допустим, что в результате выполнения і циклов получены старшие і разрядов частного, т.е. приближенное значение частного Y_i. В следующем (і+1)-цикле будет получено значение (і+1)-го разряда частного. Исходными данными для этого цикла являются Y_i и R_і.

Цифра у_і+1 может иметь одно из двух значений:

1 или 0. Если у_і+1=0, то

Y_і+1= Y_і+ у_і+1х 2^-(і+1)= Y_і; (1.3.)

R_і+1=(А-В Y_і+1) х 2^і+1= 2 R_і, (1.4.)

т.е. в частном записывается 0 при условии 0 ≤ R_і+1=2R_i < В. (1.5.)

Если у_і+1=1, то Y_і+1= Y_і+ 2^-(і+1); (1.6.)

R_і+1=(А-В х Y_і+1) х 2^і+1= (А - В х Y_i-B х 2^-(і+1) 2^(і+1)=2 R_і- В, (1.7.)

т.е. цифра частного равна 1, если выполняется условие:

0 ≤ R_і+1=2R_i -В < В (1.8.)

или В ≤ 2R_i < 2В. (1.9.)

Так как всегда выполняется одно из условий (1.5.) или (1.9.), то для определения текущей цифры частного достаточно проверить одно из них.

Обычно проверяют условие (1.5.). Левая часть этого неравенства выполняется заведомо, так как согласно (1.2.) 0 ≤ R_і, то есть очередной остаток перед началом следующего шага деления всегда является положительным числом.

Для проверки правой части неравенства сравним разность (2R_і-В) сравним с нулем. Если эта разность окажется отрицательной, то в (і+1) разряд частного запишем 0 и для подготовки исходных данных для (і+2)-го цикла определим R_і+1 следующим образом:

R_і+1=(2R_i -В) + В =2R_i . (1.10.)

Если разность 2R_i -В окажется положительной, то запишем в (і+1) разряд частного 1, а в качестве исходного значения для следующего (і+2)-го цикла используем вычисленную разность (см. 1.7.): R_і+1=2 R_і- В,

Исходными данными для 1-го цикла являются:

Y₀=0

R₀=(А-ВY₀)2⁰= А< В

т.е. по условию неравенства (1.2.) выполняется и перед началом первого цикла. После окончания n-го цикла получим n-значное частное Y_n, вычисленное с недостатком R_n=(A - BY_n)2ⁿ,который равен остатку от деления А на В, сдвинутому влево на n разрядов.

Правило деления с восстановлением остатков формулируется следующим образом.

Делитель вычитается из делимого и определяется знак нулевого (по порядку) остатка. Если остаток положительный, т.е. |A|>|В|, то в псевдознаковом разряде частного проставляется 1, при появлении которой формируется признак переполнения разрядной сетки и операция прекращается. Если остаток отрицательный, то в псевдознаковом разряде частного записывается 0, а затем производится восстановление делимого путем добавления к остатку делителя. Далее выполняется сдвиг восстановленного делимого на один разряд влево и повторное вычитание делителя. Знак получаемого таким образом остатка определяет первую значащую цифру частного: если остаток положителен, то в первом разряде частного записывается 1, если отрицательный, то записывается 0. Далее, если остаток положителен, то он сдвигается влево на 1 разряд и из него вычитается делитель для определения следующей цифры частного. Если остаток отрицателен, то к нему прибавляется делитель для восстановления предыдущего остатка, затем восстановленный остаток сдвигается на 1 разряд влево и от него вычитается делитель для определения следующей цифры частного и т.д. до получения необходимого количества цифр частного с учетом одного разряда для округления, т. е. до обеспечения требуемой точности деления.

Пример.

А=0,10011; В=0,11001; [-B]_доп= 11,00111; |В|= 0,11001