5.2. ВЫЧИСЛЕНИЕ СУММ ПАРНЫХ ПРОИЗВЕДЕНИИ

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

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

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

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

Изменяя порядок суммирования, получают

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

Устройство, реализующее выражение (5.4), представляет собой дерево, состоящее из сумматоров. Входные листья дерева содержат сумматоров, своими входами соединенных с группами схем И, которые выполняют логическое умножение. Корнем дерева является накопительный сумматор со сдвигом вправо, если умножение выполняется по 1-й схеме. Для получения суммы парных произведений потребуется выполнить циклов накоплений и сдвигов, где — количество разрядов сомножителей.

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

Очевидно, что количество этих номеров (т. е. количество возможных разрядных срезов) и, следовательно, количество сумм которые составят некоторую область будет равно

но так как

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

Вместе с тем номер сочетания будет некоторой функцией от

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

Окончательно получим

и

На основании выражений можно сформулировать следующий алгоритм вычисления выражения (5.1):

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

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

3. Далее, приняв определяется число (разрядный срез) по которому находится умножается на сдвигается вправо на один разряд), если умножение производится по первой схеме, изменяется на 1, т. е. Это достигается тем, что все множители сдвигаются на один разряд вправо (при первой схеме).

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

Указанная процедура вычислений сумм парных произведений, представленная в виде направленного графа (см. главу 12), приведена на рис. 5.1, а сам способ назван М. В. Семотюком методом вычисляемых таблиц

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

по-прежнему сохраняются обычные правила сложения и вычитания. Например, если представлены в дополнительных кодах, то выражение учетом выражения (4.17) можно записать следующим образом

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

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

Количество сложений при МВТ составит

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

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

Рис. 5.1

Рис. 5.2

Решая это уравнение относительно получим

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

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