Карацуба: три умножения вместо четырёх

Если ты помнишь разложение X·Y на четыре произведения половинок, знаешь тождество Карацубы и понимаешь, почему порог перехода на столбик обязателен, листай до «Теперь сам».

Как думаешь, можно ли умножать быстрее школьного способа

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

Рассуждение выглядит железным - и оно неверно. В 1960 году Колмогоров на семинаре высказал гипотезу, что быстрее n² нельзя; двадцатитрёхлетний Карацуба опроверг её за неделю. Вопрос: где в «железном» рассуждении дыра?

На что это похоже

Взвешивание на весах. Чтобы узнать вес трёх предметов по отдельности, кажется, нужно три взвешивания. Но если взвесить два вместе, потом первый отдельно, потом второй отдельно - третий вес получится вычитанием, и четвёртого взвешивания не понадобится. Карацуба делает ровно это: одно «совместное взвешивание» вместо двух отдельных, а разность досчитывается бесплатно.

Механизм: разрезать число пополам

Пусть у чисел по n цифр в основании B (для ручного счёта удобно B = 100, для машины B = 2³²). Разрежем каждое пополам, m = n/2:

X = X₁·Bᵐ + X₀          старшая и младшая половины
Y = Y₁·Bᵐ + Y₀

X·Y = X₁Y₁·B²ᵐ + (X₁Y₀ + X₀Y₁)·Bᵐ + X₀Y₀

Наивно это ЧЕТЫРЕ умножения половинок: X₁Y₁, X₁Y₀, X₀Y₁, X₀Y₀. Сложения и сдвиги линейны, значит T(n) = 4·T(n/2) + n. По главной теореме n^(log₂ 4) = n² против f(n) = n - листья тяжелее, ответ Θ(n²). Тот же квадрат, что у столбика: деление само по себе ничего не дало.

ТОЖДЕСТВО КАРАЦУБЫ

z₂ = X₁·Y₁
z₀ = X₀·Y₀
z₁ = (X₁ + X₀)·(Y₁ + Y₀) − z₂ − z₀        = X₁Y₀ + X₀Y₁

X·Y = z₂·B²ᵐ + z₁·Bᵐ + z₀

умножений половинок: ТРИ    →   T(n) = 3·T(n/2) + n   →   Θ(n^log₂ 3) = Θ(n^1.585)

Дыра в «железном» рассуждении вот где: каждая цифра действительно обязана повлиять на ответ, но это НЕ значит, что каждая пара цифр должна быть перемножена отдельно. Нужные суммы произведений можно получать целиком, не вычисляя слагаемые по отдельности.

Правило

Разрезав числа пополам, произведение выражается через произведения половинок. Наивно их четыре - это T(n) = 4·T(n/2) + n и всё тот же Θ(n²). ТОЖДЕСТВО КАРАЦУБЫ даёт средний член одним лишним умножением: z₁ = (X₁+X₀)(Y₁+Y₀) − z₂ − z₀. Умножений становится три, T(n) = 3·T(n/2) + n, и ответ - Θ(n^1.585). Цена трюка - лишние сложения и вычитания, поэтому на коротких числах столбик быстрее, и в реализациях стоит ПОРОГ (обычно десятки цифр), ниже которого рекурсия не идёт.

Разбор: 1234 × 5678 руками

Возьмём B = 100, то есть режем по две десятичные цифры: у каждого числа выходит ровно две «цифры» основания 100, и разрез идёт по m = 1 (одна такая цифра в младшей половине). Поэтому Bᵐ = 100, а B²ᵐ = 100² = 10 000.

X₁ = 12   X₀ = 34
Y₁ = 56   Y₀ = 78

z₂ = 12 · 56 = 672
z₀ = 34 · 78 = 2652
сумма половин: X₁ + X₀ = 46,  Y₁ + Y₀ = 134
(X₁+X₀)(Y₁+Y₀) = 46 · 134 = 6164
z₁ = 6164 − 672 − 2652 = 2840

X·Y = 672·100² + 2840·100 + 2652
    = 6 720 000 + 284 000 + 2 652
    = 7 006 652

Проверка столбиком: 1234 · 5678 = 7 006 652. Сходится.

