Изменения
Нет описания правки
<tex>O(n) + O(n) + O(\log n) = O(n) </tex> <br>
Конкретно по нашей схеме: <br>
Скорость работы схемы, приведенной на схеме определяется максимальным временем распространения сигнала. Это цепь <tex>D7, D6, D4, D2</tex>. <br>Время работы схемы можно сократить, если сумматоры располагать не последовательно друг за другом, как это предполагается алгоритмом, приведенным на первом рисунке (общая схема), а суммировать частичные произведения попарно, затем суммировать пары частичных произведений и т.д. В этом случае время выполнения операции умножения значительно сократится. <br>Особенно заметен выигрыш в быстродействии при построении многоразрядных умножителей, однако ничего не бывает бесплатно. В обмен на быстродействие придётся заплатить увеличением разрядности сумматоров, а значит сложностью схемы. <br>Если сумматоры частных произведений останутся той же разрядности, что и ранее, то разрядность сумматоров пар частичных произведений должна быть увеличена на единицу. <br>Разрядность сумматоров четвёрок частичных произведений будет на два разряда больше разрядности сумматоров частичных произведений и т.д. <br>
Есть и более быстрые способы умножения двух чисел, например умножение с помощью [[дерево Уоллеса|дерева Уоллеса]], которое работает <tex>O(\log n)</tex>.
