Верещагин Н.К., Шень А. - Языки и исчисления, страница 7

Существует схема умножения двух n-разрядных чисел размера O(n2 ) и глубины O(log n). Как мы уже говорили, умножение двух n-разрядных чисел сводится к сложению n таких чисел, и остаётся выполнить такое сложе-[п. 3]Схемы из функциональных элементов31ние схемой размера O(n2 ) и глубины O(log n). Ключевым моментомздесь является сведение сложения трёх чисел к сложению двух с помощью простой схемы размера O(n) и глубины O(1).

В самом деле,пусть есть три числа x, y и z. Если мы будем складывать отдельно вкаждом разряде, то в разряде может накопиться любая сумма от 0до 3, то есть в двоичной записи от 00 до 11. Сформируем из младших битов этих двухбитовых сумм число u, а из старших (сдвинутыхвлево) — число v. Тогда, очевидно, x + y + z = u + v. Получение цифрчисла u и v происходит параллельно во всех разрядах и требует размера O(n) и глубины O(1).Теперь, если надо сложить n чисел, можно разбить их на тройки и из каждых трёх чисел получить по два. В следующий круг,таким образом, выйдут (2/3)n чисел (примерно — граничные эффекты большой роли не играют). Их снова можно сгруппировать потройкам и т.

д. С каждым уровнем число слагаемых убывает в полтора раза, так что глубина схемы будет логарифмической. Каждоепреобразование трёх слагаемых в два требует схемы размера O(n)и уменьшает число слагаемых на единицу, так что потребуется nтаких преобразований. Итак, эта конструкция имеет общий размерO(n2 ) и глубину O(log n).

Надо только отметить, что в конце у насполучается не одно число, а два, и их напоследок надо сложить —что мы умеем делать с глубиной O(log n) и размером O(n). 15. Докажите, что схема, вычисляющая булеву функцию f от n аргументов, у которой ни один аргумент не является фиктивным, имеет размерне менее cn и глубину не менее c log n, где c > 0 — некоторая константа, зависящая от выбранного набора элементов. (Аргумент функции называютфиктивным, если от него значение функции не зависит.)Эта задача показывает, что если по ходу умножения двух n-разрядных чисел мы суммируем n слагаемых размера n, то оценкиO(n2 ) для размера и O(log n) для глубины, полученные при доказательстве теоремы 12, существенно улучшить нельзя.Однако никто не обязывает нас следовать традиционному способу умножения столбиком — отказавшись от него, мы можем уменьшить размер схемы.Теорема 13.

Существует схема умножения двух n-разрядных чисел размера O(nlog2 3 ) и глубины O(log2 n). Начнём с такого замечания. Вычисляя произведение двух комплексных чисел(a + bi)(c + di) = (ac − bd) + (ad + bc)i32Логика высказываний[гл. 1]обычным способом, мы делаем четыре умножения. Но можно обойтись и тремя с помощью трюка: вычислить ac, bd и (a + b)(c + d), апотом найти ad + bc как разность (a + b)(c + d) − ac − bd.Аналогичный фокус можно проделать и для целых чисел. Разобьём 2n-битовое число на две n-битовые части, то есть представимего в виде a2n + b. Теперь запишем произведение двух таких чисел:(a2n + b)(c2n + d) = ac22n + (ad + bc)2n + bd.Теперь видно, что достаточно найти три произведения, а именно, ac,bd и (a + b)(c + d), чтобы определить все три слагаемых в правой части равенства.

Получается, что умножение двух 2n-разрядных чиселсводится к трём умножениям n-разрядных и к нескольким сложениям и вычитаниям. (На самом деле при умножении (a + b) на (c + d)сомножители могут быть (n+1)-разрядными, но это не страшно, таккак обработка лишнего разряда сводится к нескольким сложениям.)Для размера схемы это даёт рекурсивную оценкуS(2n) 6 3S(n) + O(n),из которой следует, что S(n) = O(nlog2 3 ).

В самом деле, для умножения n-разрядных чисел требуется дерево рекурсивных вызововглубины log2 n и степени ветвления 3. Заметим, что размер схемы ввершине пропорционален числу складываемых битов. При переходеот одного уровня к следующему (более близкому к корню) размерслагаемых растёт вдвое, а число вершин уменьшается втрое, поэтому общее число элементов на этом уровне уменьшается в полторараза. Таким образом, при движении по уровням от листьев к корнюполучается убывающая геометрическая прогрессия со знаменателем2/3, сумма которой всего лишь втрое превосходит её первый член.Остаётся заметить, что число листьев равно 3log2 n = nlog2 3 .Оценка глубины также очевидна: на каждом уровне мы имеемсхему сложения глубины O(log n), а число уровней есть O(log n).

