Математики до сих пор не знают, как быстрее всего перемножать числа
Школьный способ умножения столбиком требует порядка n² элементарных умножений для n-значных чисел, и веками считалось, что быстрее в принципе нельзя. В 1960 году советский математик Андрей Колмогоров сформулировал это как формальную гипотезу на семинаре в МГУ. Через неделю 23-летний студент Анатолий Карацуба, сидевший на том семинаре, гипотезу опроверг. Курьёзная деталь: сам Карацуба статью не писал, доказательство оформил и подал в печать Колмогоров, указав Карацубу единственным автором; тот узнал о публикации, только получив по почте оттиски из «Докладов АН СССР».
Идея Карацубы, менять дорогие умножения на дешёвые сложения. Сложение n-значных чисел занимает O(n) шагов (один проход по цифрам), тогда как умножение столбиком, O(n²). При умножении двух двузначных чисел (например, 12 × 34) школьный метод требует четырёх умножений однозначных цифр. Карацуба показал: если сначала посчитать крайние произведения (ac и bd), то среднее слагаемое (ad + bc) можно получить одним дополнительным умножением по формуле (a+b)×(c+d) − ac − bd, а не двумя отдельными. Экономия одного умножения из четырёх кажется скромной, но при рекурсивном применении, числа делятся пополам, потом ещё пополам и так далее, эффект накапливается: перемножение двух тысячезначных чисел школьным методом требует около миллиона элементарных умножений, а по Карацубе, менее 57 000. Итоговая сложность алгоритма, примерно O(n^1.585) против O(n²). Приём давно работает на практике: в реализации больших целых чисел в Python алгоритм Карацубы включается для чисел длиннее примерно 630 десятичных цифр (в самом Python порог задан как 70 цифр в base 2^30).
Открытие Карацубы запустило многолетнюю гонку за предел скорости умножения. В 2019 году математики Дэвид Харви и Жорис ван дер Хувен описали алгоритм со сложностью O(n × log n), асимптотически на порядок быстрее всего, что было раньше, и очень близко к теоретическому минимуму (сама операция чтения n цифр числа требует n шагов). Но у результата есть существенная оговорка: это «галактический алгоритм», термин для методов, которые эффективны только на астрономически огромных числах и никогда не будут полезны на практике, потому что накладные расходы (рекурсивные разбиения, пересборка) окупаются лишь при нереалистично больших входных данных. Сегодня в теоретической информатике широко считается, что O(n × log n), это и есть абсолютный предел скорости умножения, а доказать это формально стало задачей-граалем узкой области математики. Но, как показывает история самого умножения, устоявшийся консенсус, ещё не доказательство: гипотезы о пределе скорости умножения уже опровергали раньше.
Ключевые факты
- В 1960 году Андрей Колмогоров выдвинул гипотезу, что O(n²), фундаментальный предел скорости умножения чисел; через неделю 23-летний студент Анатолий Карацуба гипотезу опроверг.
- Приём Карацубы: менять умножения на сложения через алгебраическое тождество (a+b)×(c+d) − ac − bd, рекурсивно применённое к разбиению чисел, итоговая сложность около O(n^1.585).
- Доказательство Карацубы формально опубликовал сам Колмогоров, указав Карацубу единственным автором; тот узнал о статье только получив оттиски по почте.
- Алгоритм Карацубы уже работает на практике, например, в Python он включается при перемножении целых чисел длиннее примерно 630 десятичных цифр.
- В 2019 году Дэвид Харви и Жорис ван дер Хувен нашли алгоритм со сложностью O(n × log n), но это «галактический алгоритм»: он эффективен только на непрактично огромных числах, а доказать, что это абсолютный теоретический предел, до сих пор не удалось.
Почему это важно
Умножение, базовая операция для шифрования, робототехники, ИИ, обработки звука и почти всего, чем занимаются процессоры; на масштабе миллиардов операций даже небольшой выигрыш в эффективности алгоритма превращается в реальную экономию вычислительных ресурсов. История также показывает, что интуитивно «очевидный» школьный метод умножения полтора века считался пределом возможного, пока студент за неделю не доказал обратное, а спустя полвека после этого рекорд снова переписали.
Кому это важно
В первую очередь, теоретикам вычислительной сложности и разработчикам библиотек для работы с большими числами (криптография, системы компьютерной алгебры, языки с произвольной точностью вроде Python), где выбор порогового алгоритма напрямую влияет на скорость реальных вычислений. Также, тем, кто интересуется историей математики и тем, как формальные гипотезы опровергаются или подтверждаются десятилетиями.
Как это применить
Алгоритм Карацубы, не музейный экспонат, а рабочий инструмент: он встроен, например, в реализацию длинной арифметики Python и активируется автоматически для чисел длиннее ~630 десятичных цифр, ускоряя реальные вычисления. Алгоритм Харви, ван дер Хувена (O(n × log n)) в практическом коде пока применять некому: это «галактический алгоритм», который выигрывает лишь на числах астрономической длины, поэтому напрямую в софт его переносить рано.
Можно ли доверять
Оба результата опубликованы и признаны математическим сообществом: доказательство Карацубы вышло в «Докладах Академии наук СССР» в 1960 году, работа Харви и ван дер Хувена, в 2019-м и прошла проверку профильных специалистов. Сомнений в корректности самих алгоритмов нет; открытым остаётся другой вопрос, является ли O(n × log n) действительно теоретическим пределом, и это именно недоказанная гипотеза, а не спорный факт.
Риски и подводные камни
Легко перепутать «самый быстрый из известных алгоритмов» с «самым быстрым из возможных», то, что O(n × log n) сейчас считается пределом, не доказано формально, и история уже знает случай, когда «незыблемая» гипотеза о пределе скорости умножения продержалась ровно до одного семинара. Отдельная ловушка, считать открытие 2019 года практически применимым: алгоритм Харви и ван дер Хувена «галактический» и не даст ускорения в реальном софте на числах разумного размера.
«В информатике «галактическим алгоритмом» формально называют метод, который впечатляюще эффективен на достаточно больших числах, но никогда не будет полезен на практике, потому что эти числа слишком велики.»
— Scientific American