Выполнение операций умножения и деления в ЭВМ (стр. 3 из 4)

|А|<|В|

где А - делимое, В - делитель. Кроме того: В¹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

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 R_i-1 х 2 = 4 R_i-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