==Это что?== '''Дерево Уоллеса ''' (англ. ''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:3→23v2.png|thumb|200px300px|Элемент 3→2]]Теперь о томДля того, чтобы представить сумму трёх чисел с помощью двух чисел, воспользуемся полным сумматором. Для каждого <tex>i</tex> направим <tex>x_i</tex>, как устроен элемент <mathtex>3\to2y_i</tex> и <tex>z_i</tex> на вход полного сумматора. Тогда младший бит сумматора будет <tex>i</tex>-ым битом первого числа, а старший {{---}} <tex>(i + 1)</mathtex>-ым второго.
Для построения элемента Очевидно, полученные числа в сумме дают <mathtex>3\to2x + y + z</mathtex> нам потребуется элемент, который умеет складывать 3 бита и возвращать 2 бита результата.Основная идея реализации --- отдельная обработка переносов и остатков.
Тогда первое число ответа На иллюстрации изображён элемент <mathtex>a</math> может быть получена так:<math>a_i = x_i 3\vee y_i \vee z_i</math> ,где <math>x</math>, <math>y</math> и <math>zto2</mathtex> --- входные числадля четырёхбитных чисел, а <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> дадут в сумме <math>x + y + z</math>==Схемная сложность==
==А чем оно лучше матричного умножителя?==Определим количество элементов и глубину схемы для умножения двух чисел из <tex>n</tex> бит.
Теперь подсчитаем схемную сложность этого элементаКаждый элемент <tex>3\to2</tex> имеет глубину <tex>O(1)</tex> и размер <tex>O(n)</tex>.
Каждый элемент Подсчитаем количество элементов <mathtex>3\to2</mathtex> имеет глубину . На каждом шаге количество чисел, которые нужно просуммировать, уменьшается в полтора раза. Тогда глубина дерева будет равна <mathtex>O(1)\log_{\frac{3}{2}}n</mathtex> , и размер в нём будет <mathtex>n + \dfrac{2}{3} n + \left(\dfrac{2}{3}\right)^2n + \ldots = O(n)</mathtex>элементов <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</math>. На каждом шаге количество чисел, которые нужно просуммировать, уменьшается на <math>1/3</math>. Тогда глубина дерева будет равна <math>} \cdot \log_{3/2}n+ depth_{sum} = O(\log n)<math/tex>, и в нём будет <mathtex>n + size = size_{3\frac23n + to2} \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>[[Категория: Схемы из функциональных элементов ]]
