Целочисленное умножение - Разделяй и властвуй

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

Задача

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

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

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

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

В основу улучшенного алгоритма заложен более умный способ разбиения произведения на частичные суммы. Предположим, вычисления ведутся по основанию 2 (на самом деле это не важно), и запишем x в форме x₁ ∙ 2^n/2 + x₀. Иначе говоря, x₁ соответствует “старшим” n/2 битам, а x₀ соответствует “младшим” n/2 битам. Аналогичным образом записываетсяy = y₁ ∙ 2^n/2 + y₀. Получаем

Уравнение (5.1) сводит проблему решения одной n-разрядной задачи (умножение двух n-разрядных чисел x и y) к проблеме решения четырех n/2-разрядных задач (вычисление произведений x₁y₁, x₁y₀, x₀y₁ и x₀y₀). Таким образом, появляется первый кандидат на решение методом “разделяй и властвуй”: рекурсивное вычисление результатов для этих четырех 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), который, как было показано, имеет решение

Вспомните, что нашей целью является вычисление выражения x₁y₁ ∙ 2ⁿ + (x₁y₀ + x₀y₁) ∙ 2^n/2 + x₀y₀ в уравнении (5.1). Как выясняется, существует простой прием, который позволит определить все члены этого выражения с использованием всего трех рекурсивных вызовов. Для этого следует проанализировать результат одного умножения Четыре произведения суммируются с затратами одного рекурсивного умножения. Если x₁y₁ и x₀y₀ определяются при рекурсии, то внешние члены будут определены явно, а средний член можно получить вычитанием x₁y₁ и x₀y₀ из (x₁ + x₀)(y₁ + y₀). Итак, в развернутом виде наш алгоритм выглядит так:

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

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

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

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

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

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