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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Добавлен рисунок)
(Добавлен рисунок)
Строка 5: Строка 5:
  
 
==Как оно работает(макро)?==
 
==Как оно работает(макро)?==
 +
 +
[[file:wallace_tree.png|thumb|200px|Оно самое]]
  
 
В отличие от ещё одной схемы для умножения --- [[Матричный умножитель|матричного умножителя]], дерево Уоллеса не складывает все числа последовательно, а с помощью специального элемента(назовём его <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>.
 
В отличие от ещё одной схемы для умножения --- [[Матричный умножитель|матричного умножителя]], дерево Уоллеса не складывает все числа последовательно, а с помощью специального элемента(назовём его <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>.
Строка 15: Строка 17:
  
 
На выходе имеем число, которое равно сумме чисел на всех входах.
 
На выходе имеем число, которое равно сумме чисел на всех входах.
 
  
 
==Как оно работает(микро)?==
 
==Как оно работает(микро)?==

Версия 07:42, 11 октября 2010

Это что?

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


Как оно работает(макро)?

Оно самое

В отличие от ещё одной схемы для умножения --- матричного умножителя, дерево Уоллеса не складывает все числа последовательно, а с помощью специального элемента(назовём его [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

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

Для построения элемента [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] , где [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\lt math\gt , и в нём будет \lt math\gt 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]