СОДЕРЖАНИЕ
Введение
1. Выполнение операции умножения в ЭВМ
2. Умножение чисел, представленных в форме с плавающей запятой
3. Методы ускорения операции умножения
4. Матричный метод умножения
5. Выполнение операции деления в ЭВМ
5.1 Деление чисел с восстановлением остатков
5.2 Деление без восстановления остатков
6. Способы ускоренного деления
7. Деление чисел в машинах с плавающей запятой
Выводы
Литература
Введение
Тема реферата «Выполнение операций умножения и деления в ЭВМ».
Цель работы – ознакомится с выполнением операций умножения и деления в ЭВМ, как с фиксированной, так и с плавающей запятой.
1. Выполнение операции умножения в ЭВМ
Операция умножения является наиболее частой после сложения. Умножение может выполняться суммированием сдвинутых на один или несколько разрядов частичных произведений, каждое из которых является результатом умножения множимого на соответствующий разряд (разряды) множителя.
При точном умножении двух чисел количество значащих цифр произведения может в пределе достичь двойного количества значащих цифр сомножителей. Еще сложнее возникает ситуация при умножении нескольких чисел. Поэтому в произведении только в отдельных случаях используют двойное количество разрядов.
Наиболее просто операция умножения выполняется в прямом коде. При этом на первом этапе определяется знак произведения путем сложения знаковых разрядов сомножителей по модулю 2, затем производится перемножение модулей сомножителей согласно двоичной таблице умножения. Результату присваивается полученный знак.
Так как умножение производится в двоичной системе счисления, частные произведения либо равны 0 (при умножении на 0), либо самому сомножителю (при умножении на 1), сдвинутому на соответствующее количество разрядов.
Произведение можно получить двумя путями:
1) сдвигом множимого на требуемое количество разрядов и прибавлением полученного очередного частичного произведения к ранее накопленной сумме частичных произведений;
2) сдвигом суммы ранее полученных частичных произведений на каждом шаге на 1 разряд и последующим прибавлением к сдвинутой сумме неподвижного множимого либо 0.
Причем каждый из этих методов может различаться еще и тем, с младших или со старших разрядов начинается умножение.
Пример.
А=0,1101; В=0,1011;
1а) 0,1101 1б) 0,1101
0,1011 0,1011
1101 1101
1101 0000
0000 1101
1101 1101
10001111 10001111
Основываясь на вышеизложенном можно создать 4 основных метода машинного умножения в прямом коде:
1) умножение младшими разрядами множителя со сдвигом накапливаемой суммы частных произведений вправо;
2) умножение младшими разрядами множителя со сдвигом множимого влево;
3) умножение старшими разрядами множителя со сдвигом накапливаемой суммы частных произведений влево;
4) умножение старшими разрядами множителя со сдвигом множимого вправо;
Рассмотрим более детально каждую из схем умножения.
1) умножение младшими разрядами множителя со сдвигом накапливаемой суммы частных произведений вправо.
Алгоритм получения результата по данному методу может быть следующим:
1) содержимое сумматора обнуляется;
2) множимое умножается на очередной разряд множителя;
3) результат суммируется с содержимым сумматора;
4) содержимое сумматора сдвигается на 1 разряд вправо;
5) пункты 2, 3, 4 повторяются n-1 раз.
Пример.
Заданы операнды А=0,0101; В=0,1011, выполнить операцию умножения.
Таблица 1
| № | Раз-ряд | Наимено-вание | ||||||||
| п/п | мн-ля | операции | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| обнуление | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
| 1 | В1
=1 |
Ах В1
|
0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| å | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | ||
| ® | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | ||
| 2 | В2
=1 |
Ах В2
|
0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| å | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | ||
| ® | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | ||
| 3 | В3
=0 |
Ах В3
|
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| å | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | ||
| ® | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | ||
| 4 | В4
=1 |
Ах В4
|
0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| å | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | ||
| ® | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
С=0,00110111.
2) умножение младшими разрядами множителя со сдвигом множимого влево.
Алгоритм получения результата по данному методу может быть следующим:
1) содержимое сумматора обнуляется;
2) множимое умножается на очередной разряд множителя;
3) результат суммируется с содержимым сумматора;
4) множимое сдвигается на 1 разряд влево;
5) пункты 2, 3, 4 повторяются n-1 раз.
Выполнение умножения по 3-му и 4-му способам умножения можно рассмотреть по аналогии к выше рассмотренным способам.
Анализ приведенных схем умножения показывает, что длительность процесса умножения по любой схеме составляет n циклов:
Ту
=nτц
.
Однако длительность циклов в разных схемах одинакова. Так во второй и четвертой схемах τц
=τсм
и, учитывая, что τсм
>τсдв
, эти схемы позволяют ускорить процесс выполнения операции умножения за счет совмещения операции сложения частичных произведений и сдвигов множимого;
2) по количеству оборудования предпочтение следует отдать первой, а потом третьей схеме умножения.
Наиболее удобными для применения в ЭВМ являются 1 и 4 схемы умножения.
2. Умножение чисел, представленных в форме с плавающей запятой
Если операнды заданы в форме с плавающей запятой:
А=a2ma
и B=b2mb
, то их произведение С=АхВ и С=с2mc
гдеC=a*b*2(ma+mb)
Алгоритм умножения нормализованных чисел состоит из следующих этапов:
1. Определение знака произведения путем сложения знаковых разрядов мантисс операндов по модулю 2.
2. Алгебраическое сложение порядков сомножителей в с целью определения порядка произведения.
3. Умножение модулей мантисс сомножителей по правилам умножения чисел с фиксированной запятой.
4. Нормализация и округление мантиссы результата. Следует учесть, что мантиссы сомножителей являются нормализованными числами. Поэтому денормализация мантиссы произведения возможна только на один разряд вправо. Она устраняется путем сдвига мантиссы на один разряд влево и вычитания 1 из порядка результата.
5. Присвоение знака результату.
Первые три операции могут выполняться одновременно, так как они независимы. Наличие операции определения знака произведения предполагает, что умножение мантисс выполняется в прямом коде.
При выполнении операции умножения в машине с плавающей запятой может получиться переполнение отрицательного порядка, которое будет интерпретировано как машинный нуль, если программой пользователя игнорируется признак исчезновения порядка. Может также возникнуть положительное переполнение порядка. В этом случае в первую очередь необходимо нормализовать мантиссу результата. Если и после этого переполнение порядка не устраняется, то машиной формируется признак переполнения порядка.
3. Методы ускорения операции умножения
Любое ускорение операции умножения даже ценой усложнения арифметических и логических схем позволяет существенно повысить производительность ЭВМ, т.к. примерно 70% машинного времени затрачивается на выполнение этой операции.
Известны способы ускорения умножения, направленные на сокращение общего количества и времени выполнения операций сложения, необходимых для образования произведения. Эти способы делятся на логические и аппаратные.
Под аппаратными понимают такие способы, которые требуют для своей реализации введения дополнительного оборудования в основные арифметические цепи, благодаря чему достигается совмещение во времени отдельных составных частей процесса умножения. Они подразделяются на способы 1-го и 2-го порядков. Для реализации способов 1-го порядка необходимо количество оборудования, пропорциональное числу разрядов машинного слова n. Для реализации способов 2-го порядка требуется объем оборудования, пропорциональный n2
.
Под логическими понимают такие способы ускорения, при реализации которых сохраняется основная структура арифметических цепей умножителя, а ускорение достигается только за счет усложнения схемы управления.
Простейшим логическим способом является пропуск тактов суммирования в тех случаях, когда очередная цифра множителя равна 0.
В среднем, количество сложений при этом сокращается вдвое.
Можно сократить и среднее и максимальное количество суммирований при использовании как прямых, так и инверсных передач множимого в сумматор. Здесь учитывается то обстоятельство, что время умножения значительно сокращается, если при наличии в разрядах множителя нескольких нулей подряд производить его сдвиг сразу на несколько разрядов. Для этого видоизменяют код множителя с целью представления его с меньшим количеством разрядов, содержащих единицу. Например, группу единиц в множителе 011. ..110 можно преобразовать в группу 100...00, т.е. перейти к системе с цифрами 1,0,.
Таким образом, в основе способа лежит представление числа как совокупности следующих последовательностей: нулей, единиц, нулей с изолированными единицами, единиц с изолированными нулями. При этом: два или более соседних нулей или соседних единиц рассматриваются как последовательность. Например, если умножение начинается с младших разрядов и множитель содержит последовательность единиц, то производится вычитание множимого с соответствующим (младшим) весом, а затем сдвиг через все эти единицы.
Сдвиг через последовательность единиц прекращается на первом нуле. Если сразу за этим нулем расположена единица, то множимое вычитается и выполняется сдвиг через последовательность единиц. Если за этим нулем непосредственно следует второй нуль, то множимое прибавляется, а затем выполняется сдвиг через последовательность нулей, который прекращается на первой единице.
Если за этой единицей следует ноль, то множимое прибавляется и производится сдвиг через последовательность нулей. Если за этой единицей непосредственно следует вторая единица, то производится вычитание множимого с соответствующим весом данного разряда, а затем выполняется сдвиг через последовательность единиц. Если в старшем разряде множителя стоит 1, входящая в последовательность единиц, то сдвиг необходимо продолжать до первого нуля после старшего разряда множителя.
Следует отметить, что при умножении со старших разрядов применяются несколько другие правила определения оптимального множителя. И в том и в другом случае в среднем на каждую операцию сложения выполняется сдвиг на 2,9 разряда, если схема рассчитана на сдвиг не более, чем на 6 разрядов одновременно.
В пределе среднее число сложений-вычитаний, приходящееся на один разряд множителя, равно 3-1
. Это наилучший результат, которого можно достичь при использовании логических методов.
Таким образом, переход от одной разновидности двоичной системы счисления к другой при преобразовании множителя позволяет получить выигрыш во времени выполнения операции в целом. При этом возникают определенной длины последовательности 0 или 1, что, в конечном счете, приводит к необходимости одновременного анализа нескольких разрядов множителя и сдвига на произвольное число разрядов.
Одновременное умножение на два разряда.
Количество циклов, необходимых для реализации в ЭВМ операции умножения, можно сократить, если в каждом цикле анализировать не один, а два или более разрядов множителя, выполняя после анализа одну передачу множимого в сумматор и сдвиг множителя на соответствующее число, т.е. два или более, разрядов. Для организации ускоренного умножения множитель можно разбить на группы по два разряда и преобразовать его таким образом, чтобы каждая группа содержала не более одной единицы, понимая под последней 1 или .
Для младшей пары разрядов при умножении с младших разрядов возможны следующие комбинации единиц и нулей в разрядах: 00, 01, 10 и 11.
Для первой комбинации не производится ни сложение, ни вычитание, для второй - суммирование множимого, для третьей - суммирование сдвинутого на 1 разряд влево множимого, т.е. умноженного на два, а для четвертой - вместо двух сложений при умножении без ускорения выполняется одно вычитание множимого и одно сложение после сдвига множимого на 2 разряда, т.е. пара разрядов множителя преобразуется к виду 10. Поскольку сложение после сдвига приходится на умножение на следующую пару разрядов, то вместо того, чтобы его выполнять добавляют единицу в следующую за данной пару разрядов. С учетом этого действия при умножении выполняются в соответствии с таблицей 2.
Описанная процедура повторяется для всех пар разрядов множителя, а также для одной пары разрядов левее запятой, т.к. может оказаться необходимым добавить к ней (к ее нулям) единицу.
Таблица 2
| Анализируемая пара разрядов | Перенос из предыдущей пары разрядов | Преобразованная пара разрядов | Примечание |
| 00 | 0 | 00 | |
| 01 | 0 | 01 | |
| 10 | 0 | 10 | Предварительный сдвиг множимого |
| 11 | 0 | 01 | Запоминается 1 для следующей пары разрядов |
| 00 | 1 | 01 | |
| 01 | 1 | 10 | Предварительный сдвиг множимого |
| 10 | 1 | 01 | Запоминается 1 для следующей пары |
| 11 | 1 | 10 | разрядов |
Следует отметить, что в общем случае при умножении на 2 разряда множителя двух знаковых разрядов в сумматоре недостаточно. Здесь возможны случаи при А →1, когда даже во втором знаковом разряде появляется единица переполнения, т.е. будет искажен знак частного произведения. Следовательно, при данном способе умножения сумматор должен иметь три знаковых разряда.
Следует отметить, что объем оборудования АУ при умножении на 2 разряда увеличивается незначительно по сравнению с АУ, работающим без ускорения.
Одновременное умножение на три и более разряда, для реализации которого применим подобный способ ускорения, используется реже, так как при этом увеличивается количество требуемых типов передач. Это приводит к значительному усложнению схем, реализующих умножение.
4. Матричный метод умножения
Когда множимое и множитель расположены в регистрах машины, нетрудно образовать сразу все частичные произведения. Следовательно, при наличии дополнительных сумматоров можно складывать сразу несколько частичных произведений, а в предельном случае и все. В этом случае формирование произведения можно себе представить как спуск по дереву сумматоров от слагаемых к их общей сумме. Время спуска по дереву будет зависеть от его организации и типа применяемых сумматоров. Рассмотрим схему умножения на примере двух четырехразрядных чисел:
| А= | а4
|
а3
|
а2
|
а1
|
|||
| В= | b4
|
b3
|
b2
|
b1
|
|||
| a4
b1 |
a3
b1 |
a2
b1 |
a1
b1 |
||||
| a4
b2 |
a3
b2 |
a2
b2 |
a1
b2 |
||||
| a4
b3 |
a3
b3 |
a2
b3 |
a1
b3 |
||||
| a4
b4 |
a3
b4 |
a2
b4 |
a1
b4 |
||||
| c8
|
c7
|
c6
|
c5
|
c4
|
c3
|
c2
|
c1
|
Эту схему умножения можно представить в виде матрицы (таблица 3), каждый элемент которой равен 0 или 1 для р=2. Для получения произведения двух чисел элементы матрицы надо суммировать в соответствии с порядком.
Таблица 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начения переносов с этих сумматоров должны быть слагаемы
Схема устройства для реализации этого дерева спуска, которое представляет собой одну из разновидностей матричного алгоритма умножения, представлена на рис. 1.
Для одноразрядных сумматоров время образования суммы больше, чем время образования переноса τп
, поэтому наибольшее время спуска по дереву данного вида есть Туск
= (n-1)(τсмì
+τn
); если только все конъюнкции вида ai
bj
поступают на дерево спуска одновременно. Это время складывается из спуска по самой длинной вертикали, а затем последовательного распространения переноса через сумматоры нижнего ряда вплоть до самого левого. Рассмотренная структура дерева спуска не единственная Время спуска можно еще уменьшить, преобразовав дерево спуска.
5. Выполнение операции деления в ЭВМ
Операция деления встречается сравнительно редко (Р=0,02), однако, реализация ее по подпрограмме занимает достаточно большое время. Поэтому в большинстве современных ЭВМ деление реализуется специальными операционными блоками.
Деление в ЭВМ, также как и умножение, проще всего выполняется в прямом коде. Но в отличие от умножения дробных чисел, где не может возникнуть переполнение разрядной сетки, при делении правильных дробей такое переполнение возможно в случае, когда делимое больше делителя. Признаком переполнения является появление целой части в частном, что грубо искажает результат.
Знак частного при делении определяется сложением по модулю 2 знаковых разрядов делимого и делителя и присваивается частному в конце операции деления.
Частное определяется путем деления модулей исходных чисел. При этом во избежание переполнения разрядной сетки должно соблюдаться условие:
|А|<|В|
где А - делимое, В - делитель. Кроме того: В¹0.
Известны два основных алгоритма выполнения операции деления:
- деление с восстановлением остатков ;
- деление без восстановления остатков.
5.1 Деление чисел с восстановлением остатков
Пусть необходимо разделить А на В. Тогда частное от деления
Yi
=А/В = 0,у1
у2
у3
... уі
-1
уі
= у1
2-1
+у2
2-2
+у3
2-3
... уі
-1
2-і -1
+уі
2-і
(1.1.)
При любом значении і должно выполняться неравенство:
0 ≤ А - ВYi
≤ В2-і
т.е. остаток от деления должен быть меньше делителя, умноженного на 2-і
, или:
0 ≤ (А - ВYi
)2і
≤ В, обозначим (А - ВYi
) 2і
=Rі
и получим:
0 ≤ Rі
≤ В. (1.2)
При делении цифры частного определяются последовательно, начиная со старшего разряда. Допустим, что в результате выполнения і циклов получены старшие і разрядов частного, т.е. приближенное значение частного Yi
. В следующем (і+1)-цикле будет получено значение (і+1)-го разряда частного. Исходными данными для этого цикла являются Yi
и 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
=2Ri
< В. (1.5.)
Если уі
+1
=1, то Yі+
1
= Yі
+ 2-(
і+1)
; (1.6.)
Rі+1
=(А-Вх Yі+
1
) х 2і+1
= (А - В х Yi
-B х 2-(
і+1)
2(
і+1)
=2 Rі
- В, (1.7.)
т.е. цифра частного равна 1, если выполняется условие:
0 ≤ Rі+1
=2Ri
-В < В (1.8.)
или В ≤ 2Ri
< 2В. (1.9.)
Так как всегда выполняется одно из условий (1.5.) или (1.9.), то для определения текущей цифры частного достаточно проверить одно из них.
Обычно проверяют условие (1.5.). Левая часть этого неравенства выполняется заведомо, так как согласно (1.2.) 0 ≤ Rі
, то есть очередной остаток перед началом следующего шага деления всегда является положительным числом.
Для проверки правой части неравенства сравним разность (2Rі
-В) сравним с нулем. Если эта разность окажется отрицательной, то в (і+1) разряд частного запишем 0 и для подготовки исходных данных для (і+2)-го цикла определим Rі+1
следующим образом:
Rі+1
=(2Ri
-В) + В =2Ri
. (1.10.)
Если разность 2Ri
-В окажется положительной, то запишем в (і+1) разряд частного 1, а в качестве исходного значения для следующего (і+2)-го цикла используем вычисленную разность (см. 1.7.): Rі+1
=2 Rі
- В,
Исходными данными для 1-го цикла являются:
Y0
=0
R0
=(А-ВY0
)20
= А< В
т.е. по условию неравенства (1.2.) выполняется и перед началом первого цикла. После окончания n-го цикла получим n-значное частное Yn
, вычисленное с недостатком Rn
=(A - BYn
)2n
,который равен остатку от деления А на В, сдвинутому влево на n разрядов.
Правило деления с восстановлением остатков формулируется следующим образом.
Делитель вычитается из делимого и определяется знак нулевого (по порядку) остатка. Если остаток положительный, т.е. |A|>|В|, то в псевдознаковом разряде частного проставляется 1, при появлении которой формируется признак переполнения разрядной сетки и операция прекращается. Если остаток отрицательный, то в псевдознаковом разряде частного записывается 0, а затем производится восстановление делимого путем добавления к остатку делителя. Далее выполняется сдвиг восстановленного делимого на один разряд влево и повторное вычитание делителя. Знак получаемого таким образом остатка определяет первую значащую цифру частного: если остаток положителен, то в первом разряде частного записывается 1, если отрицательный, то записывается 0. Далее, если остаток положителен, то он сдвигается влево на 1 разряд и из него вычитается делитель для определения следующей цифры частного. Если остаток отрицателен, то к нему прибавляется делитель для восстановления предыдущего остатка, затем восстановленный остаток сдвигается на 1 разряд влево и от него вычитается делитель для определения следующей цифры частного и т.д. до получения необходимого количества цифр частного с учетом одного разряда для округления, т. е. до обеспечения требуемой точности деления.
Пример.
А=0,10011; В=0,11001; [-B]доп
= 11,00111; |В|= 0,11001
1. Определение знака частного: 0Å0=0 2. Определения модуля частного
| № цикла | № такта | Наименование операции | Дей-ствие | Разряды частного |
||||||||||
| 0 | 1 | Вычит. делит. | А | 00 | 10011 | |||||||||
| 2 | из делимого | [-B]д
|
11 | 00111 | ||||||||||
| R0
|
11 | 11010 | 0, | 1 | 1 | 0 | 0 | |||||||
| 3 | Восстановл. | +В | 00 | 11001 | ||||||||||
| 0-остатка | R1
1 |
00 | 10011 | |||||||||||
| 1 | 1 | Сдвиг остатка | ¬R1
|
01 | 00110 | |||||||||
| 2 | Вычит. делит. | [-B]д
|
11 | 00111 | ||||||||||
| формирование | R2
1 |
00 | 01101 | |||||||||||
| разряда частн. | ||||||||||||||
| 2 | 1 | Сдвиг остатка | ¬R2
|
00 | 11010 | |||||||||
| 2 | Вычит. делит. | [-B]д
|
11 | 00111 | ||||||||||
| формирование | R3
1 |
00 | 00001 | |||||||||||
| разряда частн. | ||||||||||||||
| 3 | 1 | Сдвиг остатка | ¬R3
|
00 | 00010 | |||||||||
| 2 | Вычит. делит. | [-B]д
|
11 | 00111 | ||||||||||
| формирование | 11 | 01001 | ||||||||||||
| разряда частн. | ||||||||||||||
| 3 | Восстан. ост. | +В | 00 | 11001 | ||||||||||
| R4
1 |
00 | 00010 | ||||||||||||
| 4 | 1 | Сдвиг остатка | ¬R4
|
00 | 00100 | |||||||||
| 2 | Вычит. делит. | [-B]д
|
11 | 00111 | ||||||||||
| формирование | 11 | 01011 | ||||||||||||
| разряда частн. | ||||||||||||||
| 3 | восстановл. ост | +В | 00 | 11001 | ||||||||||
| 1 | 00 | 00100 | ||||||||||||
С=0,1100
Таким образом, цифры частного получаются как инверсное значение знаковых разрядов текущего остатка, которые принимают значение 00 или 11. Однако при сдвиге остатка влево в знаковых разрядах может возникнуть сочетание 01. В некоторых случаях, для того чтобы цифры частного формировались как прямое значение знакового разряда текущего остатка, деление выполняют с инверсными знаками. При этом делимое передается в сумматор не прямым, а инверсным кодом, а на нулевом шаге выполняется операция «+В», вместо операции «—В».
5.2 Деление без восстановления остатков
Рассмотренный способ деления с восстановлением остатков является аритмичным процессом с переменным числом шагов того или иного вида в каждом конкретном случае (3 шага при 2Ri < В и 2 шага при 2Ri>B). Для ритмизации процесса на каждую цифру частного необходимо затратить по 3 шага, в результате чего увеличивается время выполнения операции. Вместе с тем, операцию можно упростить и получить каждую цифру частного за 2 шага.
Рассмотрим случай, когда Ri <0. В предыдущем способе в этом случае выполнялись следующие операции.
Восстановление остатка:
R’і
= 2 Rі
+|В|=2 Rі-1
-|B|+|B|=2 Rі-1
Сдвиг восстановленного остатка влево:
¬R'i
= 2 R'i
= 2 Ri
-1
х 2 = 4 Ri
-1
.
Вычитание модуля делителя из восстановленного и сдвинутого влево остатка для определения следующего остатка:
Rі+1
=4 Rі-1
-|B|
Если не восстанавливать остаток, а сразу сдвинуть отрицательный Rі
на один разряд влево, то получим
R’і+1
= 2 Rі
=2(2 Rі-1
-|B|)=4Rі-1
- 2 |B|.
Результат в данном случае отличается от действительного на величину + |B|. Поэтому в качестве второго шага необходимо произвести коррекцию результата на эту величину:
Rі+1
=4 Rі-1
-2|B|+|B=4 Rі-1
-|B|
В результате получаем требуемую величину последующего остатка Rі+1
, за 2 шага.
Таким образом, чтобы определить очередную цифру частного, необходимо сдвинуть текущий остаток влево на один разряд, а затем алгебраически прибавить к нему модуль делителя, которому приписывается знак, противоположный знаку текущего остатка. Знак полученного таким образом следующего остатка и определяет следующую цифру частного: если остаток положительный, то в частном записывается 1, если отрицательный - записывается 0. Операция сдвигов и алгебраических сложений повторяется до тех пор, пока в частном не получится требуемое количество цифр.
Пример
Заданы А=0,101; В=0,110 [-B]доп
= 11,010; |В|= 0,110
1. Определение знака частного: 0Å0=0 2. Определения модуля частного
| № цикла | № такта | Наименование операции | Действие | Разряды частного | ||||||||||
| 0 | Вычит. делит. | А | 00 | 101 | ||||||||||
| из делимого | [-B]д
|
11 | 010 | |||||||||||
| R0
|
11 | 111 | 0, | 1 | 1 | 0 | 0 | |||||||
| 1 | 1 | Сдвиг остатка | ¬R0
|
11 | 110 | |||||||||
| 2 | Прибавление | +В | 00 | 110 | ||||||||||
| формирование | R1
1 |
00 | 100 | |||||||||||
| разряда частн. | ||||||||||||||
| 2 | 1 | Сдвиг остатка | ¬R1
|
01 | 000 | |||||||||
| 2 | Вычит. делит | [-B]д
|
11 | 010 | ||||||||||
| формирование | R2
1 |
00 | 010 | |||||||||||
| разряда частн. | ||||||||||||||
| 3 | 1 | Сдвиг остатка | ¬R2
|
00 | 100 | |||||||||
| 2 | Вычит. делит. | [-B]д
|
11 | 010 | ||||||||||
| формирование | R3
|
11 | 110 | |||||||||||
| разряда частн. | ||||||||||||||
| 4 | 1 | Сдвиг остатка | ¬R3
|
11 | 100 | |||||||||
| 2 | Прибавл. дел. | +B | 00 | 110 | ||||||||||
| формирование | 00 | 010 | ||||||||||||
| разряда частн. | ||||||||||||||
С=0,1100
В настоящее время во всех ЭВМ деление производится по способу без восстановления остатков. Это, во-первых, упрощает схему управления процессом деления и, во-вторых, увеличивает быстродействие ЭВМ, так как длительность операции деления без восстановления остатков равна минимальной длительности операции деления с восстановлением остатков.
При выполнении операции деления результат получится одинаковым, если сдвигать остатки от деления влево либо делитель вправо. Следовательно, возможны две схемы выполнения деления:
1) деление без восстановления остатков со сдвигом делителя вправо;
2) деление без восстановления остатков со сдвигом остатка влево.
Для реализации второго варианта необходимы: n-разрядный регистр делителя; (n+ 1)-разрядный регистр частного со сдвигом влево; n- или (n + 1)-разрядный сумматор со сдвигом влево и схема управления. Анализ обеих схем показывает, что второй вариант примерно на 40 % экономичнее по оборудованию по сравнению с первым. Выбор типа длительного устройства при проектировании машины обычно не является самостоятельной задачей. Поэтому на практике вначале по заданным техническим условиям выбирается схема множительного устройства вследствие того, что умножение является примерно в 10 раз более частой операцией. После этого выбирается наиболее совместимая с устройством умножения схема делительного блока. Однако при проектировании специализированных ЭВМ может быть принят другой порядок выбора структур отдельных устройств. Если сравнивать приведенные схемы деления со схемами множительных устройств, то оказывается, что схема первого варианта деления во многом совпадает с четвертой схемой умножения. Второй вариант схемы деления хорошо совместим с третьей схемой умножения.
6. Способы ускоренного деления
Необходимость ускорения деления следует из наличия весьма эффективных методов ускорения умножения. Способы ускоренного деления делятся на две группы: для первой группы в каждом цикле формируется одна или несколько цифр частного и новый остаток; вторая группа предполагает выполнение деления через умножение или с использованием другой процедуры.
Суть одного из способов ускоренного деления первой группы состоит в том, что в частное можно записать сразу последовательность одинаковых цифр (нулей или единиц), если в результате очередного шага деления получен остаток по абсолютной величине либо достаточно малый, либо близкий к делителю. В первом случае, если остаток имеет k нулевых старших разрядов, то для определения очередных цифр частного нет нужды вычитать делитель k раз из остатка. Необходимо в k очередных разрядов частного сразу записать нули, сдвинуть остаток на k разрядов влево, прибавить к нему алгебраически делитель и продолжить операцию деления.
Во втором случае нужно вначале произвести вычитание делителя из остатка, затем разность сдвинуть на k разрядов влево, после чего к полученному числу прибавить делитель. При этом в частное записывается k единиц.
7. Деление чисел в машинах с плавающей запятой
Если числа А и В заданы в нормальной форме, то их частное будет равно:
С =a:b=(a:b) 2 (
m
а-
mb
)
где а и b - мантиссы, а ma
и mb
— порядки соответственно чисел А и В. Отсюда следует, что операция деления в машинах с плавающей запятой выполняется в пять этапов.
1-й этап. Определение знака частного путем сложения по модулю 2 знаковых цифр мантисс операндов.
2-й этап. Деление модулей мантисс операндов по правилам деления чисел с фиксированной запятой.
3-й этап. Определение порядка частного путем вычитания порядка делителя из порядка делимого.
4-й этап. Нормализация результата и его округление.
5-й этап. Присвоение знака мантиссе результата.
Два первых этапа полностью совпадают с этапами деления чисел с фиксированной запятой. Третий этап представляет собой обычное сложение в инверсных кодах.
При делении нормализованных чисел денормализация результата возможна только влево и только на один разряд. Это обусловлено тем, что мантисса любого нормализованного числа лежит в пределах
2-1
£ |а|< 1— 2-
n
Тогда наименьшая и наибольшая возможные величины мантиссы частного равны соответственно
т. е. мантисса частного лежит в пределах 2-1
£ |y|< 2.
Поэтому на четвертом этапе может возникнуть необходимость нормализации мантиссы частного путем ее сдвига вправо на один разряд и увеличения порядка частного на единицу. Если же перед делением сдвинуть делимое на один разряд вправо, то на 4-м этапе может потребоваться нормализация результатов влево на 1 разряд.
При выполнении третьего (определение порядка) этапа порядок частного может оказаться больше допустимого, т. е. произойдет переполнение разрядной сетки, которое расценивается как аварийная ситуация. Может быть также получен порядок частного, который меньше допустимого. Если на втором этапе вычислено частное |y| > 1, то на четвертом этапе при сдвиге частного вправо его порядок должен быть увеличен на единицу. При этом становится окончательно ясно, во-первых, возникло ли переполнение разрядной сетки порядка или нет, во-вторых, будет ли порядок частного меньше допустимого значения. Если имеет место исчезновение порядка, то результат деления по указанию программиста заменяется машинным нулем.
Выводы
В процессе написания реферата мы ознакомились с:
- выполнением операций умножения в ЭВМ;
- умножением чисел, представленных в форме с плавающей запятой;
- методами ускорения операции умножения;
- матричным методом умножения;
- выполнением операций деления в ЭВМ;
- делением чисел с восстановлением остатков;
- делением без восстановления остатков;
- способами ускоренного деления;
- делением чисел в машинах с плавающей запятой.
Литература
1. Самофалов К.Г., Романкевич А.М., и др. Прикладная теория цифровых автоматов. - Киев. “Вища школа” 1987.
2. Соловьев Г.Н. Арифметические устройства ЭВМ. - М. “Энергия”. 1978.
3. Савельев А.Я. Прикладная теория цифровых автоматов - М. “Высшая школа”. 1987.
4. Каган Б.М. Электронные вычислительные машины и системы. - М. Энергоатомиздат. 1985.
5. Лысиков Б.Г. Арифметические и логические основы цифровых автоматов. Минск. “Вышэйшая школа”. 1980.