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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение)
(Элемент 3→2)
Строка 23: Строка 23:
  
 
Для построения элемента <math>3\to2</math> нам потребуется элемент, который умеет складывать 3 бита и возвращать 2 бита результата.
 
Для построения элемента <math>3\to2</math> нам потребуется элемент, который умеет складывать 3 бита и возвращать 2 бита результата.
Основная идея реализации --- отдельная обработка переносов и остатков.
+
Основная идея реализации - отдельная обработка переносов и остатков.
  
 
Тогда первое число ответа <math>a</math> может быть получена так:
 
Тогда первое число ответа <math>a</math> может быть получена так:
 
<math>a_i = x_i \oplus y_i \oplus z_i</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>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>b</math> можно получить так:
Строка 34: Строка 34:
 
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}</math> ,
где <math>\langle x, y, z\rangle</math> --- функция медианы(она же "голосование 2 из 3"). С помощью этой функции считается перенос.
+
где <math>\langle x, y, z\rangle</math> - функция медианы(она же "голосование 2 из 3"). С помощью этой функции считается перенос.
  
 
Очевидно, полученные числа <math>a</math> и <math>b</math> дадут в сумме <math>x + y + z</math>
 
Очевидно, полученные числа <math>a</math> и <math>b</math> дадут в сумме <math>x + y + z</math>

Версия 20:18, 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]