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

Когда мы умножаем два $n$-значных числа в столбик, мы фактически делаем $n^2$ однозначных умножений и столько же сложений с переносами. Сложность - $O(n^2)$, и в 1956 году Колмогоров на семинаре заявил, что эту оценку улучшить нельзя. Через четыре года 23-летний студент Анатолий Карацуба придумал, как обойтись меньшим числом операций - и опустил оценку до $O(n^{\log_2 3}) \approx O(n^{1.585})$. Это первое в истории улучшение «школьной» сложности умножения и отправная точка для всех современных быстрых алгоритмов длинной арифметики.

Идея уменьшить четыре умножения до трёх

Возьмём два $n$-значных числа $x$ и $y$ (для простоты $n$ - степень двойки). Разрежем каждое пополам:

$x = x_1 \cdot 10^m + x_0, \qquad y = y_1 \cdot 10^m + y_0,$

где $m = n/2$, а $x_0, x_1, y_0, y_1$ - числа длиной примерно $n/2$ цифр. Если раскрыть скобки в произведении $xy$ по-школьному, получится

$xy = x_1 y_1 \cdot 10^{2m} + (x_1 y_0 + x_0 y_1) \cdot 10^{m} + x_0 y_0.$

Здесь честно четыре умножения $n/2$-значных чисел: $x_1 y_1$, $x_1 y_0$, $x_0 y_1$, $x_0 y_0$. Подставив это в рекуррентное соотношение, мы получим всё ту же $O(n^2)$ - никакого ускорения, потому что четыре подзадачи в два раза меньше дают ровно ту же работу.

Трюк Карацубы - заметить, что средний коэффициент $x_1 y_0 + x_0 y_1$ можно достать из одного дополнительного произведения, а не из двух. Считаем:

$z_0 = x_0 y_0, \qquad z_2 = x_1 y_1, \qquad z_1 = (x_0 + x_1)(y_0 + y_1) - z_0 - z_2.$

Раскроем последнее выражение: $(x_0 + x_1)(y_0 + y_1) = x_0 y_0 + x_0 y_1 + x_1 y_0 + x_1 y_1$, и после вычитания $z_0$ и $z_2$ остаётся ровно $x_0 y_1 + x_1 y_0$ - то, что нам и нужно. Итоговая формула:

$xy = z_2 \cdot 10^{2m} + z_1 \cdot 10^{m} + z_0.$

Три умножения $n/2$-значных чисел вместо четырёх. Сложения и вычитания остаются - но их вклад линейный и в асимптотике задавлен умножениями.

Чтобы прогнать схему руками на длинных числах, проще не считать, а посмотреть на пошаговую трассировку - введите два многозначных числа ниже, и чат покажет разбиение, три подпроизведения и сборку ответа на двух уровнях рекурсии.

Рекурсивная схема и сложность

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

$T(n) = 3\, T(n/2) + O(n).$

По мастер-теореме (случай $a = 3$, $b = 2$, $f(n) = O(n)$, $\log_b a = \log_2 3 \approx 1.585 > 1$) ответ:

$T(n) = \Theta(n^{\log_2 3}).$

Для сравнения: школьное умножение - $O(n^2) = O(n^{2.0})$. На числах в 1000 цифр школьный метод сделает порядка $10^6$ умножений, Карацуба - $10^{4.75} \approx 5.6 \cdot 10^4$, то есть в 18 раз меньше. На 10000 цифр разрыв уже 180-кратный.

Подробный пример

Умножим $x = 1234$ и $y = 5678$ методом Карацубы. Здесь $n = 4$, $m = 2$, основание $10^m = 100$.

Шаг 1. Разбиваем. $x_1 = 12,\ x_0 = 34;\ y_1 = 56,\ y_0 = 78.$

Шаг 2. Три подпроизведения.

• $z_0 = x_0 y_0 = 34 \cdot 78 = 2652.$
• $z_2 = x_1 y_1 = 12 \cdot 56 = 672.$
• Для $z_1$ сначала суммы: $x_0 + x_1 = 46,\ y_0 + y_1 = 134.$ Тогда $(46)(134) = 6164,$ и $z_1 = 6164 - 2652 - 672 = 2840.$

Шаг 3. Собираем.

$xy = z_2 \cdot 10^{4} + z_1 \cdot 10^{2} + z_0 = 672 \cdot 10000 + 2840 \cdot 100 + 2652.$

Считаем: $6\,720\,000 + 284\,000 + 2\,652 = 7\,006\,652.$ Проверка школьным методом: $1234 \cdot 5678 = 7\,006\,652$ - совпало.

На таком маленьком примере Карацуба, конечно, проигрывает столбику: разбиение и три умножения двузначных стоят дороже, чем 16 однозначных. Выигрыш появляется на больших $n$, и каждое из трёх $z_i$, в свою очередь, считается рекурсивно - пока числа не станут достаточно короткими.

Когда Карацуба выгоднее школьного

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

