Дерево Уоллеса — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Схемная сложность)
(Схемная сложность)
Строка 40: Строка 40:
 
==Схемная сложность==
 
==Схемная сложность==
  
Теперь подсчитаем схемную сложность этого элемента.
+
Найдём схемную сложность этого элемента.
  
 
Каждый элемент <math>3\to2</math> имеет глубину <math>O(1)</math> и размер <math>O(n)</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>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>.
 
Тогда общая сложность равна
 
Тогда общая сложность равна
  

Версия 19:43, 13 октября 2010

Определение

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

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

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

Иллюстрация работы дерева для суммирования 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]