Основы информатики_Савельев А.Я_Учебник_2001
.pdf6I Методы деления двоичных чисел
Вобщем случае «школьный» алгоритм деления на примере двоичных чисел выглядит следующим образом:
делимое — |
1100100 |
IIOIO |
—делитель |
делитель — |
1010 |
1010 |
-—частное |
остаток — |
0101 |
|
|
|
1010 |
|
|
|
1011 |
|
|
воссчаиовление остатка - |
1010 |
|
|
|
01010 |
|
|
|
1010 |
|
|
|
0000 |
|
|
Здесь цифры частпою получаются последовательно, начиная со стар шего разряда иугем вычитания делителя из полученного остатка. Ксли по лучен Гюложигельный остаиж, то цифра частного равна единице; если ос таток очрнцательный, го цифра частного равна нулю, при этом восстанавливается предыдущий положительный остаток.
В случае ноложите;гьного остатка для гюлучения следующей цифры частого 1юсле/(ннй остаток сдвигается влево на один разряд (либо дели- мгпъ и11[);1во па один разряд) и из него вычитается делитель и т. д.
И cjiy4ae отрицателыюго остатка восстанавливается предыдущий тюJK)жиleJи>ilЫH ociaTOK прибавлением к отрицательному остатку делителя, и В(юс1аиовлеппый остаюк сдвигается на один разряд влево (либо сдвигается дcJrпieJи. вправо па один разряд) и из него вычитается делитель. Такой алinpniM деления получил название алгоритма деления с восстановлением осинка. <|)ормально все действия можно описать следующим образом.
Пусп. |
А |
делимое, В — |
делитель и С — частное, при этом |
А = 0 , а^а^ |
"•(•'„'- |
В - О , h^2 •••b„,C |
- О, CjC^ ... с„ . |
Для реализации алгоритма деления двоичных чисел, представленных в (|)орме с ((шксированной занятой, необходимо, чтобы выполнялось условие \yi\ < [Я[. IxjHi ло условие не выполпяегся, ю в первом шаге возникает пеpeiHunienne разрядной сетки и операция не выполняется. Если Ы < | 5 | , то иц первом maie операции проводится сдвиг делителя и определяется оста
ток А^=- А -В'2 |
' . |
Пусть /J| > 0 , тогда С, = I . Процесс деления продолжается дальше:
Ау^А^-В-2 ^
141
|
6 Выполнение операций деления чисел на двоичных сумматорах |
|
Пусть А<0, |
тогда С^ = О и проводится восстановление остатка /(,: |
|
Aj - Д |
^В-Т'-. |
|
Эгот остаток принимается за A'j и деление продолжается дальше сле |
||
дующим образом: А^ - |
A'j- В- 2"^. |
|
Таким образом, алгоритм деления можно описать в общем виде на 7-м |
||
шаге: |
|
|
|
4 = 4 _ i - f i - 2 " ' . |
(6.1) |
Ecjm Д > 0 , то С,=] |
и переход к следующему шагу; если |
Д < 0 , то |
С\ ^ О и восстановление остатка |
|
|
|
Д_1 =А,^-В-2-', |
(6.2) |
который принимается за остаток А], и процесс продолжается но формуле (6.1). Следовате;гьно, операция деления сводится к носледовачельпому вы полнению вычитании (сложений) в сумматоре и сдвигам делителя. Сдви|- дeJПJтeля может быть заменен сдвигом содержимого сумматора в противо положную сторону.
Алгоритм деления, основанный на реализации формул (6.1) и (6.2), на
зывается делением с восстановлением |
остатка. |
|
|
|
|
||||
Рассмотрим процесс |
восстановления остатка. |
-4, < О |
н С, ={), то fia |
||||||
следующем |
шаге выполняются действия по формуле А,^^ |
- ,4^'- Л-2"''*'* = |
|||||||
= А^ + В-2~' |
- 5 - 2^''*" . После преобразования получим |
|
|
||||||
|
|
|
< 1 = 4 + f i - 2 " " ^ " . |
|
|
|
(6.3) |
||
Таким образом, появляется возможность построить алгоритм деления |
|||||||||
по следующей схеме: Д |
- Д_| - fi • 2"^', если Д |
2: О, то С, = I |
и переход к |
||||||
следующему шагу; если |
Д < 0 , то |
С, = О и |
продолжение |
по формуле |
|||||
Д^1 - |
Д + fi- 2 '"^'*. При этом, если Д^, > О , то |
С,^| =: I н переходим к фор |
|||||||
муле |
(6.1), если Д^, < 0 , |
то |
C^^i - О |
и переходим |
к формуле |
(6.3). Такой |
|||
алгоритм называется делением |
без восстановления |
остатков. |
|
||||||
Реализация рассмотренных алгоритмов деления возможна с гюмощью двоичных сумматоров обратного или дополнителыюго кода. /1^ля хранения дели1еля, де1Н1Мого и накопления очередных разрядов частного выдсля101ся регистры. Минимальный состав блоков, необходимый для вьиюлиения де лений, показан на рис. 6Л в двух вариантах. Варианты отличаются сгюсо-
142
6 2 Де-ь ? чисел, представленных в форме с фиксированной запятой
бом решшзации сдвига. В варианте рис. 6.1, а осуществлен сдвиг содержи мого регистра делителя, а в варианте рис. 6.1, б — сдвиг содержимого сум матора. Стрелки на рисунке указывают направление сдвига. Индекс (и) ука зывает ориентировочное количество разрядов в цифровой части сумматора и регистра делителя. В дальнейших разделах при выполнении примеров будет использована структура, показанная на рис. 6.1, а.
Рис. 6.1. CrpyKTvpfrbie схемы ляя реализации
6.2. Деление чисел, представленных в форме с фиксированной запятой, на сумматорах
обратного и дополнительного кода
i !ри делении знаковая и цифровая части частного получаются раздельно. Знак част1гого образуется по формуле
1Ь\я образования цифр частного воспользуемся следующим соответстви ем, R котором приведены логические действия над остатками и делителем:
Знак делимого/) |
, . .. |
+ |
+ |
|
|
'Знак делителя Й |
|
+ |
- |
+ |
|
Чю ;ie;iafb » ey\fMaiope |
/J, + В -2"' |
А, + В-2~' |
А, + В-2~' |
А, + В -2' |
|
(Символ « » указывает на изменение знака на противоположный на оче редном шаге деления.)
Иа суммаюрах обратною кода возможны алгоритмы получения частного в прямом ш\и обратном коде. Это определяется правилами анализа остатка.
[[ример 6.1. Разделить числа А = -UJOOI \ и В = -0,11001 на двоичном сумматоре об' рапиио коли с получением частого в прямом коде-
Ре m с и и е }[пя реализации примера воспользуемся с1рукгурпоИ схемой рис, 6.1, а и меюдом деления с воссюповлеиием остатка,
11релстапляемчиславобрагнычкодах l^l^ls =11,01100; [В]'^ =11,00110; [В]'^ =00.11001.
из
б Иылолнеипе |
onepatiiiii |
деления чисел на двоичных |
сулшаторал |
|||||
Определим знак частного: Sg,• ^ Sg^ ®Sg/f |
= 1 Ф 1 = 0 . |
|
|
|
||||
При этом руководствуемся следующими правилами: |
|
|
|
|
||||
Вариант |
I |
|
2 |
|
|
|
|
|
Знак лелимого J-. |
+ |
|
+ |
|
|
|
|
|
Знак лелтеля/i |
+ |
|
|
|
|
|
|
|
Чго делать в С\М. |
••«,-1 + й |
2'" ' |
1,^,+11-2'"'" |
А,_, |
+ |
В2'<''" |
•1, , + в 2 I " " |
|
3FFaK ociaiKa А^.. |
А, >и А, <0 |
А^>0 |
Л, <0 |
Л, > О А, < О |
.4, > О . I, < О |
|||
Цифра часттюго |
с, = I с, |
= О |
с, = I с, = О |
с |
= О с = I |
с, = О с, = I |
||
Послелова1ельность действий для получения цифр частно! о показана в 1аблиис 6 I Oimew (Г ] = 0.11000.
Т а б л и п а 6.1
Суммаюр |
Регистр с |
11римечание |
|
|
|
||
1101100 |
00000 |
И, 11. СМ := {А\;^,. РгЛ := {В\"^. l>iC := 0: |
|
11111001 |
оооо- |
|CM):]ivr]: |
|
0011001 |
|
1СМ]:=1СМ] + |ВЙ ; |
|
1110010 |
00001 |
Л, <0-,С| =U |
|
1100101 |
0 0 0 1 - |
lCM);lKc|. |
|
00110111 |
|
|CM):=|CM| + |«0,; |
|
1111110 |
0001 1 |
/1, < 0: с, = 1: |
|
1111101 |
0 0 1 1 - |
lCM);irVr): |
|
0011001 |
|
|CMl.= lCM) + lBft ; |
|
|
|
||
0010111 |
00110 |
/f, > 0: Cj = 0; |
|
ИЙОИО |
|
Восстановление остатка |
|
11III01 |
|
|СМ]:=1СМ]+|й1:5; |
|
|
|
||
11 n u l l |
01 l o |
1СМ];|РГС|: |
|
0011001 |
|
|СМ1:=1СМ1 + | й а ; |
|
0010101 |
l l 000 |
А, > 0: с, = 0: |
|
поопо |
|
Восстановление осгагка |
|
|
|СМ]:=1СМ] + 1ВЙ; |
||
1111011 |
|
||
|
|
||
III01II |
1 100- |
1СМ];1РГГ]: |
|
|
|
||
ШЩ} |
|
|СМ]:=|СМ] + № ; |
|
11000 |
А, > 0: <-•, = 0; |
||
0010001 |
|||
|
|
Ко[!ен операции
6 2 Деление чисел, представленных в форме с фиксированной запятой
По своему характеру операция деления относится к операциям, дающим не всегда точный результат, поэтому признаком окончания опе рации деления может быть достижение заданной точности (по сумме сдвиговых сигналов). Если в процессе деления получили остаток Д = 0 , то операция останавливается и в оставшиеся разряды частного записы вается нуль. Обычно формальным признаком конца операции деления является количество сдвигов: при достижении числа сдвигов, равного количеству разрядов в частном, вырабатывается сигнал окончания опе рации деления.
Требуется несколько интерпретировать правила определения цифры час г ною . В примере 6.1 проводится сравнение знаков делимого и остатка иа каждом шаге: при совпадении знаков в частном записывается единица, при иесовпадеиии — нуль. Можно сравнивать знаки делителя и остатка, тогда единица в 1)черелиой разряд частного записывается при иесовггадении знаков, а нуль — при совпадении.
Для получения частного, представленHOI о в обратном коде, все дейст вия должны осуществляться по следующим правилам:
Вариант |
|
|
1 |
|
|
|
2 |
|
|
3 |
|
|
|
4 |
|
Знак ;!t'jmMm(i |
|
|
|
|
|
|
+ |
|
|
- |
|
|
|
- |
|
3ii;iK jicjiHFCJiH |
|
|
|
|
|
|
- |
|
|
4 |
|
|
|
- |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Чк) ;Eeii;irb » CM |
..(, |
, + |
Br^'-» |
А,_, + |
В^2-"-» |
А,_, +В |
2 |
"^'> |
/(,_, + S ' 2 - < ' - " |
||||||
ЗнакociaiKa .(, |
Л, > и |
А,<0 |
Л, |
>0 |
А,<0 |
/(, |
> 0 |
/f, |
< 0 |
/f, |
> 0 |
/1, < 0 |
|||
Un(|)pa ч а с т о ю i |
с, |
=1 |
с, |
= 0 |
?, |
= 0 |
с, |
=1 |
г, = 1 |
?, |
= 0 |
с, |
= 0 |
с, =1 |
|
|
с, |
=1 |
с, |
= 0 |
с, |
=1 |
с, |
= 0 |
с, |
= 0 |
|
|
с, |
= 0 |
г, =1 |
|
|
|
вое, ост. |
|
|
вое, ост. вое. ост. |
|
|
вое. ост. |
|
|||||
Пример fi.2. 1';илсл111ь числа |
.^==-0,10101 |
и Д = 0,11ШО |
на двоичном сумматоре обрат- |
||||||||||||
[I01 о кода с iinjiyHciHicM частного в обратном коде. |
|
|
|
|
|
|
|
|
|||||||
1'е 111 с и и с |
CipyKiypnaH схема и метол деления те же, что в примере 6.1. |
|
|
||||||||||||
1 !релс1?.!!им числа п обратных кодах: |
|
|
|
|
|
|
|
|
|
|
|||||
|
| . 4 | ^ |
= 11.01010; 1Д]^ = 11,00011; [Щ"^ |
= 00.11100 . |
|
|
|
|||||||||
Знак рс(ул1.!а[а Л^,. ^^ |фО = i .
I iocjiwioiiaiejibiiocib дейсший при решении задачи показана в таблице 6.2
Оптет {С^^^, ^ П . О О Ш .
Сумматор
И 0 1 0 Ш I010I0I 0011100 II10001 1100011 0011100 I I I M I I
i i i i m
+
0011100
0011100
IIOOOII
m i n i
i i i i i i i OUIIIOO 0011100 IIOOOII
I I I I I I I
\ n m i
+
0011100
0011100
6Выполнение операций деления чисел на двоичных сумматорах
Га б л и 11 а 6.2
Регистр С |
|
Примечание |
|
|
|
««)00 |
И. r i , C M : = l / I U ; P f e . = [Bu.i>rt-.= «. |
|
0000- |
|см]; |Pi<1; |
|
|
ICM]:=ICM] + IBC: |
|
00000 |
/fi < 0; c, = 0; |
|
oooo- |
1СМ1;1РГС]; |
|
|
||
|
ICM]:=1CM] + I B U ; |
|
00000 |
A,<0:cj=0: |
( . - l j = 0 ) ; |
0000- |
lCM];liwi; |
|
|
|CM1:=ICM] + |«C; |
|
00001 |
/1, > 0 ; c , |
= 0 ; |
|
Восстановление остатка |
|
0 0 0 1 - [СКТЦКТ]; |
||
|
[CM1:=|CM] + IBC; |
|
0001 1 |
A, >0.c,= |
1; |
|
Восстанонлеиие остатка |
|
0 0 1 1 - |
fcMl.lpSl; |
|
|
| C M ] : = I C M ] + | B ] ^ ; |
|
001II |
.4, > 0; c, |
= 1; |
Хслв = 5 . Коней
Затраты времени на выполнение операции деления можно определить по формуле
'де, ="['« . +(! + / ' ) ' „ ] . (б'») где п — длина разрядной сетки; 1^^^ — время выполнения сдвига на один разряд; /„ — время выполнения операции сложения; р ~ вероятность по
явления нулей в разрядах частного.
На двоичных сумматорах дополнительного кода можно получить частное как в прямом, так и в дополнительном кодах. Знак частного образуется отдель но от цифровой части путем сложения знаковых разрядов но модулю 2.
146
6 2 Деление чисел, представленных в форме с фиксированной запятой
Для получения частного в прямом коде правила остаются теми же, что и для сумматоров обратного кода (см, пример 6.!).
Пример 6.3. Разделить число /^ = 0,1000! иа Д= - ПОП на двоичном сумматоре до полнительного кода, qacTiFoe получить в тфямом коде. Используется структурная схема, представленная на рис. 6.1, о-
Р е ш е н и е , Поспедовательность действий при решении примера показана в таблице 6.3, [А]^ = 00,10001; [Д]" = 11.00101; 1Д]" =00,11011. Используем алгоритм без восстановле
ния остатка. Знак частно! о; Sgf- = О Ф1 = 1 .
Т а б л и ц а 63
CyMMaiop |
Регистр с |
0010001 |
00000 |
0100010 |
0000- |
1100101 |
|
00()() 111 |
00001 |
0001110 |
0 0 0 1 - |
1100101 |
|
I I 1(1011 |
00010 |
1100110 |
0010- |
OOIHIJI |
|
«OOOOOI |
00101 |
0000010 |
0 1 0 1 - |
1100101 |
|
11001 и |
01010 |
100(110 |
1010- |
0011011 |
|
I I 0 I 0 0 I |
10100 |
И . П . С М : = И 1 ; ; Р г С [СМ]; |РгС];
l C M ] : = l C M ] + [iS|;; /<1 > 0; с, = 1;
(сМ];|РгС1;
I C M ] ; = | C M ] + | B | ; ;
А^ < 0; с, = 0;
[сЩ1РгП;
I C M ] ; = [ C M ] + 1B|;;
А, > 0; с, = 1:
|СМ];1РгГ); [СМ]-.= 1СМ] + ( в ] ; ;
А, < 0; С4 = 0;
( С М Ц Р г С ) ;
|СМ];=1СМ] + 1в];;
/f, < 0; Cs = 0;
£ „ , = 5, Конец
Примечание
= 0 ; P r B : = [ B j ; :
Ответ: [С]„^ =1.10100.
Ллгори! м выполнения операции деления должен работать так, что если делитель равен О или делимое равно максимальному отрицательному чис лу, то вырабатывается сигнал переполнения.
147
6 Выполнение onepaifuu деления чисел на Овоинны.х сумматорах
Сигна/1 нереполнення должен вырабатываться и в тех случаях, когда делимое больше делителя по абсолютной величине для чисел с фиксиро ванной занятой.
6.3.Особенности деления чисел, представленных в форме
снлавающей занятой
^Для получения частного отделения двух чисел, нредсьтвлениых в форме с плавающей запятой, необходимо определить m^ - т , //;г^( . /;, - р ^ - р^ .
Так как мантиссы делимого и делителя —- нормализованные числа, при делении возможны случаи, когда \т^\ > ^тц\; [т ,| < \т„\.
Вели MaiiTHCca делимого больше или равна мантиссе делн!еля. ю в конце операции деления потребуется нормализация частного (пар>и1енис правой границы). Таким образом, а/поритм деления начинайся с операции вычитания делителя из делимого и записи единицы в целую час!ь часиюго. Все остальные действия над мантиссами аналогичны действиям над числа ми, представленными в форме с фиксированной запятой.
Если мантисса делимого меньше мантиссы делителя, то |юсле операции вычитания па первом uiaie получи^гся отрицательный остаток, что означает нуль в целой части мантиссь! частного и продолжение алгоритма деления гго рассмотренным выше правилам для чисел, представленных в форме с фикси рованной запятой. Таким образом, частное всегда получается в прямом коде, а действия над мантиссами осуществляются на ДСОК njin ДСДК.
Так как при операции деления порядки чисел вычитаются (изображения складываются), возможно переполнение разрядной сетки в сумматоре г!орядков. При иере1юлнении в сторону отрицательных величин 1горядка мантисса результата превращается в машинный нуль, а порядку присваивается наи большее отрицательное значение. Если делитель равен нулю, то таюке выра батываются сигналь! ц> = \ и останов машины. Эти nacTHbie случаи преду смотрены iipH реализации алгоритмов в ЕС ЭВМ, где используется а?1Горигм деления без восстановления остатков. При этом мантисса делимого имеет длину в два раза больше, чем делитель, что иллюстрируется примером 6.4.
Пример 6,4. Рэ)лелить число /1 = 0,100011 И • 2' на Д = 0.1 111 2^
PeuFeuMeРассматривается случай, котда |"'^|<1"1д|- Прежде неси» заммиьшакися машинные изображения мантиссы делимого |wi^)" = 00.100011 11; мантиссы лслигсля l^'wl" -00,1111 и [Ш/,]'^ = 11,0001.
6.4 Ускорение операции деления
Все действия выполняются на сумматоре дополнительного кода в послеловательности, >к<ваи!!0й в 1аблице6 4
CyMMaloji |
Pefис1р f |
00,10001111 |
0000 |
01,00011110 |
000- |
"^11,0001 |
|
00,00101110 |
0001 |
00,01011100 |
001 |
* 11,0001 |
|
11,01101100 |
0010 |
10,1101 1000 |
010,- |
* 00,1111 |
|
11,11001000 |
0100 |
11,10010000 |
100 |
*00,11 11 00,1000000(1 1001
Т а б л и ц а 64
Примечание
И. П. СМ := [mj ]"; РгС := 0; РгВ := |т„i:; слвиг суммагоров и регистров
|CM|:=|CM| + lm];;
с, = 1.
t;lBHFсуммаюров и регистров |СМ|=|СМ1 + |Я„];;
Ci=0,
елниг суммаюров и регистров |CMl:=|CM|+[m,i;;
Cj = 0;
слвиг суммагоров и регистров |СМ|:=|СМ| + | т , ] ; ,
с, = 1; Koircii
O.'innupcMciiin) н1.Г!!|сляе]ся порядок частного |
с1гедугог1гим обратом: |
Рс-Р^-Рн- |
= 0,011 0,010-0,001 гтоггре.чеяясгся зггак частою |
.Vg,. = О® 0=^ О- |
|
Оттт С -0,1001 2' |
|
|
6.4. Ускорение операции деления
Идея метода ускорения операции деления заключается в том, что в случае обра^тванпя досгаючпо мшюго или достаточно большого по абсолютной веjrHMiine остагка очередные цифры частного будут группой одинаковых цифр либо nyjreH. jni6o единиц, гюэтому продолжение процесса деления обычным
способом иигитпе, так как эту группу цифр можно записать в частное сразу, Рассмогрим примеры деления десятичных и двоичных чисел:
2281825 |
2275 |
2) 1010001 |
lOOi |
"2275 |
1003 |
1001 |
1001 |
0()()6825 |
|
0001001 |
|
6825 |
|
1001 |
|
0000 |
|
0000 |
|
6 Выполнение операций деления чисел на двоичных сулглгатора^^
Здесь на первом шаге получился малый по величине положительный остаток, который содержит нули в трех старших разрядах. В частном после первой цифры записаны нули в два следующих разряда. Можно утвержда1ь, что при малом положительном остатке в частное можно сразу записагь к - 1 нулей в соответствующие разряды, остаток сдвинуть на к разря дов влево, BbiMecTb из него делитель и далее продолжить операцию деления.
Если в результате вычитания на каком-то шаге получается большой положительный остаток, в котором к старших разрядов содержат единицы (для двоичных чисел), то гю меньшей мере в (к~\)-е разряды частного можно записать единицу;
1000000000... 110001
10001 ГТТТТО
omjo
к
10001
опою
10001
_ 0 1 0 0 ( 0 10001
000001...
Таким образом, в данном случае процесс деления должен осугцесгвлягься комбинирова1Н1ым сгюсобом, с анализом (юследовательносги нулей (если остаток положительный) или последовательности единиц (если оста ток отрицательный) в старших разрядах остатка. При обнаружении такой последовательности длиной к сразу можно записать в (А: - 1 )-е разряды ча стного соответственно нули или единицы. После этого провести сдвиг" на (^ - I ) разряд и продолжить операцию деления.
В других случаях операция выполняется по обычному алгоритму. Рассмотренный метод ускорения операции деления может дать эффею
только тогда, когда встречаются последовательности нулей или единиц в остатках.
Для ускорения операции деления можно воспользоваться также мето дом одновременного определения двух цифр частного, который являе!ся развитием изложенной выше идеи. Этот метод реализован в некоюрых ЭВМ третьего поколения.
I\ycib А - делимое; В — делте;гь; Д_| — остаток па ( / - I )-м шаге де
ления.
Для остатка справедливо О > |Д_|| < В .
150