Дерево Уоллеса

Определение

Дерево Уоллеса --- схема для умножения двух чисел.

Принцип работы

Дерево Уоллеса

Иллюстрация работы дерева для суммирования 9 чисел

В отличие от ещё одной схемы для умножения --- матричного умножителя, дерево Уоллеса складывает все числа не последовательно, а с помощью специального элемента(назовём его [math]3\to2[/math]), преобразующего 3 числа [math]x, y[/math] и [math] z [/math] в числа [math]a[/math] и [math]b[/math] такие, что [math]x + y + z = a + b[/math].

С помощью этого элемента на каждом шаге производятся следующие операции:

1. Берутся тройки чисел [math](x_1, x_2, x_3)[/math], [math](x_4, x_5, x_6)[/math], [math]\ldots[/math]. При этом какие-то числа могут остаться.
2. Для каждой тройки применяется элемент [math]3\to2[/math].
3. Повторяются пункты 1 и 2 пока не осталось 2 числа.
4. Оставшиеся 2 числа складываются с помощью двоичного каскадного сумматора.

На выходе имеем число, которое равно сумме чисел на всех входах.

Элемент 3→2

Элемент 3→2

Теперь о том, как устроен элемент [math]3\to2[/math].

Для построения элемента [math]3\to2[/math] нам потребуется элемент, который умеет складывать 3 бита и возвращать 2 бита результата. Основная идея реализации --- отдельная обработка переносов и остатков.

Тогда первое число ответа [math]a[/math] может быть получена так: [math]a_i = x_i \oplus y_i \oplus 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] дадут в сумме [math]x + y + z[/math]

Схемная сложность

Теперь подсчитаем схемную сложность этого элемента.

Каждый элемент [math]3\to2[/math] имеет глубину [math]O(1)[/math] и размер [math]O(n)[/math].

Теперь разберёмся, сколько в этой схеме элементов [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]. Тогда общая сложность равна

[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]