35
правок
Изменения
Нет описания правки
'''Дерево Уоллеса''' (англ. ''Wallace tree'') {{---}} [[Реализация булевой функции схемой из функциональных элементов|схема]] для умножения двух чисел. Время работы <tex>O(\log n)</tex>.
==Принцип работы==
===Элемент 3→2===
[[file:3→2.png|thumb|200px300px|Элемент 3→2]]
Для того, чтобы представить сумму трёх чисел с помощью двух чисел, воспользуемся полным сумматором. Для каждого <tex>i</tex> направим <tex>x_i</tex>, <tex>y_i</tex> и <tex>z_i</tex> на вход полного сумматора. Тогда младший бит сумматора будет <tex>i</tex>-ым битом первого числа, а старший {{---}} <tex>(i + 1)</tex>-ым второго.
