Математики до сих пор не уверены, как быстрее всего перемножать числа

Как 23-летний студент опроверг давнюю гипотезу об одной из простейших математических операций

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

Эта загадка имеет решающее значение для всех, кто имеет отношение к цифровому миру, поскольку умножение является основополагающей операцией для компьютеров. Шифрование, робототехника, искусственный интеллект, обработка звука и практически всё остальное, чем мы заставляем заниматься кремниевые чипы, связано с умножением, причём иногда огромных чисел, умножаемых многократно. В таких масштабах даже простая операция становится «узким местом», и любое дополнительное повышение эффективности имеет глобальные экономические последствия.

Чтобы понять суть этого «узкого места», обратите внимание на то, как «школьный» алгоритм справляется с увеличением размера чисел. При умножении двух двузначных чисел выполняется четыре однозначных умножения. Если перейти к паре трёхзначных чисел, то потребуется девять однозначных умножений. Нагрузка растёт пропорционально квадрату количества разрядов (n², где n — количество разрядов в умножаемых числах). При анализе подобного алгоритма компьютерные учёные не измеряют скорость в секундах, поскольку она зависит от аппаратного обеспечения. Вместо этого они подсчитывают количество вычислительных шагов. Они также игнорируют второстепенные детали, такие как время, необходимое для переноса единицы при умножении. Когда числа становятся достаточно большими, эти низкоуровневые операции перестают иметь значение, поскольку их полностью затмевают более ресурсоёмкие операции. Информатики обозначают количество шагов с помощью так называемой нотации «большого O»: например, алгоритм, который учат в начальной школе, требует O(n²) шагов, что читается как «порядка n в квадрате». В общих чертах, если числа в два раза длиннее, для выполнения алгоритма требуется в четыре раза больше вычислительной работы. Если числа в тысячу раз длиннее, требуется в миллион (1 000 в квадрате) раз больше работы.

Ещё с древних времён математики подозревали, что O(n²) является неотъемлемым пределом скорости умножения. Известный советский профессор математики Андрей Колмогоров сформулировал предел скорости O(n²) в виде формальной гипотезы и упомянул о ней во время семинара в Московском государственном университете в 1960 году. Когда математики выдвигают гипотезу, они бросают другим вызов и ждут, пока другие либо докажут, либо опровергнут её. Потребовалась всего неделя, чтобы Анатолий Карацуба, тогда 23-летний студент из аудитории, вернулся и доказал, что Колмогоров ошибался. Колмогоров был ошеломлён. Результат был опубликован в престижном журнале «Труды Академии наук СССР», но, что забавно, Карацуба не писал статью. Колмогоров сам написал формальное доказательство и представил его к публикации, указав Карацубу в качестве ведущего автора. Карацуба узнал о статье только тогда, когда получил репринты по почте.

Гениальность Карацубы заключалась в том, что он понял: дорогостоящие и трудоёмкие умножения можно заменить на простые и быстрые сложения. Сложение двух n‑значных чисел занимает всего O(n) времени, поскольку требует лишь одного прохода по цифрам, а не полного прохода по верхнему числу для каждой цифры нижнего числа, как при умножении. Чтобы понять, как Карацуба заменил умножение сложением, рассмотрим небольшой пример. Для такой простой задачи этот метод будет чрезмерно сложным, но он позволяет сэкономить значительное время, когда числа становятся больше.

В этом простом примере давайте вычислим чему равно 12 × 34.

Сначала разделим оба числа на десятки и единицы. Присвоим a = 1 и b = 2 (для 12), а также c = 3 и d = 4 (для 34). В алгебраическом виде 12 × 34 можно переписать как (10a + b) × (10c + d).

Раскроем скобки: 100(ac) + 10(ad + bc) + (bd).

Чтобы решить уравнение традиционным способом, необходимо выполнить четыре отдельных умножения: ac = 3, ad = 4, bc = 6 и bd = 8, что в точности соответствует методу умножения столбиком, используемому в начальной школе. (Обратите внимание, что мы не учитываем умножения на 100 или на 10, поскольку они сводятся лишь к добавлению нулей в конце чисел). Карацуба придумал гениальный алгебраический трюк. Как только вы вычислите первый и последний члены, ac и bd, вы сможете определить этот надоедливый средний член (ad + bc) с помощью всего одного дополнительного умножения вместо двух. Вам не нужно вычислять ad и bc по отдельности:

(ad + bc) = ((a + b) × (c + d)) — ac — bd,

Или, если использовать наши конкретные числа:

((1 × 4) + (2 × 3)) = ((1 + 2) × (3 + 4)) — 3 — 8 = 10.

