Битовые операции

Каждый алгоритм строится на основе некоторого фиксированного набора базовых операций, и, согласно определениям из § 1, алгебра­ическая сложность алгоритма рассматривается при допущении, что затратность операций не зависит от размеров операндов. С позиций компьютерной арифметики это допущение вполне приемлемо, если каждый из операндов умещается в одном слове памяти. Но оно пере­стает быть приемлемым, если разрешаются операнды любой длины и вычисления проводятся в рамках арифметики многократной точ­ности (арифметики длинных чисел). Здесь анализ сложности должен исходить из других принципов.

Приемлемой является, например, следующая модель как систе­ма допущений, принимаемых нами при анализе алгоритмов. Число представляется набором бит, являющихся содержимым его двоичных разрядов (знак числа — тоже бит, например, обычно знаки + и -изображаются соответственно нулем и единицей), и все арифмети­ческие операции сводятся, в конечном счете, к битовым операци­ям. В качестве битовых операций могут выступать булевы операции V, Л, ­ (другая нотация: or, and, not) при интерпретации 1 = «истина», О= «ложь» встречающихся бит; эти операции считаются равнозатрат-ными. Все биты, участвующие в записи числа, считаются равнодо­ступными.

Можно смотреть на все это так, что ячейки памяти машины со­держат по одному биту каждая, а в остальном действует принцип РАМ—ячеек бесконечно много и они в любой момент равнодоступ­ны. Это—битовая модель вычислений (соответствующее сокращение БМ может расшифровываться как «битовая модель» и как «битовая машина»).

Для анализа сложности с использованием БМ нет необходимости переписывать алгоритмы, детализируя их до уровня битовых опера-



Глава 5. Битовая сложность


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

Определение 19.1.Пусть выбран какой-то размер входа. Рассмот­рение каждой из базовых операций алгоритма А как процедуры, ос­нованной на битовых вычислениях, и измерение затрат на выпол­нение А для каждого конкретного входа в битовых операциях или, соответственно, в хранимых дополнительных битах, приводит к би­товой сложности (временной или пространственной) алгоритма А.

Для нахождения битовой сложности какого-либо алгоритма, по­строенного на основных арифметических операциях над целыми чис­лами, полезно знать битовые сложности самих основных арифмети­ческих операций. Мы исследуем школьные алгоритмы сложения, вы­читания, умножения и деления «столбиком» неотрицательных целых чисел в двоичной системе.

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

Алгоритм сложения «столбиком» будем обозначать буквами Add, от английского слова addition —сложение. Обозначим через а и Ъ операнды алгоритма (a, beN+), через т12 — их битовые длины: т1 = А(а), т2 = А(Ь).


§ 19. Битовые операции



Лемма 19.1.Количество СТш{а,Ъ) битовых операций, затрачива­емых при сложении аиЪ «столбиком», удовлетворяет неравенствам

тт{тъ т2} s= СТш(а, Ъ) s= c(max{mlJ m2} + 1), (19.1)

где с — некоторая положительная константа.

Доказательство. Принимая во внимание замечание относитель­
но ограниченности затрат на построение каждого разряда суммы,
а также то, что битовая длина суммы а + Ъ не может превышать
тах{тът2} + 1, получаем оценку C\dd{a, Ъ) s= c(max{m1, т2} + 1).
Пусть т! = min{m1, т2}. Очевидно, что т! младших цифр суммы а + Ъ
получаются выполнением битовых операций над соответствующими
цифрами обоих слагаемых и битами переноса (в то время как часть
цифр старших разрядов большего из слагаемых может быть просто
перенесена в старшие разряды суммы). Это дает нам неравенство
тт{тът2}^с1АА(.а,Ъ).

В дальнейшем будем полагать

m = max{m1,m2}. (19.2)

Предложение 19.1.Пусть Т*м(т) — сложность по числу бито­вых операций алгоритма сложения «столбиком» при использовании т в качестве размера входа. Тогда T*dd(m) = 6(m).

