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

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

Если считать, что цифры множителя распределены в каждом разряде так, что появление в каждом разряде любой цифры от О до 5 - 1 равновероятно, то на каждый

разряд множителя в среднем потребуется сло-

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

--ioggN. При 5 = 2 оно равно 0,5 logN. Введем

оценочную функцию

(S-1)1одоЛ с 1

Ф(5)= . \, = Г о • (1-10)

График этой функции показан на рис. 1.14. На этом же рисунке показана таблица некоторых значений Ф(5). Смысл функции Ф(5) сводится к тому, что она показывает, во сколько раз число сложений в си-

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

Ф (5) растет монотонно с ростом 5 (для 5 > 2). При 5-оо она ведет себя как 2F{S).

Допущение, которое использовалось при построении функции Ф(5), состояло в том, что время одного суммирования предполагалось независимым от S. Это допущение верно далеко не всегда, и его истинность ф.. зависит от той схемы

сумматора, которая

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

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

0 7 2,35678 3 70 s Рис. 1.14

долгкны- поступать на такую" схему последовательно, . и каждая цифра сама подается в виде последовательности сигналов определенной природы. Учитывая, что существуют сумматоры параллельного и последовательного типа (см. § 1.4), мы получаем следующие четыре типа сумматоров; комбинационные сумматоры параллельного типа, накапливающие сумматоры параллельного типа, комбинационные сумматоры последовательного типа и накапливающие сумматоры гюсле-довательного типа.

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

Для сумматоров второго типа время суммирования S

увеличивается в - раз за счет перехода к системе

счисления с основанием 5 (если по-прежнему считать, что в любом разряде записи числа все цифры равновероятны). Это означает, что для параллельных сумматоров накапливающего типа можно считать, что время суммирования пропорционально S. Оценочная •.функция в этом случае принимает вид

ФЧ5) = = . . (1.1.)

Для сумматоров третьего типа время сложения в одном разряде практически не зависит от S, но число разрядов в записи числа тем меньше, чем больше 5. Поэтому время сложения на комбинационном сумма- торе последовательного типа зависит от S так, что

оно оказывается пропорциональным "jjOgz) .

Оценочная функция для этого случая имеет вид

ФгЗ). (1.12)

Наконец, для сумматоров четвертого типа время сложения, с одной стороны, пропорционально S (так как сумматор состоит из накапливающих одноразрядных суммирующих схем), а с другой стороны, оно пропорционально (loga)" (так как сумматор является