1. Умножение чисел большой разрядности

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

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

Пусть X и Y сомножители в прямом коде без знака длиной разрядов в системе счисления с основанием P. Представим их как

,

,

где – группы старших и младших разрядов X и Y длиной . Тогда

. (4-12)

При вычислении по (4-12) программным способом нужно выполнить 4 умножения, 2 операции сдвига и 3 сложения.

На рис.4-5 приведена структура матрицы слагаемых при вычислении XY по (4-12). Здесь прямоугольник можно интерпретировать как слово, содержащее указанный в нем код, или как матрицы частных произведений или как системы, вычисляющие , например, табличным способом (раздел 4.4.3).

И з структуры матрицы рис.4-5 следует, что сложение можно заменить гораздо более простой операцией конкатенация (сцепление строк символов). Это сокращает количество сложений до 2. Кроме того, младшие разрядов произведения могут быть скопированы в младшие разрядов произведения XY и не участвовать в операциях сложения, что позволяет сократить разрядность слагаемых и ускорить вычисление произведения.

Известно другое решение, позволяющее сократить количество умножений до трех:

. (4-13)

В справедливости (4-13) не трудно убедиться. Сокращение количества умножений дает существенный выигрыш во времени и/или в оборудовании.

На рис.4-6 показано взаимное расположение произведений при их сложении/вычитании.

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

П оскольку

,

то

. (4-14)

Младшие n разрядов можно копировать в младшие n разрядов произведения . Тогда нет необходимости сдвигать произведения , и на n разрядов влево. Достаточно сложить с конкатенацией и старших n разрядов . Результат сложения записать в старшие 3n разрядов произведения .

При вычислении прямых кодов значащих разрядов произведения X и Y в дополнительном коде преобразование операндов в дополнительный код и результата в прямой код выполнять не следует, поскольку запись положительных чисел в обоих кодах совпадает. Вычисление в дополнительном коде позволяет всегда выполнять сложение с , причем их сумма всегда положительная (4-14).

В специализированном вычислителе достаточно вычислять дополнительные коды произведений , , без разрядов знака. Операции вычитания и можно заменить сложением (раздел 4.3.7).

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

Пример 4-62. Выполняется умножение прямых кодов значащих разрядов десятичных чисел X и Y с разрядностью в соответствии с (4-13) и схемой рис.4-6 в дополнительном коде.

В

A B C D E F

X: 0100 9900 0099 9999 9998 9040

Y: 0001 0099 9900 9999 9899 3090

x₀y₀: 0000 0000 0000 9801 9702 3600

x₁y₁: 0000 0000 0000 9801 9702 2700

(x₁ - x₀)(y₀ - y₁): 00001 09801 09801 00000 00001 03000

x₁y₁. x₀y₀: 00000000 00000000 00000000 98019801 97029702 27003600

XY: 00000100 00980100 00980100 99980001 98970202 27933600

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

В вариантах A-F так как знаки разностей совпадают. Зачеркнутый перенос при всегда равен 0. Поэтому его отбрасывание не влияет на результат сложения строк.

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

В вариантах G-L так как знаки разностей не совпадают. Строка произведения содержит дополнение его кода до веса разряда знака. Зачеркнутый перенос при всегда равен 1. Его отбрасывание уменьшает значение суммы строк.

В

G H I J K L

X: 0001 0099 9900 2099 9899 9040

Y: 0001 0099 9900 1099 9899 9030

x₀y₀: 0001 9801 0000 9801 9801 1200

x₁y₁: 0000 0000 9801 0200 9604 8100

(x₁ - x₀)(y₀ - y₁): 19999 10199 10199 12969 19999 17000

x₁y₁. x₀y₀: 00000001 00009801 98010000 02009801 96049801 81001200

XY: 00000001 00009801 98010000 02306801 97990201 81631200

варианте L , , , . Поскольку , а , то код значащих разрядов содержит дополнение произведения до 10000, т.е. . Если при сложении суммы 1200+8100=9300 с 7000 зачеркнутый перенос не отбрасывать, то будет ошибочно вычислено произведение равное 82631200.

