Реферат: Выполнение операций умножения и деления в ЭВМ

Таблица 3

аi
bi	а4	а3	а2	а1
b1	a4 b1	a3 b1	a2 b1	a1 b1
b2	a4 b2	a3 b2	a2 b2	a1 b2
b3	a4 b3	a3 b3	a2 b3	a1 b3
b4	a4 b4	a3 b4	a2 b4	a1 b4

a3 b2

a4 b1

a2 b2

a3 b1

a1 b2

a2 b1

a1 b1

С

м

С

м

С

м

a3 b3

a4 b2

a2 b3

a1 b3

C1

С

м

С

м

С

м

C2

a4 b4

a3 b4

a4 b3

a2 b4

a1 b4

С

м

С

м

С

м

C3

П

а

р

а

л

л

е

л

ь

н

ы

й

с

у

м.

C8

C7

C6

C5

C4

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

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

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

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

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

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

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

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

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

|А|<|В|

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

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

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

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

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

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

Y_i =А/В = 0,у₁ у₂ у₃ ... у_{і -1} у_і = у₁ 2^-1 +у₂ 2^-2 +у₃ 2^-3 ... у_{і -1} 2^{-і -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.)