1. Табличный способ умножения

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

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

Известны способы умножения, основанные на следующем отношении:

. (4-08)

Из отношения (4-08) следует, что для вычисления учетверенного произведения достаточно вычислить разность квадрата суммы и квадрата разности операндов. Для этого придется выполнить три операции сложения/вычитания и две операции возведения в квадрат. Операцию возведения в квадрат можно выполнять табличным способом.

Выполнив элементарные преобразования, получим

, (4-09)

или

, (4-10)

или

(4-11)

где X и Y – сомножители.

Выражения (4-09)–(4-11) позволяют вычислять произведение, выполняя деление на константу 4 или на 2 на разных этапах.

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

Табличный способ умножения прямых кодов двоичных операндов без знака

Пусть операнды имеют одинаковую разрядность . На рис.4-3 показан граф потока данных при вычислении произведения Z=XY в соответствии с выражением (4-09).

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

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

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

Если операнды X, Y двоичные целые без знака с разрядностью , то их произведение Z целое без знака с разрядностью . Тогда код учетверенного произведения 4XY равен коду Z сдвинутому на два разряда влево с занесением нулей в два младших разряда Z и, следовательно, всегда содержит два нуля справа. Из сказанного следует, что операция деления разности квадратов на константу 4 сводится к отбрасыванию двух младших разрядов разности квадратов.

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

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

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

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

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

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

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

Емкость памяти сокращенной таблицы меньше емкости памяти сокращенной таблицы в раза.

Можно заменить операцию усеченного вычитания квадратов операцией усеченного сложения. Для этого достаточно в ячейках таблицы хранить не усеченные квадраты разности , а их дополнения и вычислять сумму содержимого таблиц по правилу сложения дополнительных кодов чисел. Так как результат сложения является положительным произведением, то знак результата сложения всегда (+). Поэтому код суммы будет прямым кодом произведения. Поскольку длина уменьшаемого , а вычитаемого бит, то при сложении необходимо приписать к дополнительному коду вычитаемого слева две 1.

Например, при и значения 01₂, 01₂ В таблицах квадратов два младших разряда, выделенные жирным шрифтом, отсутствуют. Кроме того, в таблице записано дополнение кода 000010 равное 111110. При сложении кода 01011010 с дополнением 111110 необходимо приписать к коду 111110 две 1 слева. После сложения кодов 01011010 и 11111110 по правилу сложения дополнительных кодов получим:

Переносы: 1 1111110

01011010

+ 11111110

XY = 01011000₂= 88₁₀

Здесь две приписанные 1 показаны жирным шрифтом.

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

В

Переносы: 0 0111110

00011010

+ 111110

XY = 01011000₂= 88₁₀

приведенном примере в таблице вместо кода 01011010 будет записан код 00011010, так как 100. Сложение кода 00011010 с содержимым таблицы равным 111110 позволит вычислить произведение:

На рис.4-4 показан граф потока данных при вычислении произведения XY, учитывающий изложенные выше усовершенствования.

В табл.4.10 приведены требуемые объемы памяти таблиц для умножения операндов длиной бит.

Т аблица 4.10

Длина операндов X и Y (бит)	Функция
	X×Y	(X±Y)2	(X+Y)2 Без двух младших разрядов	(|X–Y|)2 Без двух младших разрядов
	Требуемый объем памяти
	n22n+1 (бит)	(n+1)2n+2 (бит)	n 2n+2 (бит)	(n–1)2n+1 (бит)
4	8×256= 2048 бит	10×32= 320 бит	8×32= 256 бит	6×16= 96 бит
8	16×216= 1 Мбит	18×512= 9 Кбит	16×512= 8 Кбит	14×256= 3,5 Кбит
12	24×224=384 Мбит	26×213= 208 Кбит	24×213= 192 Кбит	22×4096= 88 Кбит
16	32×232=128 Гбит	34×217= 4,25 Мбит	32×217= 4 Мбит	30×216=1,875 Мбит

Можно объединить блоки памяти для хранения таблиц рис.4-4 в один блок памяти с двумя портами для считывания. Это позволит сократить память накопителя до n 2ⁿ⁺² бит.