• GMP - порог около 20-30 «лимбов» (по 64 бита, то есть примерно 40-60 десятичных цифр).
• Python (CPython) - Карацуба включается с длины около 70 десятичных цифр.
• Java BigInteger - порог KARATSUBA_THRESHOLD = 80 (в 32-битных «цифрах»).

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

Развитие идеи: Toom-Cook, Шёнхаге-Штрассен, Фюрер

Карацуба разбил число на 2 части и обошёлся 3 умножениями вместо 4. Логичный следующий шаг - разбить на больше частей. Это и есть семейство алгоритмов Toom-Cook (Тоом-Кук, 1963):

• Toom-3 делит число на 3 части, делает 5 умножений вместо 9, даёт $O(n^{\log_3 5}) \approx O(n^{1.465}).$
• Toom-4 - 7 умножений вместо 16, $O(n^{\log_4 7}) \approx O(n^{1.404}).$

Чем больше частей, тем лучше асимптотика, но тем больше констант на склейке и хуже численная устойчивость. На очень длинных числах побеждают алгоритмы, основанные на быстром преобразовании Фурье:

• Шёнхаге-Штрассен (1971) - $O(n \log n \log \log n)$, переход в кольцо целых по модулю числа Ферма и FFT.
• Алгоритм Фюрера (2007) - $O(n \log n \cdot 2^{O(\log^* n)})$, ещё немного быстрее.
• Харви-ван дер Хувен (2019) - рекордные $O(n \log n)$, достигнут теоретический минимум для умножения через FFT.

В реальных библиотеках это всё каскадом: на коротких числах - школьный метод, дальше Карацуба, дальше Toom-3/4, для гигантских чисел - Шёнхаге-Штрассен.

Где встречается

• Big-number библиотеки. GMP (GNU Multiple Precision), Python int, Java BigInteger, .NET BigInteger, Boost.Multiprecision - все используют Карацубу как промежуточную стадию.
• Криптография. RSA, ECC, постквантовые схемы работают с числами в сотни-тысячи бит - там Карацуба и Toom-Cook ускоряют шифрование и подписи. В реализациях типа OpenSSL и mbedTLS они стандартно включены.
• Символьная математика. Mathematica, SymPy, Maple - длинные коэффициенты многочленов, факториалы, числа Бернулли.
• Конкурсное программирование. Когда задача требует умножения многочленов длины $10^5$ и больше - школьный метод не пройдёт по времени, а ручной Карацуба или FFT - пройдёт. В одном ряду с другими «обязательными» алгоритмами с нетривиальной асимптотикой - алгоритмом Кнута-Морриса-Пратта для строк и алгоритмом Кадане для подмассивов.

Частые ошибки

• Считают $(x_0+x_1)(y_0+y_1)$ как новое разбиение пополам - нет, эти суммы могут оказаться на цифру длиннее $n/2$, и их умножение запускает рекурсию на чуть больших аргументах. Аккуратные реализации это учитывают.
• Применяют Карацубу к коротким числам. На 4-8 цифрах столбик быстрее. Без порога переключения вы получите программу, которая на коротких числах медленнее наивной.
• Путают $\log_2 3$ с $\log_3 2$. $\log_2 3 \approx 1.585$ (показатель сложности), а $\log_3 2 \approx 0.631$ - обратная величина, никак не связана.
• Думают, что три умножения работают только в системе по основанию 10. Нет, разбиение делается по любой степени основания - в реальных реализациях это $2^{32}$ или $2^{64}$.

FAQ

Чем алгоритм Карацубы отличается от FFT-умножения? Карацуба - это «разделяй и властвуй» с тремя подзадачами, FFT - это перевод чисел в спектральную область, поточечное произведение и обратное преобразование. FFT асимптотически быстрее ($O(n \log n)$ против $O(n^{1.585})$), но проигрывает по константам на числах короче нескольких тысяч цифр.

Можно ли применять Карацубу к умножению многочленов? Да, и это даже более естественно: многочлен - это последовательность коэффициентов, разбиение пополам и три подпроизведения работают там без переносов и сдвигов по основанию. Рекуррентность и сложность те же.

Кто такой Анатолий Карацуба? Советский математик (1937-2008), автор алгоритма в 23 года, специалист по аналитической теории чисел. Алгоритм впервые опубликован в 1962 году в «Докладах АН СССР» вместе с Юрием Офманом.

Коротко

Алгоритм Карацубы умножает два $n$-значных числа за $O(n^{\log_2 3}) \approx O(n^{1.585})$ вместо школьных $O(n^2)$. Идея - разбить числа пополам и обойтись тремя умножениями половин вместо четырёх через тождество $z_1 = (x_0+x_1)(y_0+y_1) - z_0 - z_2$. Используется в bignum-библиотеках и криптографии на числах длиной от нескольких десятков цифр; для совсем гигантских чисел уступает место Toom-Cook и FFT-методам.