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

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

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

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

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

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

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

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

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

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

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

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

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

тт{т_ъ т₂} s= С^Т_ш(а, Ъ) s= c (max{ m _lJ m₂} + 1), (19.1)

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

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

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

m = max{ m ₁, m ₂}. (19.2)

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

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

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

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

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

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

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

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

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

Ь-1

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

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

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

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

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

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

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

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

Дата добавления: 2014-01-11