==Это что?=='''Дерево Уоллеса''' (англ. ''Wallace tree'') {{---}} [[Реализация булевой функции схемой из функциональных элементов|схема]] для умножения двух чисел. Время работы <tex>O(\log n)</tex>.
Дерево Уоллеса --- схема для умножения двух чисел.==Принцип работы==
===Дерево Уоллеса===
[[file:wallace_tree.png|thumb|200px|Иллюстрация работы дерева для суммирования 9 чисел]]
==Как оно работаетДля получения произведения, воспользуемся методом, напоминающим умножение «в столбик»: распишем произведение в сумму <tex>n</tex> чисел (макрокак в [[Матричный умножитель|матричном умножителе]])?==.
В Однако, в отличие от ещё одной схемы для умножения --- [[Матричный умножитель|матричного умножителя]], дерево Уоллеса не складывает все числа не последовательно, а с помощью специального элемента(назовём его <mathtex>3\to2</mathtex>) преобразует , преобразующего <tex>3 </tex> числа <mathtex>x</tex>, <tex>y</mathtex> и <mathtex> z </mathtex> в числа <mathtex>a</mathtex> и <mathtex>b</mathtex> такие, что <mathtex>x + y + z = a + b</mathtex>.
С помощью этого элемента на каждом шаге производятся следующие операции:
# Берутся тройки чисел <mathtex>(x_1, x_2, x_3)</mathtex>, <mathtex>(x_4, x_5, x_6)</mathtex> , <mathtex>\ldots</mathtex>. При этом какие-то числа могут остаться.# Для каждой тройки применяется элемент <mathtex>3\to2</mathtex>.# Повторять Повторяются пункты 1 и 2 пока не осталось <tex>2 </tex> числа.# Оставшиеся <tex>2 </tex> числа складываются с помощью [[Двоичный каскадный сумматор|двоичного каскадного сумматора]].
На выходе имеем число, которое равно сумме чисел на всех входах.
===Элемент 3→2===
[[file:3v2.png|thumb|300px|Элемент 3→2]]
Для того, чтобы представить сумму трёх чисел с помощью двух чисел, воспользуемся полным сумматором. Для каждого <tex>i</tex> направим <tex>x_i</tex>, <tex>y_i</tex> и <tex>z_i</tex> на вход полного сумматора. Тогда младший бит сумматора будет <tex>i</tex>-ым битом первого числа, а старший {{---}} <tex>(i + 1)</tex>-ым второго.
==Как оно работает(микро)?==[[file:3→2.png|thumb|200px|Элемент 3→2]]Теперь о томОчевидно, как устроен элемент полученные числа в сумме дают <mathtex>3\to2x + y + z</mathtex>.
Для построения элемента На иллюстрации изображён элемент <mathtex>3\to2</mathtex> нам потребуется элементдля четырёхбитных чисел, в верхнем прямоугольнике изображены четыре полных сумматора, который умеет складывать 3 бита и возвращать 2 бита результата.Основная идея реализации --- отдельная обработка переносов выходы которых и остатковявляются разрядами результатов.
Тогда первое число ответа <math>a</math> может быть получена так:<math>a_i = x_i \vee y_i \vee z_i</math> Поскольку все полные сумматоры работают параллельно (выходы на каждом из них зависят только от собственных входов),где <math>x</math>, <math>y</math> и <math>z</math> --- входные числа, а <math>x_i</math>, <math>y_i</math> и <math>z_i</math> --- соответствующие их <math>i</math>-е битыто глубина такой схемы есть константа (не зависит от количества бит).
Второе же число <math>b</math> можно получить так:<math> \begin{cases}b_0 & = 0\\b_{i + 1} & = \langle x_i, y_i, z_i \rangle\end{cases}</math> ,где <math>\langle x, y, z\rangle</math> --- функция медианы(она же "голосование 2 из 3"). С помощью этой функции считается перенос.Схемная сложность==
Очевидно, полученные числа <math>a</math> Определим количество элементов и глубину схемы для умножения двух чисел из <math>b</math> дадут в сумме <mathtex>x + y + zn</mathtex>бит.
==А чем оно лучше матричного умножителя?==Каждый элемент <tex>3\to2</tex> имеет глубину <tex>O(1)</tex> и размер <tex>O(n)</tex>.
Теперь подсчитаем схемную Подсчитаем количество элементов <tex>3\to2</tex>. На каждом шаге количество чисел, которые нужно просуммировать, уменьшается в полтора раза. Тогда глубина дерева будет равна <tex>\log_{\frac{3}{2}}n</tex>, и в нём будет <tex> n + \dfrac{2}{3} n + \left(\dfrac{2}{3}\right)^2n + \ldots = O(n)</tex> элементов <tex>3\to2</tex>. Обозначим за <tex>size</tex> общее количество элементов в цепи; за <tex>size_{3\to2}</tex> количество элементов <tex>3\to2</tex>; за <tex>size_{sum}</tex> количество элементов двоичного каскадного сумматора в схеме; за <tex>depth</tex> глубину схемы; за <tex>depth_{3\to2}</tex> глубину каждого из элементов <tex>3\to2</tex>; за <tex>depth_{sum}</tex> глубину каждого из элементов двоичного каскадного сумматора.Тогда общая сложность этого элемента.равна
Каждый элемент <mathtex>depth = depth_{3\to2<} \cdot \log_{3/math> имеет глубину <math>O(1)</math> и размер <math>2}n + depth_{sum} = O(\log n)</mathtex>.
Теперь разберёмся, сколько в этой схеме элементов <mathtex>size = size_{3\to2</math>. На каждом шаге количество чисел, которые нужно просуммировать, уменьшается на <math>1/3</math>. Тогда глубина дерева будет равна <math>\log_{3/2}n<math>, и в нём будет <math>n + \frac23n + \leftcdot O(\frac23\rightn)^2n + \ldots size_{sum} = O(n^2)</math> элементов <math>3\to2</mathtex> == См.также ==* [[Матричный умножитель]]* [[Сумматор]]* [[Каскадный сумматор]]* [[Двоичный каскадный сумматор]] == Источники информации== Тогда общая сложность равна* Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ — 960 с. — ISBN 5-900916-37-5
<math>depth = depth_{3\to2} \cdot \log_{3/2}n + depth_{sum} = O(\log n)</math>[[Категория: Дискретная математика и алгоритмы]]
<math>size = size_{3\to2} \cdot O(n) + size_{sum} = O(n^2) </math>[[Категория: Схемы из функциональных элементов ]]
