lekcii2 (Лекции), страница 11

Еще одна полезная машина, %ьв ([(Л)Л) ~ [Л00...0(Л)Л)). Пустые ячейки берутся ь справа на свободном краю ленты: Ч'ь,о (г0) г Сооственно реализация машины умножения: П 1~2 уу'л,оЬ Использованная в машине умножения машина ЛЛ~Я1пг1Ь сдвигает (фактически, копирует) слово слева от головки МТ в предыдущее слово ([Лш~Ли,'а(Л)Л) => [ЛшаЛиа(Л)Л)): в 1ь '0 КЗЫЬ„. 1 Г" В. 1ь' '1 Таким образом, умножение двоичных чисел разбивается на более простые алдитивные стадии. Сначала справа от второго операнда на, свободном краю ленты записывается слово из й нулей, которое будет использоваться в качестве рабочей ячейки, где и будет аккумулироваться результат умножения. Затем выполняется сложение второго операнда с этим словом (~.

~), соответствующее умножению второго операнда на очередной (ненулевой двоичный!) разряд первого, и сдвиг, происходящий при любом значении этого разряда. Сложения и сдвиги происходят вплоть до по;шого перебора всех разрядов левого операнда. Сложность этого алгоритма относительно сложений и сдвигов линейна (lс — 1 сдвиг и не более Л: сложений), а огпноеигпельно длины слова квадратична (0(Р): не более, й сдвигов-умножений, каждый из которых имеет линейную сложность относительно к).

На, самом деле эта сложность сравнительно невелика, т. к. мы используем известную своей экономностью позиционную систему счисления, а не экспоненциально-сложностную натуральную. Заметим, что если бы это была не двоичная система счисления, то перед сложением дополнительно потребовалось бы умножение операнда на цифру, что усложнило и замедлило бы реализацию умножения. В современных процессорах применяются параллельные схемы умножения, имеющие постоянную сложность (1 такт процессора!), поскольку размер слова фиксирован [18, 79[.

Для реализации мапшны деления потребуется несколько вспомогательных машин. (Напомним, что для удобства реализации и совместимости как с другими МТ, так и с язы- .