Алгоритм деления с восстановлением остатков

В основе алгоритма деления лежит логика ручного счета. При выполнении деления на бумаге вычислитель быстро анализирует, что больше – делитель или делимое (очередной остаток), и когда делимое меньше делителя, в очередной разряд частного заносится «0» и выполняется сдвиг.

В ЦВМ такой анализ можно сделать посредством вычитания делителя из делимого, и при получении отрицательного остатка в очередной разряд частного занести «0», а отрицательный остаток восстановить до предшествующего значения, прибавив к нему делитель. Только после этого можно выполнить сдвиги. Если же остаток положителен, в частное заносится «1» и выполняются соответствующие способу деления сдвиги.

Это позволяет сформулировать алгоритм деления с восстановлением остатков для дробных чисел с фиксированной запятой (ФЗ):

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

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

3. Проанализировать знак остатка после первого вычитания:

- если остаток положительный, произошло ПРС, операцию прекратить до смены масштабов операндов;

- если остаток отрицательный, в частное занести «0» (этот разряд по окончании деления станет знаковым разрядом частного) и восстановить остаток, прибавив к нему делитель.

4. Выполнить сдвиги: частного на один разряд влево и остатка на один разряд влево (I способ) или делителя на один разряд вправо (II способ).

5. В цикле формирования цифр частного: вычесть из остатка делитель, прибавив его в обратном или дополнительном кодах.

6. Проанализировать знак полученного остатка:

- если остаток положителен, в частное занести «1»;

- если остаток отрицателен, в частное занести «0».

7. Восстановить отрицательный остаток, сложив его с делителем.

8. Выполнить сдвиги, как указано в пункте 4 алгоритма.

9. Завершить цикл формированием (n+1)–го остатка для округления. Последний сдвиг частного не выполнять.

10. Выполнить округление результата и присвоить частному знак, полученный в пункте 1 алгоритма.

В соответствии с вышеизложенным алгоритмом можно представить формулой правила формирования очередного остатка для I и II способов деления.

Пусть D – делитель, D_i – остаток на i-м шаге алгоритма.

В I способе деления выполняется сдвиг влево на один разряд (удвоение) остатка (восстановленного - (D_i+D) или невосстановленного D_i):

(1)

Во II способе деления выполняется сдвиг вправо на один разряд делителя, то есть уменьшение делителя вдвое:

(2)

Анализ приведенного алгоритма позволяет отметить следующие недостатки:

-процесс деления ацикличен, так как операция восстановления остатка появляется нерегулярно, что приводит к усложнению устройства управления делением;

-быстродействие алгоритма невелико, так как примерно в половине шагов цикла выполняется дополнительная операция восстановления остатка.

Пример 8. Разделитьчисла А=27₍₁₀₎ и В=-30₍₁₀₎, представив числа в форме с ФЗ в ПК (М_А,В=2⁵). Пусть А=0,11011 –делимое; В=1,11110-делитель.

1. Знак частного: 0Å1=1.

2. Деление модулей операндов выполним I способом с использованием ДК при вычитании.

Частное	Делимое (остатки)	Пояснения
0,00000	0,11011 1,00010	Вычитание
0,00000	1,11101 0,11110	Первый остаток Восстановление
	0,11011 1,10110 1,00010	Сдвиги Вычитание
0,00001	0,11000 1,10000 1,000010	Второй остаток Сдвиги Вычитание
0,00011	0,10010 1,00100 1,00010	Третий остаток Сдвиги Вычитание
0,00111	0,00110 0,01100 1,00010	Четвертый остаток Сдвиги Вычитание
0,01110	1,01110 0,11110	Пятый остаток Восстановление
	0,01100 0,11000 1,00010	Сдвиги Вычитание
0,11100	1,11010 0,11110	Шестой остаток Восстановление
	0,11000 1,10000 1,00010	Сдвиг остатка Вычитание
0,11100(1)	0,100010	Седьмой остаток для округления

1. Так как седьмой остаток положительный, то в отбрасываемый разряд частного должна быть занесена «1», следовательно, для округления результата к младшему разряду частного нужно прибавить единицу

Тогда модуль частного после округления:

А/В=0,11101.

2. Частное со знаком в прямом коде:(А/В)_ПК= 1,11101.

Проверка: А/В= -0,11101₍₂₎=-0,90625_(10).. Точный результат –(27/30)=-0,9.

Пример 9. Разделить А=-25₍₁₀₎ на В=9₍₁₀₎, представив операнды в форме с ФЗ в прямом коде (М_А,В=2⁵). А=1,11001 – делимое; В=0,01001 – делитель.

1. Знак частного: 1Å0=1.

2. Деление модулей операндов выполним II способом с использованием ДК при вычитании.

Частное	Делитель	Делимое (остатки)	Пояснения
	0,0100100000	0,1100100000 1,1011100000
		10,1000000000	ПРС!
Увеличим масштаб делимого до М=27
	0,0100100000	0,00110 01000 1,10111 00000	Вычитание
0,00000		1,11101 01000 0,01001 00000	Первый остаток Восстановление
	0,0010010000	10,00110 01000 0,00110 01000 1,11011 10000	Сдвиги Вычитание
0,00001	0,0001001000	10,00001 11000 0,00001 11000 1,11101 11000	Второй остаток Сдвиги Вычитание
0,00010		1,11111 10000 0,00010 01000	Третий остаток Восстановление
	0,0000100100	10,00001 11000 0,00001 11000 1,11110 11100	Сдвиги Вычитание
0,00101	0,0000010010	10,00000 10100 0,00000 10100 1,11111 01110	Четв-ый остаток Сдвиги Вычитание
0,01011	0,0000001001	10,00000 00010 0,00000 00010 1,11111 10111	Пятый остаток Сдвиги Вычитание
0,10110		1,11111 11001 0,00000 01001	Шестой остаток Восстановление
	0,0000000100	0,00000 00010 0,00000 00010 1,11111 11100	Сдвиги Вычитание
0,10110(0)		1,11111 11110	Седьмой остаток

3. Округленное частное в прямом коде:

А/В=1,10110

Проверка: М=М_А/М_В=2⁷/2⁵=2². А/В= -10,110₍₂₎=-2,75₍₁₀₎. Точный результат –(25/9)=-2,78; относительная погрешность =1,08%.

Поиск по сайту: