Изменения

==Как оно работаетДля получения произведения, воспользуемся методом, напоминающим умножение «в столбик»: распишем произведение в сумму <tex>n</tex> чисел (макрокак в [[Матричный умножитель|матричном умножителе]])?==.

[[file:wallace_tree.png|thumb|200px|Оно самое]] В Однако, в отличие от ещё одной схемы для умножения --- [[Матричный умножитель|матричного умножителя]], дерево Уоллеса не складывает все числа не последовательно, а с помощью специального элемента(назовём его <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>, <tex>y_i</tex> и <tex>z_i</tex> на вход полного сумматора. Тогда младший бит сумматора будет <tex>i</tex>-ым битом первого числа, а старший {{---}} <tex>(i + 1)</tex>-ым второго.  Очевидно, как устроен полученные числа в сумме дают <tex>x + y + z</tex>. На иллюстрации изображён элемент <mathtex>3\to2</mathtex>для четырёхбитных чисел, в верхнем прямоугольнике изображены четыре полных сумматора, выходы которых и являются разрядами результатов.

Для построения элемента <math>3\to2</math> нам потребуется элементПоскольку все полные сумматоры работают параллельно (выходы на каждом из них зависят только от собственных входов), который умеет складывать 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> ,где Определим количество элементов и глубину схемы для умножения двух чисел из <mathtex>\langle x, y, z\ranglen</mathtex> --- функция медианы(она же "голосование 2 из 3"). С помощью этой функции считается переносбит.

Очевидно, полученные числа Каждый элемент <mathtex>a3\to2</mathtex> и имеет глубину <mathtex>bO(1)</mathtex> дадут в сумме и размер <mathtex>x + y + zO(n)</mathtex>.

Подсчитаем количество элементов <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>size = size_{3\to2</math> имеет глубину <math>} \cdot O(1n)</math> и размер <math>+ size_{sum} = O(n^2)</mathtex>.

Теперь разберёмся== См. также ==* [[Матричный умножитель]]* [[Сумматор]]* [[Каскадный сумматор]]* [[Двоичный каскадный сумматор]] == Источники информации== * Кормен, сколько в этой схеме элементов <math>3\to2</math>Т. На каждом шаге количество чисел, которые нужно просуммироватьЛейзерсон, уменьшается на <math>1/3</math>Ч. Тогда глубина дерева будет равна <math>\log_{3/2}n<math>, Ривест, Р. Алгоритмы: построение и в нём будет <math>n + \frac23n + \left(\frac23\right)^2n + \ldots = O(n)</math> элементов <math>3\to2</math>анализ — 960 с.Тогда общая сложность равна— ISBN 5-900916-37-5