Карацуба: быстрее, чем учили в школе

Гипотеза $n^2$

Осенью 1960 года Андрей Николаевич КолмогоровАндрей Николаевич Колмогороврусский и советский математик · 1903–1987Дал вероятности аксиомы, турбулентности — закон, сложности — определение, а школьной математике в СССР — программу, по которой учились миллионы. вёл на механико-математическом факультете МГУ семинар по математической логике и кибернетике. Его занимал вопрос, который тогда почти никто не считал вопросом: сколько операций нужно, чтобы перемножить два числа?

Способ «в столбик», которому учат в школе и который в неизменном виде дошёл до нас от аль-Хорезми, требует умножить каждую цифру на каждую — это $n^{2}$ операций для $n$-значных чисел. Колмогоров высказал гипотезу, что лучше нельзя: любой алгоритм умножения требует порядка $n^{2}$ операций.

Гипотеза выглядела очевидной. Чтобы получить результат, надо ведь так или иначе учесть все $n^{2}$ пар цифр.

Неделя

Через неделю студент пятого курса Анатолий Карацуба принёс на семинар алгоритм, работающий быстрее.

Идея занимает три строки. Разрежем каждое число пополам:

$$x = x_1 B^{m} + x_0,\qquad y = y_1 B^{m} + y_0,$$

где $B$ — основание, $m$ — половина длины. Обычное перемножение

$$xy = x_1y_1 B^{2m} + (x_1y_0 + x_0y_1)B^{m} + x_0y_0$$

требует четырёх умножений половинок. Карацуба заметил, что достаточно трёх:

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

Раскроем скобки в $z_1$: $(x_1+x_0)(y_1+y_0) = x_1y_1 + x_1y_0 + x_0y_1 + x_0y_0$, и после вычитания $z_2$ и $z_0$ остаётся ровно $x_1y_0 + x_0y_1$ — то, что нужно. Одно умножение заменено двумя сложениями и двумя вычитаниями, а сложение стоит несравненно дешевле.

Посмотрим на числах: $1234\times5678$. Берём $B=100$, $m=1$; $x_1=12$, $x_0=34$, $y_1=56$, $y_0=78$.

$$z_2 = 12\cdot56 = 672,\qquad z_0 = 34\cdot78 = 2652,$$
$$z_1 = (12+34)(56+78) - 672 - 2652 = 46\cdot134 - 3324 = 6164 - 3324 = 2840 .$$

Собираем: $672\cdot10^{4} + 2840\cdot10^{2} + 2652 = 6\,720\,000 + 284\,000 + 2652 = 7\,006\,652$. Верно.

Оценка

Пусть $T(n)$ — число операций. Применяя приём рекурсивно, получаем

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

Три задачи вдвое меньшего размера плюс линейная работа на сложения. Разворачивая рекуррентность, получаем

$$T(n) = O\!\left(n^{\log_2 3}\right) = O\!\left(n^{1{,}585\ldots}\right).$$

Показатель $\log_2 3$ появляется потому, что на каждом уровне рекурсии задач становится втрое больше, а размер уменьшается вдвое. Для тысячезначных чисел это разница между миллионом операций и пятьюдесятью шестью тысячами — почти в двадцать раз.

Гипотеза Колмогорова была опровергнута.

Статью написал Колмогоров

Дальше произошло то, что стоит рассказать отдельно, потому что так почти никогда не бывает.

Колмогоров, узнав результат, сам написал статью и сам отправил её в «Доклады Академии наук» — от имени учеников. Работа вышла в 1962 году: А. А. Карацуба, Ю. П. Офман, «Умножение многозначных чисел на автоматах», ДАН СССР, том 145, две страницы. Юрий Офман был вторым участником семинара, получившим смежный результат — о глубине схем, — и Колмогоров объединил обе заметки в одну публикацию.

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

Ещё одна подробность, которая ставит всё на место: Карацуба был теоретико-числовиком. Его настоящая работа — метод тригонометрических сумм, оценки характерных сумм, теория дзета-функции РиманаБернхард Риманнемецкий математик · 1826–1866Прожил тридцать девять лет и оставил около десяти работ — из которых выросли современная геометрия, теория функций комплексного переменного и главная нерешённая задача математики.; этому он посвятил сорок лет в Математическом институте имени Стеклова. Алгоритм умножения он считал пустяком, потраченной неделей. Это самый цитируемый его результат.

Что было дальше

Приём оказался началом целого направления — «разделяй и властвуй» с экономией умножений.

• Тоом (1963) и Кук (1966) обобщили: разрезая число не на две части, а на $k$, можно довести показатель до $1+\varepsilon$ при любом $\varepsilon>0$.
• Шёнхаге и Штрассен (1971) применили быстрое преобразование Фурье и получили $O(n\log n\log\log n)$ — умножение стало почти линейным.
• Фюрер (2007) снял почти весь логарифмический хвост.
• Харви и ван дер Хувен (2019) доказали оценку $O(n\log n)$. Есть основания считать, что это окончательный ответ: лучше, по-видимому, нельзя, хотя доказательства нет.

Параллельно тот же вопрос был задан про матрицы, и ответ оказался таким же: Штрассен в 1969 году показал, что перемножить две матрицы $2\times2$ можно семью умножениями вместо восьми — и школьный алгоритм снова оказался неоптимальным.

Почему это важнее, чем кажется

До 1960 года вопроса «сколько стоит вычисление» в математике по существу не было. Считалось, что задача либо решается, либо нет; способ — дело техники.

Карацуба показал, что способ — это содержание. Если самый очевидный алгоритм для самой простой операции оказался не лучшим, то и про всё остальное надо спрашивать заново. Через одиннадцать лет из этого вопроса вырастет теория сложности и самая знаменитая открытая задача современности.

Задача. Сколько умножений однозначных чисел потребует школьный способ и способ Карацубы для двух восьмизначных чисел?
(Ответ: в столбик — $8^{2}=64$. У Карацубы рекурсия делит длину пополам трижды: $8\to4\to2\to1$, и на каждом шаге число подзадач умножается на три, то есть $3^{3}=27$. Выигрыш уже здесь больше чем вдвое, а с ростом длины он растёт неограниченно.)

Соседние точки: аль-Хорезми (столбик) → Карацуба (1960) → БПФ (1965) → Штрассен (1969).