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

Микропроцессор КР580 не содержит команд деления чисел, поэтому для выполнения этой операции необходимы программы. Любой программный метод деления сводится к последовательному нахождению цифр частного, начиная с его старшей цифры, путем вычитания делителя из делимого или остатка и анализа получаемой разности. Двоичное деление проще десятичного, поскольку выбор очередной цифры частного производится всего из двух цифр: О и 1, причем цифра 1 выбирается при неотрицательной разности (делимое по модулю больше или равно делителю), а цифра О - при отрицательной разности (делимое по модулю меньше делителя) [5,32, 33, 61]. Процедура обычного (неускоренного) деления носит последовательный характер: очередная цифра частного и новый остаток не могут быть вычислены прежде, чем будет получен и исследован предыдущий остаток.

Поскольку частное в отличие от произведения можно получать только со старших его цифр, имеются две вычислительные схемы деления (рис. 1.8). Схема 1 (рис. 1.8, а) аналогична схеме 3 умножения (см. рис 1.5, в), а схема 2 (рис. 1.8, б) -схеме 4 умножения (см. рис. 1.5, г). На схемах рис. 1.8 обозначены: ДМ - делимое; ДЛ - делитель; ЧСТ - частное; ОСТ - остаток (в скобках указаны разрядности данных). Цифры частного формируются по значению признака переноса CY, устанавливаемого в операциях вычитания делителя из делимого или остатка, и сдвигаются влево. При этом в схеме 1 для получения нового остатка предыдущий остаток сдвигается влево при неподвижном делителе, а в схеме 2, наоборот, при неподвижном остатке сдвигается вправо делитель. Схема 1 проще и не требует команд сдвига вправо многобайтных данных (в микропроцессоре КР580 такие команды отсутствуют). Поэтому рассматриваемые ниже программы деления все выполнены по схеме 1.

Есть два способа получения цифр частного и остатка: 1) деление с восстановлением остатка; 2) деление без вос-

-Сдбиг

ЦСТ(п)

ДЛ(п)

-СЗбиг

-Сдбиг

Сдвиг

ДЛ(2п)

ДМ(2п),0СТ(п)

Рис. 1. 8. Вычислительные схемы операции деления

становления остатка. Рассмотрим способ деления с восстановлением остатка для класса целых беззнаковых двоичных чисел (он применим и для дробных беззнаковых чисел). Пусть А, Y, Z, Q - целые беззнаковые {X, Y, Q - м-разрядные числа, а Z-2п-разрядные) числа, такие, что X • Y -\- Q = Z, где Q <Х. Тогда справедливы выражения:

Z-.YX; Z:Y = {X, Q),

где X - неполное частное; Q - остаток. Если Z < У, то - = 0, Q = Z; если Z = У, то Х=\, Q = 0; если Z = = У, то Q = 0.

Обозначим через Q,- разность между остатком Q, i и делителем, где / е {1, 2,.... и}; Qo = Z, а через - цифру частного X, причем j = n - i, /е{0, 1, п - 1}. Тогда процедуру деления с восстановлением остатка можно записать в виде рекуррентной формулы

п . (•2Q, ,-У; х„ , = 1 при 2Q, i-y>0;.,

Эта процедура состоит из п циклов деления, причем в каждом /-М цикле осуществляется сдвиг влево на один двоичный разряд остатка Q/-i, полученного во время выполнения предыдущего (/-1)-го цикла, и вычисление разности между удвоенным остатком и делителем: 2Q, , - у. Если разность положительна, то в очередной {п - /)-й разряд частного записывается цифра х„-,= 1,

а разность становится новым остатком Q,-. Если же разность отрицательна, то в рязряд частного записывается Xn-i = 0, а остаток 2Qi i восстанавливается (либо путем сложения 2Qii - Y-\-Y, либо извлечением из области его сохранения) и интерпретируется как новый остаток Qi. После выполнения м-го цикла деления сформированы все п старшие цифры частного и получен остаток Q = Q„ < < X. Этот остаток можно использовать для повторного деления с целью вычисления дробной части частного и повышения тем самым точности его вычисления. Многократно повторяя последнюю операцию, можно вычислить частное с любой наперед заданной точностью.

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

0 /2Qi-i-y, если Q,-,>0; •~l2Q, , Н- Y, если Q, , <0;

1, если Q,>0; если Q/<;0.

В этой процедуре при получении отрицательной разности Q( i = 2Q, 2-Y последняя не восстанавливается, как в формуле (1.25): Q, i=2Qi 2, а сдвигается в сле-дуюшем, /-М цикле влево, и к ней прибавляется делитель: Qi = 2Qi ,-\-Y.

Преобразование = 2Q,- , Г = 2(2Q, 2 - К) Ч-+ F = 2(2Q, 2-У показывает эквивалентность обоих способов. При способе с восстановлением остатка в каждом цикле производятся одна либо две операции: вычитание или вычитание и сложение (при восстановлении), а при втором способе - только одна операция: вычитание или сложение. Поэтому второй способ имеет потенциально большее быстродействие, но это его преимущество проявляется лишь при аппаратных реализациях деления. Программная реализация второго способа сложнее, что связано с необходимостью хранения знака остатка до начала следующего цикла деления с целью определения типа выполняемой операции (сложение или вычитание делителя) и коррекции конечного остатка Q„ в случае, если Q„ i<;0 (необходимо вычесть делитель). Вследствие этого деление без восстановления остатка редко используется в программах (в иллюстративных целях далее будет приведена программа деления Д16А, выполняемого по этому способу).