Изменения

==Определение== '''Дерево Уоллеса ''' (англ. ''Wallace tree'') {{- --}} [[Реализация булевой функции схемой из функциональных элементов|схема ]] для умножения двух чисел. Время работы <tex>O(\log n)</tex>.

В Для получения произведения, воспользуемся методом, напоминающим умножение «в столбик»: распишем произведение в сумму <tex>n</tex> чисел (как в [[Матричный умножитель|матричном умножителе]]). Однако, в отличие от ещё одной схемы для умножения --- [[Матричный умножитель|матричного умножителя]], дерево Уоллеса складывает все числа не последовательно, а с помощью специального элемента(назовём его <mathtex>3\to2</mathtex>), преобразующего <tex>3 </tex> числа <mathtex>x</tex>, <tex>y</mathtex> и <mathtex> z </mathtex> в числа <mathtex>a</mathtex> и <mathtex>b</mathtex> такие, что <mathtex>x + y + z = a + b</mathtex>.

# Берутся тройки чисел <mathtex>(x_1, x_2, x_3)</mathtex>, <mathtex>(x_4, x_5, x_6)</mathtex>, <mathtex>\ldots</mathtex>. При этом какие-то числа могут остаться.# Для каждой тройки применяется элемент <mathtex>3\to2</mathtex>.# Повторяются пункты 1 и 2 пока не осталось <tex>2 </tex> числа.# Оставшиеся <tex>2 </tex> числа складываются с помощью [[Двоичный каскадный сумматор|двоичного каскадного сумматора]].

[[file:3→23v2.png|thumb|200px300px|Элемент 3→2]]Теперь о томДля того, как устроен элемент чтобы представить сумму трёх чисел с помощью двух чисел, воспользуемся полным сумматором. Для каждого <mathtex>3\to2i</mathtex>. Для построения элемента направим <mathtex>3\to2x_i</mathtex> нам потребуется элемент, который умеет складывать 3 бита <tex>y_i</tex> и возвращать 2 бита результата<tex>z_i</tex> на вход полного сумматора.Основная идея реализации Тогда младший бит сумматора будет <tex>i</tex>-ым битом первого числа, а старший {{---}} <tex>(i + 1)</tex>- отдельная обработка переносов и остатковым второго.

Тогда первое число ответа <math>a</math> может быть получена так:<math>a_i = x_i \oplus y_i \oplus z_i</math> Очевидно,где полученные числа в сумме дают <mathtex>x</math>, <math>+ y</math> и <math>+ z</math> --- входные числа, а <math>x_i</math>, <math>y_i</math> и <math>z_i</math> --- соответствующие их <math>i</mathtex>-е биты.

Второе же число На иллюстрации изображён элемент <mathtex>b</math> можно получить так:<math> \begin{cases}b_0 & = 0\\b_{i + 1} & = \langle x_i, y_i, z_i 3\rangle\end{cases}to2</math> ,где <mathtex>\langle xдля четырёхбитных чисел, yв верхнем прямоугольнике изображены четыре полных сумматора, z\rangle</math> --- функция медианы(она же "голосование 2 из 3"). С помощью этой функции считается переносвыходы которых и являются разрядами результатов.

ОчевидноПоскольку все полные сумматоры работают параллельно (выходы на каждом из них зависят только от собственных входов), полученные числа <math>a</math> и <math>b</math> дадут в сумме <math>x + y + z</math>то глубина такой схемы есть константа (не зависит от количества бит).

Найдём схемную сложность этого элементаОпределим количество элементов и глубину схемы для умножения двух чисел из <tex>n</tex> бит.

Каждый элемент <mathtex>3\to2</mathtex> имеет глубину <mathtex>O(1)</mathtex> и размер <mathtex>O(n)</mathtex>.

Подсчитаем количество элементов <mathtex>3\to2</mathtex>. На каждом шаге количество чисел, которые нужно просуммировать, уменьшается на <math>1/3</math>в полтора раза. Тогда глубина дерева будет равна <mathtex>\log_{\frac{3/}{2}}n</mathtex>, и в нём будет <mathtex>n + \frac23n dfrac{2}{3} n + \left(\frac23dfrac{2}{3}\right)^2n + \ldots = O(n)</mathtex> элементов <tex>3\to2</tex>. Обозначим за <tex>size</tex> общее количество элементов в цепи; за <tex>size_{3\to2}</tex> количество элементов <mathtex>3\to2</mathtex>; за <tex>size_{sum}</tex> количество элементов двоичного каскадного сумматора в схеме; за <tex>depth</tex> глубину схемы; за <tex>depth_{3\to2}</tex> глубину каждого из элементов <tex>3\to2</tex>; за <tex>depth_{sum}</tex> глубину каждого из элементов двоичного каскадного сумматора.

<mathtex>depth = depth_{3\to2} \cdot \log_{3/2}n + depth_{sum} = O(\log n)</mathtex> <tex>size = size_{3\to2} \cdot O(n) + size_{sum} = O(n^2) </tex> == См. также ==* [[Матричный умножитель]]* [[Сумматор]]* [[Каскадный сумматор]]* [[Двоичный каскадный сумматор]] == Источники информации== * Кормен, Т., Лейзерсон, Ч., Ривест, Р. Алгоритмы: построение и анализ — 960 с. — ISBN 5-900916-37-5 [[Категория: Дискретная математика и алгоритмы]]