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

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

Версия 23:59, 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,{}5[/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]

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Дерево_Уоллеса&oldid=3884»