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

Два числа по 65 536 цифр. Столбиком их перемножают за 65 536² ≈ 4,3 миллиарда умножений цифр: каждая цифра одного на каждую цифру другого. Анатолий Карацуба в 1960 году показал, что столько не нужно. Ниже — гонка прямо в вашем браузере: столбик, умножение Карацубы и встроенный в браузер BigInt на всё более длинных числах. Оси логарифмические, поэтому скорость роста видна по наклону линий.

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

Идея

Разрежем каждое число пополам: x = x₁B + x₀, y = y₁B + y₀. Тогда xy = x₁y₁B² + (x₁y₀ + x₀y₁)B + x₀y₀. Среднее слагаемое не нужно считать двумя умножениями: оно равно (x₀ + x₁)(y₀ + y₁) − x₁y₁ − x₀y₀, а оба вычитаемых нам и так нужны. Три умножения половин вместо четырёх — и, повторив трюк на каждом уровне, мы получаем n^{log₂ 3} ≈ n^1,585 вместо n².

На маленьком примере: 3141 · 2718. Половины по две цифры, B = 100: x₁ = 31, x₀ = 41, y₁ = 27, y₀ = 18. Три умножения: 31 · 27 = 837, 41 · 18 = 738 и (31 + 41)(27 + 18) = 72 · 45 = 3240. Среднее слагаемое 3240 − 837 − 738 = 1665, и ответ — 837 · 10⁴ + 1665 · 10² + 738 = 8 537 238. Умножение на B — просто сдвиг, его не считаем.

Почему это больше, чем экономия одной четверти. Каждое из трёх умножений половин делается тем же способом, его половины — тоже, и экономия повторяется на каждом уровне. Время подчиняется уравнению T(n) = 3T(n/2) + cn: сложения, вычитания и сдвиги стоят линейно. По основной теореме 3 > 2¹, работа сосредоточена в листьях дерева рекурсии, а листьев n^{log₂ 3}. С четырьмя умножениями половин листьев было бы n^{log₂ 4} = n² — столько же, сколько у столбика: разрезание пополам само по себе ничего не даёт, выигрывает только сэкономленное умножение. Как распределена работа по уровням на настоящих числах, показывает сцена в статье «Разделяй и властвуй».

Код

Числа хранятся списками «цифр» по основанию 10 000, младшая первой. Внутри рекурсии переносы не нужны: коэффициенты спокойно бывают больше основания и даже временно отрицательными, — это умножение многочленов, а переносы делаются один раз в конце. Ниже порога (cutoff) куски умножаются столбиком. Программа перемножает две половины n! — произведения 1·…·n/2 и (n/2 + 1)·…·n, — сверяет результат со встроенной длинной арифметикой и считает умножения цифр.

     n   digits   school products   Karatsuba (cutoff 1)   (cutoff 16)
   200      375              2200                    671          1737
   500     1135             19964                   4259          8436
  1000     2569            101956                  14753         31795
  2000     5736            508464                  49383        115776

На двух половинах 2000! — вместе 5736 десятичных цифр, 1434 «цифры» по основанию 10 000 — столбик делает 508 464 умножения, а Карацуба до упора — 49 383, вдесятеро меньше. С порогом 16 умножений больше, 115 776, но, как увидим ниже, такой вариант работает быстрее.

Сколько это стоит

Время — Θ(n^{log₂ 3}) ≈ Θ(n^1,585), где n — длина чисел: в листьях дерева рекурсии n^{log₂ 3} умножений цифр, а сложений и сдвигов на всех уровнях вместе — тоже Θ(n^{log₂ 3}), потому что работа уровней растёт в полтора раза с каждым уровнем вниз. Память — O(n): каждый уровень держит числа вдвое короче предыдущего, и в сумме по ветке рекурсии выходит не больше 2n цифр. Замер — наш столбик, наша Карацуба с порогом 16 и встроенное умножение языка:

На Python наша Карацуба обгоняет столбик уже на нескольких сотнях цифр и на 2048 цифрах примерно вчетверо быстрее. Встроенное умножение Python на порядки быстрее обеих — оно написано на C, — но наклон у него тот же, около 1,6: каждое удвоение длины примерно втрое увеличивает время. Это и есть Карацуба внутри CPython. В Go встроенная math/big растёт так же, а наша Карацуба на Go обгоняет столбик позже, около четырёх тысяч цифр: внутренний цикл столбика компилируется в несколько машинных команд, и выделения памяти в рекурсии на этом фоне обходятся относительно дороже.

