1. Операция алгебраического умножения

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

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

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

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

В разделах 4.4.1 – 4.4.4 рассмотрены способы точного умножения.

1. Умножение в прямом коде

Результат умножения в прямом коде двух операндов без знака содержащих и m значащих разрядов имеет значащих разрядов. При разрядность результата равна . Например, в десятичной системе счисления 999´99=98901.

При умножении операндов со знаком и значащими разрядами произведение, содержит разряд. Поэтому при записи произведения в формат, вдвое превышающий формат операндов, существует слева один избыточный значащий разряд, в который следует записывать 0. Например, если операнды со знаком представлены в прямом двоичном коде в шестнадцати битовом формате, то значащих разрядов 15, и разрядность произведения, включая его знак, 2´15+1=31. Поэтому в 32 разрядный формат придется записывать 0 в разряд, следующий за разрядом знака.

Знак произведения вычисляют сложением по модулю 2 знаковых разрядов операндов, в том числе, если один или оба операнда равны 0.

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

Чтобы сократить количество сложений используют таблицы умножения цифр и тот факт, что результат умножения числа на основание системы счисления P совпадает со значением этого числа, сдвинутым на один разряд влево с занесением 0 в крайний правый разряд. Например, в десятичной системе счисления: ; в двоичной: .

Вычисляют частные произведения множимого X на каждый разряд множителя Y. Вес частного произведения учитывают сдвигом его влево на необходимое число разрядов относительно частного произведения X на младший разряд Y. Суммируют частные произведения с учетом их веса равного весу разряда множителя.

Этот прием используют при умножении десятичных чисел на бумаге. При умножении в системе счисления с основанием все действия выполняются аналогично. Отличие лишь в том, что используется таблица умножения цифр системы счисления с основанием P и сложение выполняется по правилам справедливым в этой системе счисления.

Таблицы умножения цифр системы счисления P можно получить, перемножив количественные эквиваленты ее цифр в десятичной системе и представив результаты в системе счисления с основанием P. Например, произведение цифр шестнадцатеричной системы счисления имеет количественный эквивалент . Следовательно, , и результат умножения в данном разряде равен 7₁₆, а перенос в следующий разряд равен 8₁₆.

Составьте самостоятельно таблицы умножения двоичных, восьмеричных и шестнадцатеричных цифр, используя изложенный способ.

При вычислении частных произведений в системе счисления с основанием необходимо учитывать переносы в старшие разряды, возникающие при умножении цифры X на цифру Y. В двоичной системе такие переносы отсутствуют, что существенно упрощает умножение.

В двоичной системе счисления частное произведение числа X на цифру числа Y равно

• 0, если цифра Y равна 0;

• X, если цифра Y равна 1.

Пример 4-25. Пусть необходимо перемножить прямые двоичные коды чисел 0|1101|01 и 1|1011|10. Определим знак результата: – знак произведения минус.

Н айдем матрицу частных произведений значащих разрядов.

Первая и предпоследняя строки матрицы нулевые, так как они содержат частные произведения X на разряды Y равные нулю. Остальные строки содержат X, так как соответствующие им разряды Y равны 1. Каждое последующее частное произведение сдвинуто на разряд влево относительно предыдущего, чтобы учесть его вес (удвоить).

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

Можно поступать иначе, поочередно складывать строки матрицы в любом порядке. Например, сверху вниз: первую строку со второй; их сумму с третьей и т.д. Ничто не мешает складывать строки снизу вверх.

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

Так, например, если в столбце пять единиц, включая единицы переноса в этот столбец, то код числа единиц в данном столбце 101. Так как младший разряд кода 1, то разряд произведения в данном столбце 1. Перенос в следующий слева столбец равен 0, а перенос в последующий столбец 1.

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

В примере 4-25 в правом столбце 0 единиц, сумма равна 0 и нет переносов в последующие столбцы. Во втором столбце код числа единиц 01. Следовательно, сумма в столбце равна 1 и перенос в последующий столбец 0. Продолжите вычисление результата этим способом самостоятельно.