Остановимся на мгновение, чтобы обратить внимание на странность в приведённом выше уравнении. Получается, что для быстрого умножения 12 × 34 нужно сложить 1 и 2 в числе 12, а также 3 и 4 в числе 34. Это вряд ли можно назвать очевидным. Неудивительно, что потребовалось столько времени, чтобы кто‑то до этого додумался. Однако в итоге это снижает нагрузку: поскольку мы уже вычислили ac и bd, в правой части остается только одно умножение, плюс несколько сложений и вычитаний.

Вернувшись к выражению 100(ac) + 10(ad + bc) + (bd), мы видим, что нам потребуется всего три умножения вместо четырёх. Мы вычисляем ac и bd обычным способом, а затем используем приём Карацубы, чтобы вычислить (ad + bc) с помощью одного умножения. Подставляя ac = 3, bd = 8 и (ad + bc) = 10, получаем ответ 408.

Мы сократили процедуру на одно умножение. Если это кажется незначительным, у Карацубы есть ещё одна идея. Допустим, мы умножаем более крупные числа: 1234 × 5678. Мы разбиваем их пополам, как и раньше: a = 12, b = 34, c = 56 и d = 78, и записываем задачу в виде (100a + b) × (100c + d) = 10 000(ac) + 100(ad + bc) + (bd).

Мы можем решить эту задачу с помощью трёх умножений. Однако в этих умножениях теперь участвуют двузначные числа. К счастью, мы знаем способ умножения двузначных чисел, при котором для каждого из них требуется всего по три однозначных умножений! В итоге задача, для решения которой традиционным способом потребовалось бы 16 однозначных умножений, теперь требует всего девяти. Благодаря рекурсивному применению приёма Карацубы к большим числам экономия растёт. Он делит входные числа пополам, затем делит эти половины пополам и так далее, применяя этот обмен «четыре на три» на всех уровнях. Время выполнения алгоритма составляет примерно O(), что значительно быстрее, чем O(n²). Для сравнения: умножение пары тысячных чисел требует миллиона однозначных умножений при использовании школьного метода, но менее 57 000 — при использовании алгоритма Карацубы.

Эффективность этого алгоритма от 23-летнего математика заложена в повседневно используемое программное обеспечение. Из‑за дополнительных накладных расходов (сложение, управление повторяющимся разделением и объединением чисел и так далее) его преимущества по сравнению с алгоритмом начальной школы проявляются только тогда, когда числа становятся относительно большими. Например, Python — популярный язык программирования, который, как известно, хорошо обрабатывает целые числа любого размера. Если заглянуть в исходный код Python (поищите тут «Karatsuba»), то можно увидеть, что он основан на гибридном подходе. Для входных данных небольшого размера он использует школьную математику, но как только числа достигают примерно 630 десятичных разрядов, он переключается и применяет алгоритм Карацубы. Такое количество разрядов может показаться гигантским по меркам обывателя, но компьютеры работают с гораздо большими числами. (Техническое примечание: на большинстве современных машин Python хранит большие числа в системе счисления с основанием , поэтому указанный порог Карацубы в 70 цифр в системе счисления с основанием соответствует примерно 630 десятичным цифрам).

Алгоритм Карацубы дал старт продолжавшейся несколько десятилетий гонке за установлением предельной скорости умножения. Эта гонка завершилась в 2019 году, когда математики Дэвид Харви и Йорис ван дер Ховен описали чрезвычайно сложный алгоритм, превзошедший алгоритм Карацубы в разы больше, чем любой из предыдущих прорывов. Новый алгоритм работает за время O(n × log n). Здесь log обозначает логарифм n — функцию, которая растёт очень медленно. Это ошеломляющий результат. Функция n × log n лишь ненамного превышает само число n. Это означает, что вычисление произведения двух огромных чисел требует лишь немного больше времени, чем их сложение или даже простое считывание из памяти (для считывания всех n цифр числа требуется n вычислительных шагов).

Однако этот триумф сопровождается важной оговоркой. Точно так же, как алгоритм Карацубы превосходит школьный подход только при достаточно больших числах, алгоритм Харви‑ван дер Ховена не показывает преимущества, пока числа не становятся поистине «галактическими». В информатике «галактический алгоритм» — это формальный термин, обозначающий метод, который впечатляюще эффективен при работе с достаточно большими числами, но никогда не будет полезен на практике из‑за огромных размеров этих чисел.

Но даже с такой оговоркой это было переломным достижением. Оно закрепило за собой рекорд самого быстрого из известных методов умножения в теоретическом плане и могло бы открыть путь к алгоритмам, работающим за O(n × log n) шагов — не только в теории, но и на практике. Сегодня теоретики информатики полагают, что O(n × log n) — это максимально возможная скорость умножения, и формальное доказательство этого стало «святым Граалем» для этой узкой области математики. Но, как напоминает нам история, широкий консенсус — это не математическое доказательство. Гипотезы о пределе скорости умножения уже опровергались ранее.