Порог: где переходить на столбик

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

Порог зависит от машины, и разработчики Go описали это подробно. Для math/big они замерили умножение чисел длиной от 200 до 400 слов с шагом 8 при каждом пороге на пяти процессорах. На большинстве лучший порог оказался около 40, на одном из серверных Intel Xeon — ближе к 60; выбрали 40, и на том Xeon он проигрывает лучшему в среднем около 2%. Там же видно, почему одного идеального порога нет: для числа из 320 слов все пороги от 21 до 40 дают одно и то же — рекурсия доходит до кусков по 40 слов, — а для числа из 240 слов одинаковы пороги от 31 до 60. Поэтому порог выбирают по многим длинам сразу. В GMP пороги подобраны под каждый тип процессора отдельно и выбираются при сборке библиотеки.

В первой сцене порог можно двигать самому. В JavaScript накладные расходы рекурсии велики, и порог 1 заметно проигрывает порогу 16, хотя умножений делает меньше: количество операций и время — не одно и то же.

Суммы или разности, равные и неравные множители

Суммы или разности. CPython считает среднее слагаемое через суммы, (x₁ + x₀)(y₁ + y₀). Go и GMP — через разности: x₁y₀ + x₀y₁ = x₁y₁ + x₀y₀ − (x₁ − x₀)(y₁ − y₀). Сумма половин может оказаться на цифру длиннее половины, а разность — никогда; зато у разности бывает знак, и его приходится помнить отдельно. У разностей есть и неожиданное следствие: если половины чисел совпадают, третье умножение становится умножением на ноль и стоит почти ничего. Как это однажды испортило замер для каталога, рассказано в статье о сложности по замерам.

Квадрат. Если x = y, все три умножения половин — тоже квадраты, а квадрат дешевле произведения: половину попарных произведений цифр можно не считать. Поэтому у квадратов свой порог: в CPython 140 цифр вместо 70, в Go 80 слов вместо 40.

Неравные множители. Пусть одно число в сто раз длиннее другого. Если резать длинное пополам, у короткого старшая половина окажется нулём, и трюк выродится. CPython в таком случае режет длинное число на куски длиной в короткое и перемножает короткое с каждым куском — так получаются вызовы с равными длинами, где Карацуба работает. Go делает то же. А если второй множитель совсем короткий, в одну-две цифры, Карацубе нечего делать вовсе: такое умножение и так линейно.

Отсюда практический вывод для произведения многих чисел. Посчитаем n! двумя способами одним и тем же BigInt браузера: умножая по очереди — каждый раз длинное число на короткое, — и деревом произведений, где множители всегда примерно равны по длине.

По очереди время растёт примерно как n²: каждое из n умножений проходит по всему длинному числу. Деревом время растёт заметно медленнее: на каждом уровне дерева перемножаются равные половины, и быстрое умножение работает в полную силу. Так считает и сам Python: math.factorial устроен как «разделяй и властвуй» по половинам диапазона.

Что после Карацубы

Идея обобщается. Андрей Тоом в 1963 году и Стивен Кук в 1966-м резали числа не на две, а на k частей и обходились 2k − 1 умножениями частей вместо k²: при трёх частях — пятью умножениями вместо девяти, и рост n^{log₃ 5} ≈ n^1,465. Арнольд Шёнхаге и Фолькер Штрассен в 1971 году перемножили числа через быстрое преобразование Фурье за O(n log n log log n), а в 2019 году Дэвид Харви и Йорис ван дер Хувен получили O(n log n); быстрее, по общему мнению, нельзя, но доказательства нет.

На практике методы выстраиваются по длине чисел. В GMP за столбиком идёт Карацуба, за ней Тоом — Кук на три, четыре, шесть с половиной и восемь с половиной частей, а для самых длинных чисел — БПФ. CPython и Go на Карацубе останавливаются. Тот же трюк годится и для многочленов — там нет переносов, и он даже проще; так его и записывает листинг выше.

История

Осенью 1960 года Андрей Колмогоров на семинаре по математическим вопросам кибернетики предположил, что быстрее чем за порядка n² действий два n-значных числа перемножить нельзя. Двадцатитрёхлетний Анатолий Карацуба через неделю принёс способ с тремя умножениями половин. В 1962 году статья о методе вышла в «Докладах Академии наук» под фамилиями Карацубы и Юрия Офмана; опубликовал её Колмогоров, и Карацуба, по его воспоминаниям, узнал о статье, только получив оттиски. Подробнее эта история рассказана в главе базового курса.

Задачи

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