МЕТОДИКА УМНОЖЕНИЯ
Умножение точных «-разрядных чисел дает точное 2 «-разрядное произведение. Погрешность этой операции для чисел ограниченной точности определяется следующим правилом: граничная относительная ошибка произведения приблизительно равна сумме граничных относительных ошибок представления сомножителей [15, 70]'
результат умножения чисел ограниченной точности (будь это целые или дробные числа) не может иметь больше значащих цифр, чем их имеет наименее точный сомножитель.
Очевидно, что при умножении «-разрядных чисел ограниченной точности произведение является также «-разрядным числом, причем, если значность каждого из двух сомножителей равна «, то в произведении предпоследняя цифра —(«— 1)-я для дробного и 2-я для целого числа — безусловно верна, а последняя не вполне точна (сомнительна). При увеличении количества сомножителей пропорционально растет граничная относительная ошибка произведения и уменьшается его значность.Микропроцессор КР580 не содержит команд умножения чисел, и поэтому умножение требует разработки программ. Любой программный метод выполнения умножения (за исключением громоздкого табличного метода) основан на многократном выполнении операций сложения. Очевидно, что простейший способ умножения целых беззнаковых чисел X • Y = Z есть суммирование множимого А с накоплением его столько раз, сколько единиц содержит значение множителя Y. Этот способ требует при больших значениях Y значительных затрат времени на выполнение многократных операций сложения, и поэтому применение его ограниченно.
Сокращение количества операций сложения при реализации умножения основано на методах совместного анализа цифр множителя [32, 33, 46, 611. Эти методы дробят
процесе получения произведения на ряд шагов, связанных сформированием частичных произведений (ЧП) — произведений множимого на отдельные разряды или группы разрядов множителя — и их суммированием, т.
е. формированием суммы частичных произведений (СЧП). Ускоренные методы умножения используют анализ одновременно двух и более цифр множителя для получения ЧП, а обычные (неускоренные) методы — анализ поочередно каждой отдельной цифры множителя. Ускоренные методы требуют специальных схемотехнических решений, которые, как правило, не используются в микропроцессорах, и поэтому здесь применяются обычные методы неускоренного умножения.Методы умножения двоичных беззнаковых чисел основаны на представлении произведения в виде полинома [с учетом формулы (1.4)]:
(поскольку младшие п разрядов множимого равны нулю) и такого же формата для операции сложения (сложение выполняется со старшими п разрядами СЧП). Формулы (1.19) и (1-20) определяют алгоритмы умножения с младших разрядов множителя соответственно при неподвижной и подвижной СЧП.
Форматы множимого и операции сложения можно ограничить п разрядами, если изменить процедуру обработки, определяемую формулой (1.19), следующим образом:
Аналогичные формулы имеют место при умножении со старших разрядов множителя:
Рассмотренным четырем алгоритмам умножения со- ответствуют четыре вычислительные схемы, используемые при разработке программ умножения (рис. 1.5): схема 1 (рис. 1.5, а) соответствует выражениям (1.20), (1.21); схема 2 (рис. 1.5,6) —формуле (1.19); схема 3 (рис. 1.5, в).— соотношениям (1.22), (1.23); схема 4 (рис. 1.5, г) —формулам (1.24). На схемах обозначены: МН — множители, ММ — множимые (с указанием в
скобках разрядности данных). Анализ разрядов множителя осуществляется путем сдвига его разрядов вправо (умножение с младших разрядов в схемах 1,2) или влево (умножение со старших разрядов в схемах 3, 4) с модификацией признака переноса CY, используемого для управления процессом накопления СЧП.
Последовательность выполнения в вычислительных схемях опепяпий рпкигя и сложрния поясняется в тябл.
Рис. 1.5. Вычислительные схемы операции умножения
ных схем описаны далее, при рассмотрении конкретных программ умножения.
Табл. 1.3. Умножение по схеме 3
Методы умножения беззнаковых чисел применимы и для вычисления произведений двоичных знаковых чисел в дополнительных кодах. Пусть целые двоичные сомножители X и Y представлены в дополнительном коде в «-разрядном формате, старший разряд которого исполь-
Помимо прямой коррекции произведения чисел в дополнительном коде путем вычитания поправок из псевдопроизведения, существуют методы, обеспечивающие автоматическое введение поправок при любых знаках сомножителей. В частности, известен алгоритм Бута [5, 61]. Его программная реализация для микропроцессора КР580 подробно рассматривается далее (см. п. 1.3.3).
Методы умножения двоичных чисел рассматривались выше на примере целых чисел. Все они справедливы и по отношению к дробным числам. Необходимо помниіь, что дробные числа являются, как правило, числами ограниченной точности, и поэтому формат их произведения обычно не превышает формата сомножителей (в отличие от удвоенного формата произведения точных целых
дробных, знаковых и беззнаковых чисел различных форматов, обеспечивающих необходимую точность и диапазон значений как сомножителей, так и их произведений.
1.3.2. ЦЕЛЫЕ БЕЗЗНАКОВЫЕ ЧИСЛА
1.З.2.1. Формат 8-8=16
Программа У8 реализует простейший способ умножения путем накопления суммы множимого:
в (D) = 0), что минимизирует длительность цикла накопления.
Программа У88А реализует умножение по вычислительной схеме 1 (см. рис. 1.5, а):
граммы и ее время можно уменьшить (на 5 байт и 22 такта), если исключить операции проверки сомножителей на нуль (эти операции сокращают среднее время выполнения программы, когда в потоке обрабатываемых данных часто встречаются нулевые сомножители). Заметим, что сложение множимого (Р) с двухбайтной суммой в регистровой паре (Н, L), как и в предыдущей программе, осуществляется командой DAD D, но при этом в отличие от предыдущей ситуации может возникать переполнение СЧП. Это переполнение автоматически устраняется при сдвиге СЧП вправо. Микропроцессор КР580 не имеет команд сдвига вправо двухбайтных данных, поэтому операция такого сдвига выполняется побайтно с использованием аккумулятора.
Программа У88А представляет собой вариант «бесхитростного» программирования схемы 1, при котором МН и СЧП размещаются, согласно-схеме, в структурно раздельных элементах: МН — в регистре (С), а СЧП — в регистровой паре (Н, L). Более детальный анализ схемы 1 показывает, что операции сдвига вправо МН и СЧП можно совместить, если размещать выдвигаемые младшие разряды СЧП в освобождающиеся старшие разряды МН [33]. Эту «хитрость» реализует программа У88А1 (аналогичная программа приведена в работе [20]):
В программе У88А1 множитель размещен в регистре (С), СТБ СЧП — в регистре (В), а МЛБ СЧП в процессе работы программы размещается в освобождающихся разрядах регистра (С). Поскольку после 8 сдвигов МН вправо необходимо в соответствии с алгоритмом (1.20) произвести последний, 9-й сдвиг вправо СЧП, счетчик цикла перед началом программы устанавливается в регистре (D) = 9. Последний, 9-й неполный цикл используется только для сдвига вправо МЛБ СЧП в регистр (С) (9-й сдвиг СТБ СЧП происходит в конце полного 8-го цикла).
Максимальная длительность полного цикла равна 62 тактам, а время программы 7^45 + 62-8 = = 541 такту. Программа У88А1 экономичнее программы У88А по длине на 24 %, а по затратам времени на 17 % (при условии, что в программе У88А исключены операции проверки сомножителей на нуль, отсутствующие в программе У88А1).Программа У88Б в отличие от программ У88А и У88А1 выполняет умножение по вычислительной схеме 3 (см. рис. 1.5, в):
Программа У88Б1 экономичнее программы У88А1 по длине на 10 % и по затратам времени на 26 %, но использует для размещения данных лишний регистр. Быстродействие программы можно увеличить (с 396 до 257 тактов), если раскрыть цикл, т. е. исключить команды проверки конца цикла, а сам цикл повторить 8 раз путем 8-кратного размещения команд цикла в теле программы [18]. Сравнение вычислительных схем 1 и 3 по их программным реализациям показывает предпочтительность использования схемы 3. Ее преимущество объясняется наличием у микропроцессора КР580 команд сложения типа DAD, обеспечивающих быстрое сложение двухбайтных данных и их сдвиг влево. Из-за отсутствия команд сдвига вправо двухбайтных данных малоперспективна схема 4.
Программа У88В реализует умножение по вычислительной схеме 2 (см. рис. 1.5, б) (аналогичная программа приведена в работе [16]):
Особенность этой программы заключается в том, что МН постоянно размещен (и сдвигается) в аккумуляторе, причем конец цикла контролируется не по счетчику (счетчик цикла отсутствует), как в предыдущих программах, а по остатку МН в аккумуляторе. Выполнение же операций сложения и сдвига осуществляется, как и в программах У88Б и У88Б1, посредством команд типа DAD, минуя аккумулятор, причем для сдвига МН влево временно используется та же регистровая пара (H,L), в которой размещается СЧП.
Программа У88В по быстродействию
1.З.2.2. Форматы 8 - 16=24, 8 • 16= 16
Программа У24 реализует умножение по вычислительной схеме 3 аналогично программе У88Б:
более высокого уровня широко используется ее упрощенный вариант (без проверки сомножителей на нуль) — программа У24А (аналогичная программа приведена в работе [21]):
Иногда при умножении целых чисел возникает необходимость получения произведения в сокращенном формате, не превышающем формат одного из сомножителей. Обычно такое произведение формируют из полноформатного путем его округления. Программа У168 реализует сокращенный формат умножения путем симметричного округления произведения формата 16-8 = 24, вычисляемого предварительно подпрограммой У24:
В результате округления точного произведения формируется произведение ограниченной точности, погрешность которого определяется формулами (1.10) и (1.12). Заметим, что модуль полученного произведения содержит неявный множитель 256, так как сокращенный формат представляет только СТБ и СРВ полного произведения (МЛБ отбрасывается). Тестовые наборы данных для программ У24 и У24А приведены в табл. 1.6.
Табл. 1.6. Тесты умноження формата 8-16=24 (целые двоичные беззнаковые числа)
1.З.2.З. Формат 16- 16=32
Программа У32А, подобно программам У88Б, У24, реализует умножение по вычислительной схеме 3 (аналогичная программа приведена в работе [71]):
Увеличение разрядности сомножителей и произведения ведет к росту количества используемых регистров и усложнению типа передач данных между ними, что в результате увеличивает длину программы, длительность ее цикла и общее время ее выполнения. Максимальная длительность цикла умножения в программе У32А равна
сдвига МН временно используется та же регистровая пара (Н, L), что и для накопления СЧП; 2) для сохранения переноса от сдвига множителя (с целью последующего его анализа) используется старший бит аккумулятора; 3) счетчик конца цикла построен не по принципу уменьшения переменной цикла до нуля, как в предыдущих программах, а, наоборот, по принципу увеличения переменной цикла от нуля до переполнения счетчика (аккумулятора) .
Программа У32А выполняет процесс умножения как 16-кратное повторение цикла умножения множимого на очередной разряд множителя. Благодаря этому обеспечиваются регулярная структура программы и минимальные затраты памяти, но время выполнения программы велико. Его можно сократить, если организовать процесс вычисления произведения формата 16-16 = 32 как последовательность двух подпроцессов умножения форматов 16 ■ 8 = 24 для МЛБ МН и 16 • 8 = 24 для СТБ МН с последующим суммированием полученных произведений с учетом их сдвига на один байт относительно друг друга. Этот алгоритм реализует программа У32Б (аналогичная программа приведена в работе [21]):
щая подпрограмма У24А. В результате программа У32Б на 34 % снижает время умножения по сравнению с программой У32А, но на 50 % увеличивает затраты памяти (с учетом длины подпрограммы У24А). В программе У32Б для временного хранения первого промежуточного произведения (из-за нехватки свободных регистров) использована область стека, причем для записи СРБ ПР1 и МЛБ ПР1 из регистровой пары (Н, L) в стек использована команда XTHL обмена вершины стека с регистровой парой (Н, L). Действие этой команды поясняется
В программе для получения промежуточных произведений формата 16-8 — 24 используется быстродействую
на рис. 1.6. Указатель стека (SP) перед выполнением
Рис. 1.6. Действие команды XTHL
команды XTHL указывает на ячейку стека, в которую предыдущей командой PUSH В записан младший байт BL регистровой пары (В, С). При выполнении команды XTHL содержимое вершины стека по адресам (SP) и (SP) +1 переписывается в регистровую пару (Н, L), а содержимое регистровой пары (Н, L) — на место ВН, BL (ВН — старший байт регистровой пары (В, С)). Глубина стека в программе равна 4 байтам. Тестовые данные для программ У32А, У32Б приведены в табл. 1.7.
Табл. 1.7. Тесты умножения формата 16-16=32 (целые двоичные беззнаковые числа)
1.3.3. ЦЕЛЫЕ ЧИСЛА СО ЗНАКОМ
1.З.З.1. Формат 8-8=16
Программа УД88 выполняет умножение, обращаясь к подпрограмме У88Б:
Вместо подпрограммы У88Б можно использовать подпрограмму У88Б1, если предварительно передать МН из регистра (С) в аккумулятор и не ставить задачу сохранения МН после выполнения УД88. Глубина стека в программе равна 2 байтам. Тестовые данные для программы УД88 приведены в табл. 1.8.
Табл. 1.8. Тесты умножения формата 8-8=16 (целые двоичные числа в дополнительном коде)
1.З.З.2. Формат 8 • 16= 24
Программа УД24 выполняет умножение, обращаясь к подпрограмме У24:
Глубина стека — 2. Тестовые данные для программы УД24 приведены в табл. 1.9.
Табл. 1.9. Тесты умножения формата 8-16=24 (целые двоичные числа в дополнительном коде)
1.З.З.З. Формат 16 ■ 16= 32
Программа УД32 выполняет умножение, обращаясь к подпрограмме У32Б:
Тестовые данные для программы УД32 приведены в табл. 1.10.
Табл. 1.10. Тесты умножения формата 16-16=32 (целые двоичные числа в дополнительном коде)
1.З.З.4. Формат 8-24=32
Программа УД248 реализует умножение чисел формата 8-24 = 32 как сумму произведений МН соответственно на МЛ Б и СРБ ММ формата 8 • 16 = 24 и СТБ ММ формата 8-8=16, используя быстродействующие подпрограммы У24А и У88Б1 и операцию вычитания поправок из псевдопроизведения:
Для временного хранения промежуточных результатов в программе задействована область стека. Тестовые данные для программы УД248 приведены в табл. 1.11.
Табл. 1.11. Тесты умножения формата 8-24=32 (целые двоичные числа в дополнительном коде)
1.3.4.