10
правок
Изменения
Нет описания правки
вначале мы суммируем <tex>m^{(0)}</tex> и <tex>m^{(1)}</tex>, саму сумму занесем в <tex>u^{(1)}</tex>, а переносы в <tex>v^{(1)}</tex>(в <tex>u^{(1)}</tex> и <tex>v^{(1)}</tex> будет не более n+1 битов в каждом), затем суммируем числа <tex>u^{(1)}</tex>, <tex>v^{(1)}</tex>, <tex>m^{(2)}</tex> и получаем <tex>u^{(2)}</tex>, <tex>v^{(2)}</tex>. Так суммируется <tex>u^{(i-1)}</tex>, <tex>v^{(i-1)}</tex>, <tex>m^{(i)}</tex> для всех i = 2, 3, … , n – 1. В итоге получаем два числа <tex>u^{(n-1)}</tex> и <tex>v^{(i-1)}</tex>, которые складываем с помощью [[двоичный каскадный сумматор|двоичного каскадного сумматора]].
==Схемная сложность==
Частичные произведения вычисляются за ''n '' шагов, то есть имеют временную сложность O(n). Сложение с вычисление переносов включает ''n - 1 шагов и требует времени O(n)'' шаг. Последнее сложение можно выполнить за ''O(log n)''. <br>
В итоге суммарное время работы: <br>
''O(n) + O(n) + O(log n) = O(n) '' <br>Есть и более быстрые способы умножения двух чисел, например умножение с помощью [[дерево Уоллеса|дерева Уоллеса]], которое работает ''O(log n)''.
== Литература ==
* ''[http://ru.wikipedia.org/wiki/Кормен Кормен Т.], [http://ru.wikipedia.org/wiki/Лейзерсон,_Чарльз_Эрик Лейзерсон Ч.], [http://ru.wikipedia.org/wiki/Ривест,_Рональд_Линн Ривест Р.]''. Алгоритмы: построение и анализ = Introduction to Algorithms / Пер. с англ. под ред. А. Шеня. — М.: МЦНМО, 2000. — 960 с. — ISBN 5-900916-37-5