Доказательство. При фиксированном т мы можем выбрать а и Ъ
так, что тг = т2 = т, тогда тт{тът2} = max{m1,m2} = m; далее
применяем лемму 19.1. □

Алгоритм сложения «столбиком» позволяет получать сумму а и Ъ на месте максимального из этих двух чисел, в этом случае для би­товой пространственной сложности имеем S^d(m) = 0(l). Если для суммы чисел используется дополнительное место (чтобы не изменять данные слагаемые), то, соответственно, S^d(m) = m + 0(1).

Утверждения леммы 19.1 и предложения 19.1 верны, как легко убедиться, и для операции вычитания (при вычитании «столбиком» в старших разрядах занимается 0 или 1; битовая длина разности не превосходит т).

Формула T*dd(m) = в(т) говорит о том, что алгоритм сложения «столбиком» при рассмотрении т в качестве размера входа является оптимальным по порядку битовой сложности: мы не можем игнори­ровать содержимое разрядов, и поэтому т является нижней грани­цей битовой сложности алгоритмов сложения. Для алгоритмов умно­жения и деления «столбиком» в дальнейшем будет показано, что их



Глава 5. Битовая сложность


сложность имеет порядок т2, и в этой ситуации уже ниоткуда не следует, что не может существовать алгоритмов с лучшей асимпто­тикой сложности, и такие алгоритмы действительно существуют (мы об этом еще будем говорить). Поэтому умножение и деление «столби­ком» мы будем называть, как это делается в некоторых книгах, наив­ным умножением и делением соответственно, используя обозначения NM и ND (от английских слов naive multiplication/division —наивное умножение/деление). Сложение «столбиком» будем просто называть сложением.

Пример 19.1.Допустим, что для умножения двух целых положи­тельных чисел а и Ъ мы используем сложения:

а + а, (а + а)+а, ..., {а + ...+а)+а. (19.3)

Ь-1

Исследуем битовую сложность такого «сверхнаивного» умножения, считая т размером входа. В силу леммы 19.1 при тг = т2 = т на каждое сложение уйдет не менее т битовых операций. Учитывая, что Ъ > 2т-г, получаем для исследуемой сложности оценку П{2тт). С другой стороны, аЪ < 22т, поэтому результат каждого шага в (19.3) имеет не превосходящую битовую длину. Это означает, что чис­ло битовых операций на каждом из шагов не превосходит с • 2т, где с — константа. Отсюда получаем оценку 0(2mm), и в итоге — оценку 6(2mm).

Наряду с размером входа (19.2) часто рассматривают два парамет­ра тът2 размера входа.

Предложение 19.2.Если рассмотреть два параметра тг = А (а), m2 = A(b) размера входа, то битовая сложность Т**А(.тът2) алго­ритма сложения будет допускать оценку в(шах{т12}).

Доказательство. Пусть, например, max{m1,m2} = m1. Тогда оцен­
ка Т^Аъ т2) = Г2(шах{т1, т2}) подтверждается наличием входа а =
=
2mi - 1, Ъ = 2т? - 1. Оценка же Т**А(.тъ т2) = 0(max{m1, m2}) сле­
дует из леммы 19.1. □

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


§ 20. Наивная арифметика: умножение



в § 20 и 21, мы займемся битовой сложностью наивного умножения и деления.

Еще одно замечание в заключение этого параграфа. Битовый ана­лиз может учесть мельчайшие затраты, связанные с выполнением ал­горитма. Вопрос в том, нужен ли настолько детализированный под­ход, коль скоро компьютеры выполняют операции над основными структурами данных на уровне слов, длина же слова—это, как пра­вило, 64 бита. В связи с этим иногда вместо битовой рассматривается так называемая словесная сложность1. Но принципиальной разницы между битовой и словесной сложностью нет. Можно сказать так, что битовая сложность предполагает использование системы счисления с основанием 2, а словесная — с основанием 64. Анализ словесной сложности не является, в сравнении с анализом битовой сложности, ни более легким, ни более информативным.