Дерево Уоллеса — различия между версиями
(→Определение) |
(→Элемент 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</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> | + | где <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
Определение
Дерево Уоллеса - схема для умножения двух чисел.
Принцип работы
Дерево Уоллеса
В отличие от ещё одной схемы для умножения --- матричного умножителя, дерево Уоллеса складывает все числа не последовательно, а с помощью специального элемента(назовём его ), преобразующего 3 числа и в числа и такие, что .
С помощью этого элемента на каждом шаге производятся следующие операции:
- Берутся тройки чисел , , . При этом какие-то числа могут остаться.
- Для каждой тройки применяется элемент .
- Повторяются пункты 1 и 2 пока не осталось 2 числа.
- Оставшиеся 2 числа складываются с помощью двоичного каскадного сумматора.
На выходе имеем число, которое равно сумме чисел на всех входах.
Элемент 3→2
Теперь о том, как устроен элемент .
Для построения элемента нам потребуется элемент, который умеет складывать 3 бита и возвращать 2 бита результата. Основная идея реализации - отдельная обработка переносов и остатков.
Тогда первое число ответа может быть получена так: , где , и - входные числа, а , и - соответствующие их -е биты.
Второе же число можно получить так: , где - функция медианы(она же "голосование 2 из 3"). С помощью этой функции считается перенос.
Очевидно, полученные числа и дадут в сумме
Схемная сложность
Найдём схемную сложность этого элемента.
Каждый элемент имеет глубину и размер .
Подсчитаем количество элементов . На каждом шаге количество чисел, которые нужно просуммировать, уменьшается на . Тогда глубина дерева будет равна , и в нём будет элементов . Тогда общая сложность равна
