МЕТОДИКА ДЕЛЕНИЯ
Деление — операция, обратная умножению: нахождение одного из сомножителей (частного) по произведению (делимому) и второму сомножителю (делителю). С другой стороны, операцию деления можно рассматривать как умножение делимого на величину, обратную делителю.
В связи с этим для чисел ограниченной точности граничная относительная ошибка деления определяется выражением (1.18), и, следовательно, значность частного не может быть больше значности наименее точного из делимых чисел. Очевидно, что если делимое и делитель представляются «-разрядными дробными числами, то частное также не должно содержать более п разрядов.Произведение точных целых «-разрядных чисел имеет разрядность 2«. Поэтому при делении таких чисел примем разрядности делимого и делителя соответственно 2« и «. Как отмечалось в § 1.1, множество целых чисел незамкнуто относительно операции деления, т. е. частное может быть не только точным целым числом, но и конечной или бесконечной дробью (правильной или неправильной), т. е. числом ограниченной точности. В связи с этим разрядность частного при делении целых чисел определяется необходимой точностью его вычисления и может превышать разрядность делимого или делителя. На практике деление целых чисел выполняется как деление с остатком: находятся целое неполное точное частное
(его произведение с делителем дает целое число, не превышающее делимое) и целый остаток, т. е. разность между делимым и произведением неполного частного на делитель. Разрядность неполного частного не превосходит разрядности делимого, а разрядность остатка — разрядности делителя (остаток по абсолютной величине всегда меньше делителя).
Микропроцессор КР580 не содержит команд деления чисел, поэтому для выполнения этой операции необходимы программы. Любой программный метод деления сводится к последовательному нахождению цифр частного, начиная с его старшей цифры, путем вычитания делителя из делимого или остатка и анализа получаемой разности.
Двоичное деление проще десятичного, поскольку выбор очередной цифры частного производится всего из двух цифр: 0 и 1, причем цифра 1 выбирается при неотрицательной разности (делимое по модулю больше или равно делителю), а цифра 0 — при отрицательной разности (делимое по модулю меньше делителя) [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) деление без вос-
Рис. 1. 8. Вычислительные схемы операции деления
border=0 class="lazyload" data-src="/files/uch_group53/uch_pgroup331/uch_uch1315/image/87.jpg">
ровать дальнейшие вычисления вследствие их некорректности.
Избежать переполнения можно за счет увеличения разрядности частного до разрядности делимого (но при этом в два раза увеличивается и количество циклов деления). Помимо выявления переполнения, при делении чисел необходимо выявлять ситуацию деления на нуль. Заметим, что при анализе переполнения деления целых чисел автоматически выявляется и деление на нуль.4.5.2. ЦЕЛЫЕ БЕЗЗНАКОВЫЕ ЧИСЛА
1.5.2.4. Формат 46:8= (8,8)
Программа Д16 реализует деление с восстановлением остатка и с размещением сдвигаемых влево разрядов частного в освобождаемых младших разрядах делимого:
Программа имеет много команд ветвления в связи с необходимостью выполнения альтернативных операций сложения и вычитания делителя из остатка и последующей проверки каждой из этих операций на знак результата. Затраты памяти и время выполнения этой программы значительно больше, чем программы Д16, что иллюстрирует недостатки программной реализации метода деления без восстановления остатка (по крайней мере для рассматриваемого типа микрокалькулятора).
Тестовые данные для программ приведены в табл. 1.16.
Табл. 1.16. Тесіы деления формата 16:8=(8,8) (целые беззнаковые двоичные числа)
1.5.2.2. Формат 16:8=146,8)
В программах Діб и Д16А СТБ делимого должен быть обязательно меньше делителя, иначе произойдет переполнение формата частного. В ряде приложений такие ограничения неприемлемы. Программа Д1616 устраняет эти ограничения и позволяет находить частное при превышении значением делимого значения делителя:
В основу программы положен алгоритм, описанный в работе [49].
Программа выполняет деление, если делимое не меньше делителя и делитель не равен нулю. Если деление возможно, программа устраняет незначащие нули делимого и делителя путем сдвига этих чисел влево с одновременной фиксацией разности их сдвигов. Например, если делимое и делитель имеют по 8 значащих цифр, то после сдвига делимого влево на 8 разрядов счетчик циклов деления в регистре (В) имеет значение 8 + 0 — — 8 = 0, и деление практически выполнять не надо (достаточно вычесть делитель из делимого). Если же делимое имеет 16, а делитель — одну значащие цифры, то после нормализации чисел счетчик циклов в регистре (В) имеет значение 8 + 7 —0=15, и в этом случае потребуется 15 циклов деления для получения результата. После окончания деления остаток отделяется от частного и приводится к своему истинному значению путем сдвига вправо на величину начального сдвига делителя влево. Расширение диапазона обрабатываемых чисел в программе Д1616 требует дополнительных затрат памяти и времени по сравнению с программами Д16 и Д16А. Тестовые данные для программы приведены в табл. 1.17.Табл. 1.17. Тесты деления формата 16:8=(16, 16) (целые беззнаковые двоичные числа)
t.5.2.3. Формат 24:16= (8,16)
Программа Д24 реализует деление с предварительным преобразованием делителя в дополнительный код и восстановлением остатка путем сохранения и извлечения его из стека (аналогичная программа приведена в работе [21]):
В программе использован прием баланса стека с помощью команд изменения непосредственно указателя стека INX SP вместо обычно применяемых команд извлечения из стека типа POP. Такой прием полезен в случаях, когда все регистры заняты, но необходимо реализовать баланс стека. Тестовые данные, программы приведены в табл. 1.18.
Табл. 1.18. Тесты деления формата 16:8=(16, 16)
(целые беззнаковые двоичные числа)
1.5.2.4.
Формат 32:16= (16,16)Программа Д32, подобно программе Діб, реализует деление по классической схеме с вычитанием делителя, восстановлением остатка путем его сложения с делителем и размещением частного на месте младших байтов делимого (аналогичная программа приведена в работе [71]:
Из-за увеличения разрядности данных в программе Д32 необходимо выполнять в отличие от предыдущих программ 16 циклов деления, что существенно увеличивает общее время выполнения программы. Это время можно несколько уменьшить, если заменить в цикле операцию вычитания делителя из остатка сложением остатка с дополнительным кодом делителя. Эта модификация выполнена в программе Д32А:
Программа Д32А на 10 % сокращает время деления, но требует на 30 % больше затрат памяти. Заметим, что в программе Д32А счетчик цикла выполнен по принципу счета до переполнения, что позволяет использовать его дополнительно для хранения признака переноса при сдвиге остатка влево в регистровой паре (Н, L). Тестовые данные для программ Д32 и Д32А приведены в табл. 1.19.
Табл. 1.19. Тесты деления формата 32:16=(16, 16)
(целые беззнаковые двоичные числа)
1.5.2.5. Формат 16:16= {16,16)
Программа Д162 в отличие от предыдущих программ выполняет деление целых чисел одинаковой разрядности, причем соотношение абсолютных величин делимого и делителя, которые ограниченны в предыдущих программах, не имеет значения, т. е. делитель может быть как меньше, так и больше делимого. В любом случае программа дает неполное точное целое частное и целый остаток:
По своей структуре программа аналогична программе Д32, но отличается от последней представлением полноформатного делимого в регистрах (Н, L, D, Е) с двумя нулевыми старшими байтами, что облегчает анализ ситуаций.
В результате программа Д162 проще и выполняется быстрее, чем Д32. Тестовые данные для программы приведены в табл. 1.20.Табл. 1.20. Тесты деления формата 16:16=(іб, 16) (целые беззнаковые двоичные числа)
Программа Д216 в отличие от Д162 и других вышеприведенных программ выполняет деление целых чисел, когда делимое заведомо меньше, чем делитель:
Результат операции содержит точное неполное дробное частное и дробный остаток. Эта программа может использоваться при делении точных целых чисел с получением приближенного частного, содержащего целую часть, которая вычисляется, например, с помощью программ типа Д32, и дробную часть, определяемую с помощью программы Д216.
Программа Д216 по структуре подобна программам Д24 и Д32А, т. е. использует дополнительный код делителя для вычисления очередного остатка.
Действия программы Д216 можно также интерпретировать как деление целого делимого с множителем 216 (этот множитель смещает запятую в делимом и частном (остатке) на 16 разрядов вправо) и получение целочисленных частного и остатка. Такая интерпретация упрощает представление тестовых данных программы (см. табл. 1.21).
Табл. 1.2J. Тесты деления формата 16:16=(16т 16) (целые беззнаковые двоичные числа)
1.5.3. ЦЕЛЫЕ ЧИСЛА СО ЗНАКОМ
Деление целых двоичных чисел в дополнительных кодах целесообразно выполнять путем их преобразования в прямые коды, деления беззнаковых чисел и коррекции результата с учетом знаков делимого и делителя. Знаки частного и остатка в зависимости от знаков делимого и делителя будут определяться следующими правилами:
( + ) : ( + )=(+, +); ( + ) : (-)=(-, +); (-):( + ) = = ( —, —) и ( —) : ( — )=( + , —). Процедура деления целых чисел со знаком рассматривается ниже на примере программы ДД216.
Программа ДД216 выполняет деление целых двоичных чисел в дополнительном коде с получением дробных частного и остатка:
Программа обращается к подпрограмме беззнакового деления Д216, известным вспомогательным подпрограммам получения дополнительного кода ДОПВ, ДОПД, ДОПН и новым вспомогательным подпрограммам правого одноразрядного сдвига числа соответственно в регистровых парах (В, С), (D.E) и (Н, L):
зуются для сдвига вправо соответственно частного и остатка с целью внесения в формат их знаков, поскольку деление целых беззнаковых чисел дает беззнаковые дробные частное и остаток. После сдвига прямых кодов этих чисел вправо и освобождения (обнуления) крайнего ле-
4—1926
97
вого разряда знак минус вводится, если необходимо, дополнением частного или остатка. Тестовые данные программы приведены в табл. 1.22.
Табл. 1.22. Тесты деления формата 16:16=(16, 16) (целые двоичные числа в дополнительном коде)
1.5.4. ДРОБНЫЕ ЧИСЛА СО ЗНАКОМ
1.5.4.1. Деление дробных чисел
кодах можно выполнять теми же методами, что и деление целых чисел со знаком, т. е. преобразованием в прямые коды, делением беззнаковых чисел и коррекцией результата с учетом знаков делимых чисел. Далее будет приведена программа ДДФ17, реализующая такой способ деления. Вместе с тем деление дробных чисел в дополнительных кодах можно выполнять и непосредственно, без предварительного преобразования их в прямые коды, а на основе модифицированного алгоритма деления без восстановления остатка [61]:
с удвоенным остатком, если их знаки разные. В результате выполнения алгоритма за п циклов деления автоматически образуются цифровые и знаковый разряды частного.
1.5.4.2. Формат 16:16=16
Программа ДДФ16 реализует алгоритм деления (1.26), (1.27):
Знаковый разряд частного определяется в программе на первом цикле деления и при совпадении знаков делимого и делителя устанавливается в единицу (хотя, очевидно, должен быть равен нулю), что позволяет достигнуть регулярности в теле цикла. Но по окончании деления знаковый разряд корректируется: 1-+-0 или 0-+-1. Заметим, что для правильной работы программы делитель должен быть по абсолютной величине больше делимого, иначе возможно переполнение — появление неправильных дробей.
1.5.4.З. Формат 17:17=17
Программа ДДФ17 реализует деление чисел, размещенных в памяти и имеющих знаковый разряд в старшем бите знакового байта:
Программа пересылает делимые числа из памяти в регистры, преобразовывает их в прямые коды, выполняет беззнаковое деление этих кодов посредством подпрограммы Д216А (дополнительный вход в подпрограмму Д216), анализирует переполнение частного (если делимое оказывается по модулю больше делителя), устраняет одноразрядное переполнение формата частного и преобразует частное в дополнительный код, если знаки делимых чисел различны. Она используется в программе деления чисел с плавающей запятой (см. об этом в гл. 2). Тестовые данные
для программы приведены в табл. 1.23. Эти данные можно использовать и для проверки программы ДДФ16 (предварительно сдвинув шестнадцатеричные числа на один двоичный разряд вправо с учетом знака).
Табл. 1.23. Тесты деления формата 17:17=17 (дробные двоичные числа в дополнительном коде)
