загрузка...

АЛГОРИТМЫ - Разработка и применение - 2016 год

Глава 5. Разделяй и властвуй

5.5. Целочисленное умножение

А теперь рассмотрим совершенно иное применение принципа «разделяй и властвуй», в котором «стандартный» квадратичный алгоритм улучшается при помощи другой рекуррентности. В анализе более быстрого алгоритма используется одно из рекуррентных отношений, рассмотренных в разделе 5.2, в котором на каждом уровне порождается более двух рекурсивных вызовов.

Задача

В каком-то смысле задача умножения двух целых чисел настолько фундаментальна, что на первый взгляд может показаться, что это вообще не алгоритмический вопрос. Но в действительности на уроках математики в младших классах объясняют конкретный (и довольно эффективный) алгоритм умножения двух целых чисел х и у, каждое из которых состоит из n цифр. Сначала вычисляется «частичное произведение», для чего каждая цифра у отдельно умножается на х, а полученные частичные произведения суммируются. (Рисунок 5.8 поможет вам вспомнить этот алгоритм. В начальной школе умножение всегда выполняется в десятичной системе, но по основанию 2 оно работает точно так же.) Если взять отдельную операцию с парой битов за один шаг в этом вычислении, для вычисления каждого частичного произведения потребуется время O(n), а также время O(n) для объединения его с накапливаемой суммой всех частичных произведений. С n частичными суммами общее время выполнения составляет O(n2).

Рис. 5.8. Алгоритм умножения двух целых чисел в десятичном (а) и двоичном (b) представлении

Если вы особенно не задумывались над этим алгоритмом с начальной школы, перспективы его улучшения на первый взгляд кажутся сомнительными. Разве все эти частичные произведения не являются в каком-то смысле необходимыми? Но оказывается, время O(n2) можно улучшить при использовании другого, рекурсивного способа выполнения умножения.

Разработка алгоритма

В основу улучшенного алгоритма заложен более умный способ разбиения произведения на частичные суммы. Предположим, вычисления ведутся по основанию 2 (на самом деле это не важно), и запишем x в форме x1 ∙ 2n/2 + x0. Иначе говоря, x1 соответствует «старшим» n/2 битам, а x0 соответствует «младшим» n/2 битам. Аналогичным образом записываетсяy = y1 ∙ 2n/2 + y0. Получаем

Уравнение (5.1) сводит проблему решения одной n-разрядной задачи (умножение двух n-разрядных чисел x и y) к проблеме решения четырех n/2-разрядных задач (вычисление произведений x1y1, x1y0, x0y1 и x0y0). Таким образом, появляется первый кандидат на решение методом «разделяй и властвуй»: рекурсивное вычисление результатов для этих четырех n/2-разрядных экземпляров с последующим объединением их с использованием уравнения (5.1). Объединение решений требует постоянного количества сложений О(n)-разрядных чисел, поэтому оно выполняется за время O(n); следовательно, время выполнения T(n) ограничивается рекуррентным отношением

T(n) ≤ 4T(n/2) + cn

для константы c. Хватит ли этого, чтобы обеспечить субквадратичное время выполнения? Чтобы получить ответ, достаточно заметить, что это просто случай q = 4 класса рекуррентных отношений в (5.3). Как было показано ранее в этой главе, решение имеет вид

Получается, что, применяя алгоритм «разделяй и властвуй» с разбиением на четыре части, мы всего лишь возвращаемся к тому же квадратичному времени более сложным способом! И чтобы добиться лучших результатов со стратегией, сводящей задачу к n/2-разрядным экземплярам, нужно по возможности обойтись только тремя рекурсивными вызовами. Это приведет к случаю q = 3 из (5.3), который, как было показано, имеет решение

Вспомните, что нашей целью является вычисление выражения x1y1 ∙ 2n + (x1y0 + x0y1) ∙ 2n/2 + x0y0 в уравнении (5.1). Как выясняется, существует простой прием, который позволит определить все члены этого выражения с использованием всего трех рекурсивных вызовов. Для этого следует проанализировать результат одного умножения Четыре произведения суммируются с затратами одного рекурсивного умножения. Если x1y1 и x0y0 определяются при рекурсии, то внешние члены будут определены явно, а средний член можно получить вычитанием x1y1 и x0y0 из (x1 + x0)(y1 + y0). Итак, в развернутом виде наш алгоритм выглядит так:

Анализ алгоритма

Время выполнения алгоритма определяется следующим образом. Для двух n-разрядных чисел выполняется постоянное количество сложений O(n)-разрядных чисел помимо трех рекурсивных вызовов. Пока проигнорируем тот факт, что x1 + x0 и y1 + y0 могут содержать n/2 + 1 битов (вместо n/2), так как это не влияет на асимптотические результаты; итак, каждый из рекурсивных вызовов работает с экземпляром размера n/2. Вместо рекурсии с четверным ветвлением мы получаем тройное ветвление с временем выполнения, удовлетворяющим отношению

T(n) ≤ 3T(n/2) + cn

для константы c.

Перед нами тот самый случай q = 3 из (5.3), к которому мы стремились. Используя разрешение рекуррентности, приведенное ранее в этой главе, имеем:

(5.13) Время выполнения рекурсивного умножения для двух n-разрядных множителей равно





загрузка...

загрузка...