П3.5. Деление программным способом

Деление — процесс обратный умножению. Если при умножении выполняется многократное суммирование, то при делении — многократное вычитание. Деление обычно сводится к выполнению последовательности вычитаний делителя Y сначала из делимого X, а затем из образующихся в процессе предыдущих вычитаний остатка и сдвига частичных остатков. Наиболее распространенными схемами деления являются схема деления с неподвижным делимым и сдвигаемым вправо делителем (рис. П3.9) и схема деления с неподвижным делителем и сдвигаемым влево делимым (рис. П3.10).

Частное Z

X -Y

Инверсное значение

знака остатка

Исходное

значение делителя

Рис. П3.9. Схема деления с неподвижным делимым и сдвигаемым вправо делителем

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

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

Частное Z

X -Y

Инверсное значение

знака остатка

Делитель Y YY

Рис. П3.10. Схема деления с неподвижным делителем и сдвигаемым влево делимым

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

Реализация алгоритма деления предполагает, что исходные значения делителя и делимого нормализованы, т. е. удовлетворяют неравенству | X| ≤ | Y|. Если условие не выполняется, то предварительно (перед делением) необходимо выполнить выравнивание (масштабирование) делителя.

Процедура деления начинается с формирования модулей делимого и делителя и последующего определения и запоминания знака частного. Затем, если необходимо, осуществляется масштабирование делителя, и после этого выполняется собственно деление. Деление реализуется методом многократного (циклического) вычитания делителя Y сначала из делимого X, а затем из образующихся в процессе деления частичных остатков Х_к и сдвига влево частичных остатков. В микропроцессорах вычитание реализуется путем суммирования делимого с дополнительным кодом отрицательного делителя. Остаток Х_к может быть ≥ 0 или < 0. Если Х_к < 0, то для формирования следующего остатка необходимо восстановить прежний остаток (путем прибавления к нему делителя в прямом коде) и перед вычитанием делителя сдвинуть его на один разряд влево. Очередная цифра частного, определяемая как инверсное значение знака частичного остатка, заносится в младший разряд частного. Число циклов вычитания делителя из частичных остатков и сдвигов делимого и частного зависит от требуемой точности выполнения операции деления (требуемой разрядности частного). Рассмотренный способ деления носит название деление с восстановлением остатка. Недостатком этого способа деления при аппаратной реализации является необходимость использования дополнительного такта на восстановление остатка при Х_к < 0.

Более быстродействующим при аппаратной реализации является способ деления без восстановления остатка, не требующий восстановления предыдущего остатка после получения отрицательного остатка. При этом способе деления при выявлении отрицательного знака остатка Х_к сразу формируется следующий остаток Х_к+1. Для этого осуществляется сдвиг остатка Х_к влево и его суммирование с делителем. При аппаратной реализации деление без восстановления остатка в зависимости от знака частичного остатка реализуется двумя различными циклами:

- если очередной частичный остаток Х_к > 0, то в следующем цикле выполняется вычитание делителя из сдвинутого частичного остатка Х_к (путем суммирования делимого с дополнительным кодом отрицательного делителя);

- если очередной частичный остаток Х_к < 0, то в следующем цикле выполняется суммирование сдвинутого частичного остатка Х_к и прямого кода делителя.

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

Х_{к +1} = 2*(Х_к + Y) – Y = 2*[(Х_{к -1} – Y) + Y ] – Y = 2 Х_{к -1} – Y полностью совпадает с частичным остатком при делении без восстановления остатка

Х_{к +1} = 2*(Х_{к -1} – Y) + Y = 2 Х_{к -1} – Y.

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

В общем случае алгоритм деления целых чисел можно описать следующей последовательностью действий:

- определяется и запоминается знак частного.

- формируются модули (прямые коды) делимого Х и делителя Y. Делитель должен быть ненулевым.

- выполняется процедура нормализации (выравнивания) делителя. В зависи- мости от значений делителя и делимого нормализованный делитель должен удовлетворять одному из условий: |X| < |Y| или |Y| ≤ |X| ≤ 2|Y|.

Выравнивание реализуется путем сравнения Х и Y и последующих сдвигов делителя. Если в результате сравнения выясняется, что делимое Х больше делителя Y (флаг переноса С=1), осуществляется сдвиг делителя влево, что соответствует его умножению на 2. Выравнивание продолжается до выполнения неравенства |X|<|Y|. Число сдвигов (шагов выравнивания) фиксируется. Оно определяет число разрядов целой части частного.

Если в процессе выравнивания старший (значащий) разряд делителя при очередном сдвиге вправо занимает знаковый разряд, это соответствует соотношению |Y| ≤ |X| ≤ 2|Y|. При таких значениях |X| и |Y| для правильного деления дополнительно необходимо сдвинуть делитель вправо.

- выполняется собственно деление делимого |X| на нормализованный делитель |Y|. Первый цикл деления зависит от значений делимого и выровненного делителя. При |X| < |Y| деление начинается со сдвига делимого влево, а при |Y| ≤ |X| ≤ 2|Y| сдвиг делимого не выполняется. Затем из сдвинутого или несдвинутого делимого вычитается делитель. Формируемый частичный остаток Х_к запоминается в регистре делимого. После этого анализируется знак разности и определяется цифра, которая помещается в младший разряд частного: эта цифра равна 1, если частичный остаток Х_к ≥ 0, или 0, если Х_к < 0. Далее контролируется число выполненных циклов, и, если деление не завершено, цикл деления повторяется, при этом перед выполнением последующих циклов деления содержимое регистров частного и частичного остатка сдвигается влево.

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

Рассмотренный алгоритм деления обеспечивает формирование модуля частного в виде правильной дроби с нулевым разрядом целой части частного. Для 8-разрядных представлений делимого и делителя 8-разрядный модуль частного формируется за 7 циклов.

В общем случае частное может содержать целую и дробную части (если выполнялась нормализация делителя). При таком представлении целая часть частного обычно размещается в старшем байте, а дробная часть – в младшем байте. По этой причине алгоритм деления должен предусматривать проверку счетчика шагов выравнивания. Если выполнялась нормализация делителя, разрядность частного должна быть увеличена. Для выделения целой части частного опрашивается счетчик шагов выравнивания, и если он не равен 0, выполняется сдвиг частного влево на число разрядов, определяемое значением этого счетчика плюс 1. Формируемое в старшем слове частного значение соответствует целой части частного.

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

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