В вариантах J и K при сложении возникает перенос из старшего разряда равный 1, но этот перенос отбрасывать не следует.

Почему следует отбрасывать перенос? Ответ на этот вопрос вытекает из правила сложения в дополнительном коде. При сложении в дополнительном коде необходимо выравнивать форматы слагаемых, приписывая слева нули к положительным и цифры обратные нулю к отрицательным операндам с меньшим количеством разрядов целого (например, так как это делалось в примере 4-32).

В нашем частном случае слагаемые и всегда положительные и к ним слева должны быть приписаны нули. Это позволяет задать приписываемые нули по умолчанию, что и сделано в примере 4-62.

Слагаемое в зависимости от его знака должно быть расширено влево нулями или девятками.

В вариантах A-F знак слагаемого (+), и расширяющие нули заданы по умолчанию. В вариантах G-L . Поэтому соответствующее слагаемое должно быть расширено влево цифрой 9. Так как , результат сложения первой тройки строк должен быть всегда положительным. Следовательно, при сложении тройки строк должен обязательно распространиться перенос 1 через цепочку 9, чтобы сумма была положительной и содержала в старших разрядах цепочку 0. Предвидя это можно сразу вместо цепочки 9 записать цепочку 0 и не вычислять перенос, который должен был бы обнулить цепочку 9. Это позволяет сократить затраты оборудования и времени на вычисления.

Пример 4-63. Выполняется в соответствии с (4-13) и схемой рис.4-6 умножение в дополнительном коде прямых кодов значащих разрядов двоичных чисел X и Y с разрядностью .

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

В вариантах A-F так как знаки разностей совпадают. Зачеркнутый перенос при всегда равен 0. Поэтому его отбрасывание не влияет на результат сложения строк.

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

В

A B C D E F

X: 0100 1100 0011 1111 1110 1001

Y: 0001 0011 1100 1111 1011 0111

x₀y₀: 0000 0000 0000 1001 0110 0011

x₁y₁: 0000 0000 0000 1001 0110 0010

(x₁ - x₀)(y₀ - y₁): 00001 01001 01001 00000 00001 00010

x₁y₁. x₀y₀: 00000000 00000000 00000000 10011001 01100110 00100011

XY: 00000100 00100100 00100100 11100001 10011010 00111111

G H I J K L

X: 0001 0011 1100 1011 1011 1101

Y: 0001 0011 1100 0111 1011 1000

x₀y₀: 0001 1001 0000 1001 1001 0000

x₁y₁: 0000 0000 1001 0010 0100 0110

(x₁ - x₀)(y₀ - y₁): 11111 10111 10111 11110 11111 11100

x₁y₁. x₀y₀: 00000001 00001001 10010000 00101001 01001001 01100000

XY: 00000001 00001001 10010000 01101101 01111001 01101000

вариантах G-L , так как знаки разностей не совпадают. Строка произведения содержит дополнение его кода до веса разряда знака. Зачеркнутый перенос при всегда равен 1. Его отбрасывание уменьшает значение суммы строк.

В варианте L , , , . Поскольку , а , то код значащих разрядов содержит дополнение произведения до 10000, т.е. . Если при сложении суммы 0000+0110=0110 с 1100 зачеркнутый перенос не отбрасывать, то будет ошибочно вычислено произведение равное 10101000.

При большой разрядности операндов можно разбивать каждую группу разрядов длиной n на две группы разрядов длиной n/2 и вычислять произведения по правилам рассмотренным выше.

Можно сомножители длиной 3n разбивать на три группы разрядов длиной n. Тогда

,

,

и

. (4-15)

Вычисление по (4-15) потребует выполнение 9 умножений n разрядных целых без знака. Можно сократить количество умножений до 6, если воспользоваться выражением (4-16) эквивалентным (4-15):

(4-16)

Известны способы умножения многоразрядных двоичных чисел, использующие быстрое преобразование Фурье [5, стр. 337], [13-17], которые позволяют вычислять 2n разрядное произведение за время меньшее, чем рассмотренные.