403
правки
Изменения
Новая страница: «==Это что?== Дерево Уоллеса --- схема для умножения двух чисел. ==Как оно работает(макро)?== В …»
==Это что?==
Дерево Уоллеса --- схема для умножения двух чисел.
==Как оно работает(макро)?==
В отличие от ещё одной схемы для умножения --- [[Матричный умножитель|матричного умножителя]], дерево Уоллеса не складывает все числа последовательно, а с помощью специального элемента(назовём его <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>(x_1, x_2, x_3)</math>, <math>(x_4, x_5, x_6)</math> <math>\ldots</math>. При этом какие-то числа могут остаться.
# Для каждой тройки применяется элемент <math>3\to2</math>.
# Повторять пункты 1 и 2 пока не осталось 2 числа.
# Оставшиеся 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<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>
Дерево Уоллеса --- схема для умножения двух чисел.
==Как оно работает(макро)?==
В отличие от ещё одной схемы для умножения --- [[Матричный умножитель|матричного умножителя]], дерево Уоллеса не складывает все числа последовательно, а с помощью специального элемента(назовём его <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>(x_1, x_2, x_3)</math>, <math>(x_4, x_5, x_6)</math> <math>\ldots</math>. При этом какие-то числа могут остаться.
# Для каждой тройки применяется элемент <math>3\to2</math>.
# Повторять пункты 1 и 2 пока не осталось 2 числа.
# Оставшиеся 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<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>
