Умножение КарацубыKaratsuba Multiplication

Пусть x и y — n-значные числа (n чётно для простоты), разбитые пополам: x = x₁·10^m + x₀, y = y₁·10^m + y₀, где m = n/2, x₁/y₁ — старшие половины, x₀/y₀ — младшие. Произведение раскрывается как x·y = x₁y₁·10^(2m) + (x₁y₀ + x₀y₁)·10^m + x₀y₀. Наивно это требует 4 рекурсивных умножения: x₁y₁, x₁y₀, x₀y₁, x₀y₀ — и рекуррентное соотношение T(n) = 4T(n/2) + O(n) по Master theorem (2.1.2) даёт O(n²), то же самое, что и школьный метод без всякой рекурсии. Разбиение само по себе ничего не выиграло.Let x and y be n-digit numbers (n even for simplicity), split in half: x = x₁·10^m + x₀, y = y₁·10^m + y₀, where m = n/2, x₁/y₁ are the high halves, x₀/y₀ the low halves. The product expands as x·y = x₁y₁·10^(2m) + (x₁y₀ + x₀y₁)·10^m + x₀y₀. Naively this needs 4 recursive multiplications: x₁y₁, x₁y₀, x₀y₁, x₀y₀ — and the recurrence T(n) = 4T(n/2) + O(n), by the Master theorem (2.1.2), gives O(n²), the same as the schoolbook method with no recursion at all. The split by itself bought nothing.

Ключевой трюк Карацубы: средний коэффициент (x₁y₀ + x₀y₁) можно получить не через два отдельных умножения, а через одно дополнительное — вычислить z = (x₁+x₀)(y₁+y₀) = x₁y₁ + x₁y₀ + x₀y₁ + x₀y₀, а затем вычесть из z уже посчитанные x₁y₁ и x₀y₀: x₁y₀ + x₀y₁ = z − x₁y₁ − x₀y₀. Итого нужно ровно 3 рекурсивных умножения — x₁y₁, x₀y₀ и z — вместо 4, а остальное (сложения, вычитания, сдвиг на степень 10) стоит O(n). Рекуррентное соотношение становится T(n) = 3T(n/2) + O(n), и по Master theorem это T(n) = O(n^log₂3) = O(n^1.585...) — асимптотически строго лучше n², хотя разница проявляется только на достаточно больших n из-за constant factor рекурсии.Karatsuba's key trick: the middle coefficient (x₁y₀ + x₀y₁) can be obtained not via two separate multiplications but via one extra one — compute z = (x₁+x₀)(y₁+y₀) = x₁y₁ + x₁y₀ + x₀y₁ + x₀y₀, then subtract the already-computed x₁y₁ and x₀y₀ from z: x₁y₀ + x₀y₁ = z − x₁y₁ − x₀y₀. In total exactly 3 recursive multiplications are needed — x₁y₁, x₀y₀, and z — instead of 4, and everything else (additions, subtractions, shifting by a power of 10) costs O(n). The recurrence becomes T(n) = 3T(n/2) + O(n), and by the Master theorem that's T(n) = O(n^log₂3) = O(n^1.585...) — asymptotically strictly better than n², though the difference only shows up at sufficiently large n because of the recursion's constant factor.

long long karatsuba(long long x, long long y) {
    if (x < 10 || y < 10) return x * y;   // базовый случай// base case

    int m = std::max(digits(x), digits(y)) / 2;
    long long pow10m = ipow(10, m);

    long long x1 = x / pow10m, x0 = x % pow10m;   // старшая / младшая половина// high / low half
    long long y1 = y / pow10m, y0 = y % pow10m;

    long long z2 = karatsuba(x1, y1);              // x1*y1// x1*y1
    long long z0 = karatsuba(x0, y0);              // x0*y0// x0*y0
    long long z1 = karatsuba(x1 + x0, y1 + y0) - z2 - z0;  // ровно одно доп. умножение// exactly one extra multiplication

    return z2 * ipow(10, 2*m) + z1 * pow10m + z0;
}

Введите два небольших числа — демонстрация проигрывает разбиение на половины, вычисление трёх произведений z2/z0/z1 и финальную сборку z2·10^2m + (z1−z2−z0)·10^m + z0 шаг за шагом.Enter two small numbers — the demo auto-plays the split into halves, computing the three products z2/z0/z1, and the final assembly z2·10^2m + (z1−z2−z0)·10^m + z0, step by step.

Mergesort (2.2.1) тоже разбивает пополам и решает T(n) = 2T(n/2) + O(n) = O(n log n) — но там a=2 и это не выбор, а прямое следствие природы задачи (объединить два уже отсортированных списка можно только слиянием, никакого "трюка" для уменьшения количества подзадач не существует и не нужно). У Карацубы a изначально было 4 (по числу пар половин), и весь алгоритм — это способ снизить его до 3. Разница принципиальна: в сортировке слиянием f(n) — это неизбежная стоимость слияния, а в умножении Карацубы a — это то, что можно уменьшить алгебраическим трюком. Именно поэтому Карацуба — не "ещё одна сортировка", а первый пример техники "разделяй и властвуй ради самой техники".Mergesort (2.2.1) also splits in half and solves T(n) = 2T(n/2) + O(n) = O(n log n) — but there a=2 isn't a choice, it's a direct consequence of the problem's nature (merging two already-sorted lists can only be done by merging; there's no "trick" to reduce the subproblem count, nor is one needed). For Karatsuba, a started out at 4 (one per pair of halves), and the entire algorithm is a way to bring it down to 3. The difference is fundamental: in mergesort, f(n) is the unavoidable cost of merging, while in Karatsuba multiplication, a is the thing an algebraic trick can shrink. That's exactly why Karatsuba isn't "just another sort" — it's the first example of divide-and-conquer as a technique in its own right.