Посчитаем умножения. Столбиком - 4 × 4 = 16 умножений цифр. Наивным делением пополам - четыре умножения двузначных, то есть 4 × 4 = 16 умножений цифр. Карацубой - три умножения двузначных, 3 × 4 = 12. На четырёх цифрах экономия невелика, но она РЕКУРСИВНАЯ: на каждом уровне вместо четырёх подзадач возникает три.

Разбор: откуда берётся 1.585 и когда она окупается

Посчитаем число умножений цифр на разных размерах.

На n = 2^k цифрах числа считаются точно: столбик делает 4^k умножений (на каждом уровне четыре подзадачи), Карацуба - 3^k.

n цифр      столбик 4^k        Карацуба 3^k      отношение (4/3)^k
    8               64                   27            2.4
   64            4 096                  729            5.6
  512          262 144               19 683           13.3
 4096       16 777 216              531 441           31.6

Растёт не разница, а ОТНОШЕНИЕ: n² / n^1.585 = n^0.415. На тысяче цифр (k = 10) это 1 048 576 против 59 049 - почти в восемнадцать раз меньше умножений, на миллионе цифр - в сотни.

Но у трюка есть цена. Посчитаем сложения на одном уровне. Наивно их три: X₁Y₀ + X₀Y₁ и два при сборке ответа. У Карацубы шесть: X₁ + X₀, Y₁ + Y₀, два вычитания в z₁ и те же два при сборке. Итого одно умножение сэкономлено, три сложения добавлено - и на коротких числах это невыгодно. Пока числа короткие, эти операции дороже сэкономленного умножения, поэтому все реализации ставят порог:

n < ПОРОГ   →  умножать столбиком, без рекурсии
n >= ПОРОГ  →  Карацуба

Конкретное значение порога зависит от машины и от размера машинного слова; в библиотеках длинной арифметики это обычно от 16 до 64 «цифр» по 32 или 64 бита. Ровно та же история, что с порогом в сортировке слиянием из прошлой главы: асимптотика говорит, что делить выгодно, а замер говорит, до какого размера.

Что ломается без этого

Первое: считать, что деление пополам само по себе ускоряет, - четыре умножения половинок дают тот же квадрат. Второе: забыть, что X₁ + X₀ может быть ДЛИННЕЕ половины на одну цифру (перенос), и получить переполнение буфера в реализации на массивах. Третье: писать Карацубу без порога и получить программу медленнее столбика на всех практических размерах. Четвёртое: применять трюк к числам разной длины, не выровняв их нулями: разрез должен идти по одному и тому же m. Пятое: считать, что n^1.585 - предел: Тоом-Кук даёт n^1.465, а умножение через быстрое преобразование Фурье - n·log n; Тоом-Кук разбирается в третьем уроке этой главы, а преобразование Фурье - в отдельной главе раздела.

Зачем это в работе

Длинная арифметика стоит под всей криптографией с открытым ключом: RSA перемножает числа по две тысячи бит и больше, и там Карацуба - обязательный минимум (а дальше Тоом-Кук и БПФ по порогам). Она же нужна в компьютерной алгебре, в точных вычислениях с рациональными числами, в подсчёте больших комбинаторных величин. Даже если ты никогда не будешь писать bignum сам, полезно знать, что int в Python - это длинная арифметика с порогами внутри, и умножение двух очень больших чисел не линейно по числу цифр, а почти линейно - и это следствие именно таких алгоритмов. А главный урок общий: «каждая пара обязана встретиться» - типичная ложная интуиция, и проверять её надо арифметикой, а не ощущением.

Теперь сам

Перемножь X = 5612 и Y = 3478 методом Карацубы при B = 100. Выпиши z₂, z₀, z₁ и ответ.

z₂ = 56 · 34 = 1904
z₀ = 12 · 78 = 936
X₁ + X₀ = 68,  Y₁ + Y₀ = 112
(X₁+X₀)(Y₁+Y₀) = 68 · 112 = 7616
z₁ = 7616 − 1904 − 936 = 4776

X·Y = 1904·10 000 + 4776·100 + 936
    = 19 040 000 + 477 600 + 936
    = 19 518 536