На этом мы завершаем знакомство со схемами из функциональных элементов, выполняющими арифметические операции. О нихможно прочесть в главе 29 учебника Кормена, Лейзерсона и Ривеста [18] и в книге Ахо, Хопкрофта и Ульмана [1].Рассмотрим теперь функцию «голосования» (majority). Она имеет нечётное число аргументов, и значение её равно 0 или 1 в зависимости от того, какое из двух значений чаще встречается средивходов.[п. 3]Схемы из функциональных элементов33Теорема 14. Для функции голосования существует схема размераO(n) и глубины O(log n log log n).

На самом деле можно даже вычислить общее число единиц среди входов. Это делается рекурсивно: считаем отдельно для каждойполовины, потом складываем. Получается логарифмическое числоуровней. На верхнем уровне надо складывать числа размера log n,на следующем — размера (log n − 1) и так до самого низа, где складываются однобитовые числа (то есть биты входа). Какой среднийразмер складываемых чисел? Половина вершин в дереве приходится на нижний уровень (числа длины 1), четверть— на следующийP(числа длины 2) и т. д. Вспоминая, что ряд (k/2k ) сходится, видим,что средний размер складываемых чисел есть O(1) и общий размерсхемы есть O(n).

А общая глубина есть O(log n log log n), так как накаждом из log n уровней стоит схема глубины O(log log n). Заметим, что хотя функция голосования монотонна, построеннаясхема её вычисления содержит немонотонные элементы (посколькуоперация сложения не монотонна). Мы уже говорили, что всякуюмонотонную функцию можно составить из конъюнкций и дизъюнкций. Для функции голосования есть очевидный способ это сделать:написать дизъюнкцию всех конъюнкций размера (n + 1)/2 (напомним, что число входов n предполагается нечётным).

Однако при этомполучится схема экспоненциального по n размера.Теорема 15. Существует схема размера O(nc ) и глубины O(log n),составленная только из элементов И и ИЛИ (с двумя входами), вычисляющая функцию голосования. Для начала заметим, что ограничение на размер является следствием ограничения на глубину, так как элементы И и ИЛИ имеюттолько два входа и число элементов в схеме глубины d есть O(2d ).Схема будет строиться из элементов большинства с тремя входами. (Каждый из них можно собрать из конъюнкций и дизъюнкцийпо формуле (a ∧ b) ∨ (a ∧ c) ∨ (b ∧ c).) Выход схемы будет большинством из трёх значений, каждое из которых есть большинство изтрёх значений и т.

д. (рис. 3).Продолжая эту конструкцию на k уровнях, мы получим схему с3k входами. (Отметим, что эта схема не будет вычислять большинство среди своих входов — по той же причине, по которой результатнепрямого голосования может отличаться от мнения большинства.)Но мы сделаем вот какую странную вещь: возьмём k равным c log nпри достаточно большом коэффициенте пропорциональности c (число входов такой схемы будет полиномиально зависеть от n) и напи-34Логика высказываний............[гл. 1]......Рис. 3. Дерево из элементов 3-большинства.шем на входах случайно выбранные переменные из данного нам набора x1 , .

. . , xn . (Переменные, записываемые на разных входах, выбираются независимо.) Оказывается, что с ненулевой вероятностьюэта схема будет вычислять функцию большинства среди x1 , . . . , xn ,если константа c достаточно велика. Следовательно, искомая схемасуществует.Обратите внимание: нам удастся доказать существование интересующей нас схемы, не предъявив её явно. (Такое использованиевероятностных методов в комбинаторных рассуждениях часто бывает полезно.)Итак, почему же схема с положительной вероятностью вычисляетфункцию большинства? Это доказывается так: рассмотрим какой-тоодин набор значений на входах и докажем, что на этом конкретномнаборе случайная схема выдаёт правильный ответ с вероятностью,очень близкой к единице (равной 1 − ε при очень малом ε).Если число ε настолько мало, что остаётся меньшим единицыдаже после умножения на число возможных входов (2n ), то получаемтребуемое (каждое из 2n событий имеет вероятность не меньше 1−ε,значит их пересечение имеет вероятность не меньше 1 − 2n ε > 0).Итак, осталось оценить вероятность того, что случайная схемадаст правильный ответ на данном входе.

Пусть доля единиц средивсех входов равна p. Тогда на каждый входной провод схемы подаётся единица с вероятностью p и нуль с вероятностью 1 − p (выборслучайной переменной даёт единицу с вероятностью p), причём сигналы на всех входах независимы.Если на трёх входах элемента 3-большинства сигналы независимы, и вероятность появления единицы на каждом входе есть p, то вероятность появления единицы на выходе есть ϕ(p) = 3p2 (1−p)+p3 == 3p2 − 2p3 . На следующих уровнях вероятность появления единицыбудет равна ϕ(ϕ(p)), ϕ(ϕ(ϕ(p))), . .