Файл: 351-400.pdf

Целочисленное деление  3 7 1

тель с сумматором одинарной длины. Неподвижный делитель

 D

 хранится в регис-

тре одинарной длины, а делимое

 Z,

 сдвигаемое относительно

 D,

 находится в двух

таких же регистрах. Образующиеся цифры частного

 Q

 заносятся в освобождаю-

щиеся при сдвиге Z разряды одного из регистров Z

Ниже на. примере чисел без знака рассматриваются два основных алгоритма

целочисленного деления.

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

Наиболее очевидный алгоритм носит название алгоритма

 деления с неподвижным

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

 В учебнике он представлен в силу того, что

очень похож на общепринятый способ деления столбиком. Данный алгоритм мо-
жет быть описан следующим образом:

1. Исходное значение частичного остатка полагается равным старшим разрядам

делимого.

2. Частичный остаток удваивается путем сдвига на один разряд влево. При этом

в освобождающийся при сдвиге младший разряд 40 заносится очередная цифра

частного.

3. Из сдвинутого Ч0 вычитается делитель и анализируется знак результата вы-

читания.

4. Очередная цифра модуля частного равна единице, когда результат вычитания

положителен, и нулю, если отрицателен. В последнем случае значение остатка

восстанавливается до того значения, которое было до вычитания.

5. Пункты 2-4 последовательно выполняются для получения всех цифр модуля

частного.

На рис. 7,48 показан процесс деления с восстановлением остатка, здесь число 41

делится на 8.

Деление без восстановления остатка

Недостаток затронутого алгоритма заключается в необходимости выполнения на

отдельных шагах дополнительных операций сложения для восстановления час-
тичного остатка. Это увеличивает время выполнения деления, которое в этом слу-

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

еле-

ния с неподвижным делителем без восстановления остатка.

 Приведем описание

этого алгоритма.

1, Исходное значение частичного остатка полагается равным старшим разрядам

делимого.

2, Частичный остаток удваивается путем сдвига на один разряд влево. При этом в

освобождающийся при сдвиге младший разрядЧ0 заносится очередная цифра

частного.

3, Из сдвинутого частичного остатка вычитается делитель, если остаток положи-

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

3 7 2 Глава 7. Операционные устройства вычислительных машин

Рис. 7,48. Пример деления с восстановлением остатка

4. Очередная цифра модуля частного равна единице, когда результат вычитания

положителен, и нулю, если он отрицателен.

5. Пункты 2-4 последовательно выполняются для получения всех цифр модуля

частного.

Как видим, пункты 1,2,5 полностью совпадают с соответствующими пунктами

предыдущего алгоритма деления.

Процесс деления без восстановления остатка для ранее рассмотренного приме-

ра демонстрируется на рис. 7.49.

Деление чисел со знаком

Как и в случае умножения, деление чисел со знаком может быть выполнено путем

перехода к абсолютным значениям делимого и делителя, с последующим присвое-

нием частному знака «плюс» при совпадающих знаках делимого и делителя либо
«минус» — в противном случае.

Деление чисел, представленных в дополнительном коде, можно осуществлять

не переходя к модулям. Рассмотрим необходимые для этого изменения в алгорит-
ме без восстановления остатка.

Так как делимое и делитель не обязательно имеют одинаковые знаки, то дей-

ствия с частичным остатком (прибавление или вычитание

 D)

 зависят от знаков

остатка и делителя и определяются содержимым табл. 7,5:

Целочисленное деление

  3 7 3

Рис.

 7.49. Пример деления без восстановления остатка

Таблица 7.5.

 Операция, выполняемая в очередной итерации деления

И Если знак остатка совпадает со знаком делителя, то очередная цифра частно-

го — 1, иначе — 0.

- Ecли Z>0

 и

 D<

 0, частное необходимо увеличить на 1.

-

 Если Z < 0 и

 D >

 0, то при ненулевом остатке от деления частное нужно увели-

чить на единицу.

- Если Z < 0 и

 D <

 0, то при нулевом остатке от деления частное нужно увели-

чить на единицу.

Остаток всегда приводится к положительному числу, то есть если по заверше-

нии деления он отрицателен, к нему следует прибавить модуль делителя.

Устройство деления

Рассмотренный алгоритм деления без восстановления остатка может быть реали-

зован с помощью устройства, схема которого приведена на рис. 7.50.

Процедура начинается с занесения делимого в 2n-разрядный регистр делимого

(РДМ) и делителя в n-разрядный регистр делителя (РДТ). В счетчик цикла (СЧЦ —
на схеме не показан), служащий для подсчета количества полученных цифр част-
ного, помещается исходное значение, равное

 п.

3 7 4 Глава 7. Операционные устройства вычислительных машин

Рис. 7.50. Схема деления по алгоритму без восстановления остатка

На каждом шаге содержимое регистра делимого (РДМ) и регистра частного

(РЧ) сдвигается на один разряд влево. В зависимости от сочетания знаков частичного

остатка и делителя определяется значение очередной цифры частного и требуемое
действие: вычитание или прибавление делителя. Вычитание делителя производит-

ся посредством прибавления дополнительного кода делителя. Преобразование
в дополнительный код осуществляется за счет передачи делителя на вход сумма-
тора обратным (инверсным) кодом с последующим добавлением единицы к млад--
шему разряду сумматора.

Описанная процедура повторяется до исчерпания всех цифр делимого, о чем

свидетельствует нулевое содержимое счетчика циклов (содержимое СЧЦ умень-

шается на единицу после каждой итерации). По окончании операции деления ча-

стное располагается в регистре частного, а в регистре делимого будет остаток от
деления.

На заключительном этапе, если это необходимо, производится корректировка

полученного результата, как это предусматривает алгоритм деления чисел со знаком.

На практике для накопления и хранения частного вместо отдельного регистра

используют освобождающиеся в процессе сдвигов младшие разряды регистра де-

лимого.

Комбинированное устройство умножения/деления

Сходство процедур умножения и деления находит свое отражение в близости струк-

тур соответствующих устройств (рис. 7.51).

Из подобия процедур вытекает очевидная идея реализации обеих операций

с помощью единых технических средств, в виде комбинированного устройства ум-
ножения-деления (рис. 7.52).

Целочисленное деление  3 7 5

Рис. 7.51. Структура устройств умножения и деления

Рис. 7.52. Комбинированное устройство умножения/деления

Видим, что для хранения операндов и результатов используются общие регис-

тры. Усложнение связано, главным образом, с устройством управления, функции

которого существенно расширяются, что, естественно, требует определенного уве-

личения аппаратурных затрат.