На этом шаге мы рассмотрим рекурсивную версию алгоритма Карацубы.

Известный ещё со школы классический алгоритм поразрядного умножения двух неотрицательных N-разрядных целых чисел требует времени порядка n². На этом шаге мы разберём более быстрый алгоритм Карацубы. Метод можно применять к числам в любой системе счисления, но мы сосредоточимся на умножении двоичных чисел. В частности, пусть x и у - два неотрицательных целых числа, состоящих из b_x и b_y двоичных разрядов соответственно. Применив подход "разделяй и властвуй", каждое двоичное число можно разделить на два следующим образом:

    x = a * 2^m + b, y = c * 2^m + d,       (6.2)

где m = min(⌊b_x/2⌋, ⌊b_y/2⌋).

Например, для x = 594 и у = 69 декомпозиция будет такой:

    x = 1001010010₂ = 1001010{a = 74}010{b = 2} = 74 * 2³ + 2, 
    у = 1000101₂ = 1000{с = 8}101{d = 5} = 8 * 2³ + 5,

где b_x = 10, b_y = 7, m = 3, a = 74, b = 2, c = 8 и d = 5. Таким образом, меньшее число (в данном случае - у) разделено на две части (примерно) с одинаковым количеством двоичных разрядов, а младшие части разбиения (b и d) имеют одинаковое количество двоичных разрядов.

Во многих языках программирования вычислить значения a, b, c и d можно с помощью операций поразрядного сдвига (в языке Python такими операциями являются << и >>). Сдвиг x влево на m разрядов (x << m) с добавлением m младших нулей равнозначен ⌊x * 2^m⌋. Сдвиг x вправо на m разрядов (x >> m) с отбрасыванием m младших разрядов равнозначен ⌊x / 2^m⌋. Такие поразрядные операции полезны при целочисленном умножении (или делении) на степень двух и могут использоваться для разбиения x и у согласно (6.2) следующим образом:

    a = x >> m, b = x - (a << m), c = у >> m, d = у - (c << m),

где круглые скобки необходимы в силу правил старшинства операций.

Согласно декомпозиции, произведение x и у можно записать как

    x * у = (а * 2^m + b)(c * 2^m + d) = a * c2^2m + (a * d + b * c)2^m + b * d.   (6.3)

Этот первоначальный (примитивный) подход разбивает исходную задачу (умножения) на четыре меньшие подзадачи умножения ac, ad, bc и bd, решение которых можно получить четырьмя рекурсивными вызовами (затратами времени на умножение на степень двух можно пренебречь, поскольку его очень эффективно заменяют операции поразрядного сдвига). Однако этот подход не намного эффективнее "школьного", так как он тоже требует n² поразрядных умножений для двух n-разрядных чисел. Предложенный Карацубой алгоритм может снизить затраты времени примерно до 1,585 * n за счёт перегруппировки слагаемых и увеличения числа операций сложения и вычитания, которые оказывают незначительное влияние на асимптотическую сложность вычислений. В частности, произведение xy можно заново переписать как

    x * у = a * c2^2m + ((a + b)(c + d) - a * c - b * d)2^m + b * d,        (6.4)

где требуется всего три более простых произведения a * c, b * d и (a + b) (c + d), что приводит к более быстрому алгоритму, выполняющему только три рекурсивных вызова.

В примере 6.8 приведена реализация метода Карацубы вместе со вспомогательной функцией, вычисляющей количество двоичных разрядов неотрицательного целого числа n, равное ⌊log₂n⌋ для n > 1.

Пример 6.8. Быстрый алгоритм Карацубы умножения двух неотрицательных целых чисел

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

def number_of_bits(n):
    if n < 2:
        return 1
    else:
        return 1 + number_of_bits(n >> 1)


def multiply_karatsuba(x, y):
    if x == 0 or y == 0:
        return 0
    elif x == 1:
        return y
    elif y == 1:
        return x
    else:
        n_bits_x = number_of_bits(x)
        n_bits_y = number_of_bits(y)

        m = min(n_bits_x // 2, n_bits_y // 2)

        a = x >> m
        b = x - (a << m)
        c = y >> m
        d = y - (c << m)

        ac = multiply_karatsuba(a, c)
        bd = multiply_karatsuba(b, d)
        t = multiply_karatsuba(a + b, c + d) - ac - bd     

        return (ac << (2 * m)) + (t << m) + bd

Архив с файлом можно взять здесь.

Размер задачи - min(b_x, b_y). Таким образом, начальные условия должны проверить входы на равенство 0 или 1, приводящие к тривиальным результатам. Рекурсивные условия реализуют (6.4) тремя рекурсивными вызовами.

Что касается эффективности этого алгоритма, то предположим, что оба входа имеют одинаковое количество двоичных разрядов n, являющееся степенью двух (то есть n = 2^k). Такое допущение возможно, поскольку к входным целочисленным значениям всегда можно добавить ведущие нули так, чтобы предположение выполнилось. В этом случае время выполнения алгоритма описывается функцией:

            1,                если n ≤ 1,
    T(n) =  
            3T(n/2) + cⁿ + d, если n > 1,

Слагаемое cⁿ + d возникает из-за сложений, вычитаний, операций сдвига и вызовов number_of_bits(), которые выполняются за линейное время относительно n. Применяя основную теорему, T(n) ∈ Θ(n log₂3) = Θ(n * 1,585...). Таким образом, этот метод эффективнее подхода, связанного с (6.3), чья стоимость вычислений описывается функцией:

            1,                если n ≤ 1,
    T(n) =  
            4T(n/2) + eⁿ + f, если n > 1,

где T(n) ∈ Θ(n²).

Алгоритм Карацубы использует меньше умножений (соответствующих рекурсивным вызовам), чем школьный метод, но выполняет больше сложений и вычитаний. На практике алгоритм будет быстрее для больших значений n. Однако если n мало, дополнительные операции могут сделать его медленнее традиционного метода. В любом случае, метод примечателен тем, что он может сократить количество операций умножения, которые значительно дороже сложения или вычитания.

Со следующего шага мы начнем рассматривать умножение матриц.

Предыдущий шаг Содержание Следующий шаг