В системах счисления с основанием , вычисление частных произведений существенно осложняется по сравнению с двоичной системой, так как произведение цифр больших, чем 1 может быть двухразрядным числом. Например, в десятичной системе счисления . Это приводит к необходимости выполнять прибавление переносов при вычислении частного произведения множимого на цифру множителя. Чтобы избежать прибавления переносов при вычислении частного произведения, можно представить частное произведение в матрице в виде двух строк. В одной строке записывать цифру произведения, а в другой – цифру переноса с соответствующим сдвигом. Суммируя все строки матрицы, получим результат умножения.

Пример 4-26. Пусть необходимо перемножить прямые десятичные коды чисел +9063 и –8015. Знак произведения вычислим сложением по модулю 2 знаковых разрядов сомножителей: .

Для вычисления частного произведения X на разряд Y умножаем разряды X на разряд Y и представляем частное произведение парой строк в матрице.

В варианте A верхняя строка пары содержит цифры переноса, а нижняя – цифру произведения в данном разряде. Поэтому верхняя строка в каждой паре сдвинута на разряд влево относительно нижней строки. Верхняя пара строк представляет частное произведение на младший разряд множителя равный 5. Следующая пара строк представляет частное произведение на цифру 1 множителя и сдвинута на разряд влево относительно предыдущей пары, чтобы учесть ее вес 10.

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

A B C D E F

X: 0| 9063 9063 9063 9063 FF 1111 1111

Y: 1| 8015 8015 8015 8015 FF 1111 1111

4031 5005 7042 0015 E1 1110 0001

5005 4031 2084 4530 E1 1110 0001

0000 9063 0000 0003 E1 1110 0001

9063 0000 0000 0906 E1 1110 0001

0000 0000 0000 0000 FE01 1111 1110 0000 0001

0000 0000 9063 0000

7042 2084 4031 0024

2084 7042 5005 7248

1| 72639945 72639945 72639945 72639945

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

Очевидно, что перемещение цифры в пределах одного столбца не может изменить значения суммы строк, т.е. величину произведения. В варианте D цифры смещены так, чтобы строки частного произведения содержали пары разрядов произведений цифры множимого на цифру множителя. Например, первая пара строк содержит произведения цифр 9063 на 5, т.е. 45 00 30 15.

Ничто не мешает вычислять пару строк частного произведения множимого на цифру множителя, начиная с любого разряда множимого. Например, в варианте D, умножать на цифру 5, начиная со старшего разряда множимого и вначале записывать 45, затем 00, 30 и 15.

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

Цифра младшего разряда произведения всегда равна единственной цифре в столбце младшего разряда. Поэтому этот столбец можно опустить, сразу записывая его цифру в младший разряд результата. Остальные цифры произведения можно вычислять подсчетом числа единиц в столбцах с учетом переносов, начиная со столбца второго разряда справа.

В вариантах A, B, C и D в столбцах 2, 3 и 4 разряда количество единиц 4, 9 и 9 соответственно, и нет переносов в последующие столбцы. В столбце 5 количество единиц 4+9+2+8=23. Поэтому цифра произведения в пятом столбце 3 и перенос в столбец 6 равен 2. Если количество единиц в столбце равно, например 234, что может быть при умножении много разрядных чисел, то цифра произведения в этом столбце 4, перенос в следующий столбец 3, а в последующий столбец 2.

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

В варианте E выполнено умножение шестнадцатеричных чисел. Матрица частных произведений построена по тому же принципу, что и в варианте D. Для умножения в этой системе счисления нужно помнить таблицу умножения размерностью 16´16, что сложнее сделать, чем в десятичной системе счисления (размерность 10´10) и тем более чем в двоичной (размерность таблицы 2´2). Произведение F´F=E1, так как 15₁₀´15₁₀=225₁₀= E1₁₆.

В варианте F шестнадцатеричные цифры F, E и 1 в строках чисел варианта D заменены их двоичными эквивалентами. Фактически выполнено преобразование шестнадцатеричных чисел в двоичные. Вариант F можно рассматривать как иллюстрацию способа умножения двоичных чисел с применением таблицы умножения шестнадцатеричных чисел. Он позволяет по сравнению со способом умножения в примере 4-25 сократить длину пробега переноса и вдвое уменьшить количество строк в матрице частных произведений.