Изменения
math → tex
[[file:wallace_tree.png|thumb|200px|Иллюстрация работы дерева для суммирования 9 чисел]]
В отличие от ещё одной схемы для умножения --- [[Матричный умножитель|матричного умножителя]], дерево Уоллеса складывает все числа не последовательно, а с помощью специального элемента(назовём его <mathtex>3\to2</mathtex>), преобразующего 3 числа <mathtex>x, 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 пока не осталось 2 числа.
# Оставшиеся 2 числа складываются с помощью [[Двоичный каскадный сумматор|двоичного каскадного сумматора]].
===Элемент 3→2===
[[file:3→2.png|thumb|200px|Элемент 3→2]]
Теперь о том, как устроен элемент <mathtex>3\to2</mathtex>.
Для построения элемента <mathtex>3\to2</mathtex> нам потребуется элемент, который умеет складывать 3 бита и возвращать 2 бита результата.
Основная идея реализации - отдельная обработка переносов и остатков.
Тогда первое число ответа <mathtex>a</mathtex> может быть получена так:<mathtex>a_i = x_i \oplus y_i \oplus z_i</mathtex> ,где <mathtex>x</mathtex>, <mathtex>y</mathtex> и <mathtex>z</mathtex> - входные числа, а <mathtex>x_i</mathtex>, <mathtex>y_i</mathtex> и <mathtex>z_i</mathtex> - соответствующие их <mathtex>i</mathtex>-е биты.
Второе же число <mathtex>b</mathtex> можно получить так:<mathtex> \begin{cases}
b_0 & = 0\\
b_{i + 1} & = \langle x_i, y_i, z_i \rangle
\end{cases}</mathtex> ,где <mathtex>\langle x, y, z\rangle</mathtex> - функция медианы(она же "голосование 2 из 3"). С помощью этой функции считается перенос.
Очевидно, полученные числа <mathtex>a</mathtex> и <mathtex>b</mathtex> дадут в сумме <mathtex>x + y + z</mathtex>
==Схемная сложность==
Определим схемную сложность этого элемента.
Каждый элемент <mathtex>3\to2</mathtex> имеет глубину <mathtex>O(1)</mathtex> и размер <mathtex>O(n)</mathtex>.
Подсчитаем количество элементов <mathtex>3\to2</mathtex>. На каждом шаге количество чисел, которые нужно просуммировать, уменьшается в <mathtex>1,{}5</mathtex> раза. Тогда глубина дерева будет равна <mathtex>\log_{3/2}n</mathtex>, и в нём будет <mathtex>n + \frac23n + \left(\frac23\right)^2n + \ldots = O(n)</mathtex> элементов <mathtex>3\to2</mathtex>.
Тогда общая сложность равна
<mathtex>depth = depth_{3\to2} \cdot \log_{3/2}n + depth_{sum} = O(\log n)</mathtex>
<mathtex>size = size_{3\to2} \cdot O(n) + size_{sum} = O(n^2) </mathtex>
