Алгоритм Карацубы: быстрое умножение чисел в программировании

Алгоритм Карацубы - это алгоритм умножения двух чисел, который был разработан в 1960-х годах русским математиком Анатолием Александровичем Карацубой. Он основан на идее разбиения чисел на меньшие части, а затем использования рекуррентной формы для вычисления произведения.

Алгоритм Карацубы позволяет ускорить процесс умножения и быстро находить произведение очень больших чисел. Он может работать до O(n^(log2(3))) операций сравнения и выполнения операций сложения и вычитания. В отличие от обычного умножения, которое работает за O(n^2) операций, где n - количество цифр в числах.

Пример рекурсивного алгоритма Карацубы для умножения двух чисел выглядит следующим образом:

1. Разбить каждое число на две равные части.

2. Рекурсивно умножить полученные части.

3. Вычислить три промежуточных произведения: первая - умножение левых частей, вторая - умножение правых частей, а третья - (A1 + A2) * (B1 + B2).

4. Вычислить результат: первое произведение * 10^(2*m) + третье произведение * 10^m + второе произведение.

Вот пример кода на Python, реализующий алгоритм Карацубы:

def karatsuba(x, y):
    # выход из рекурсии при однозначных числах
    if x < 10 or y < 10:
        return x*y
    # определяем максимальное количество цифр в числах
    m = max(len(str(x)), len(str(y)))
    m2 = m // 2
    # разбиваем числа на две части
    a, b = divmod(x, 10**m2)
    c, d = divmod(y, 10**m2)
    # рекурсивно вычисляем произведения частей
    ac = karatsuba(a, c)
    bd = karatsuba(b, d)
    abcd = karatsuba(a+b, c+d)
    # вычисляем третье промежуточное произведение
    adbc = abcd - ac - bd
    # вычисляем результат
    return ac * 10**(2*m2) + adbc * 10**(m2) + bd

Давайте рассмотрим пример: x = 1234, y = 5678.

1. Разбиваем x и y на две равные части: a = 12, b = 34, c = 56, d = 78.

2. Рекурсивно умножаем нашы части: ac = 672, bd = 2652, abcd = 21594.

3. Вычисляем третье промежуточное произведение: adbc = abcd - ac - bd = 1970.

4. Вычисляем результат: 672 * 10^4 + 1970 * 10^2 + 2652 = 7006652.

Таким образом, мы нашли произведение двух чисел за O(n^(log2(3))) операций вместо O(n^2), что делает алгоритм Карацубы более эффективным при умножении больших чисел.