Когда мы пишем очередной скрипт на Python или JS, умножение двух переменных кажется элементарной операцией стоимостью в один такт процессора (пока это не падает в продакшене с Out of Memory). Но что делать, если под капотом криптографической системы или распределенного блокчейна вам нужно перемножить числа размером в миллиарды бит? Обычный школьный столбик здесь бессилен, а поиск предела скорости арифметики веками занимал умы лучших математиков. Сегодня мы разберем прорыв, который переписал учебники информатики.

Введение: Фундаментальный предел арифметики

Умножение целых чисел — это базовая вычислительная операция, с которой начинается любое знакомство с программированием. Мы привыкли к школьному алгоритму «в столбик», который требует квадратичного времени O(n²), где n — количество цифр в числе. Для небольших чисел (в пределах машинного слова процессора) этот процесс происходит мгновенно за счет аппаратных инструкций CPU.

Однако в эпоху криптографии с открытым ключом, систем компьютерной алгебры и обработки огромных массивов данных возникает необходимость перемножать числа, состоящие из миллионов, миллиардов и даже триллионов битов. В таких масштабах алгоритм O(n²) становится узким местом. Возникает вопрос: каков абсолютный предел скорости умножения?

Долгое время барьером казалась сложность O(n log n). Этот рубеж казался фундаментальным, поскольку быстрые алгоритмы опираются на быстрое преобразование Фурье (Fast Fourier Transform — FFT), работающее за O(n log n). Однако математики Давид Харви (David Harvey) и Йорис ван дер Хувен (Joris van der Hoeven) опубликовали алгоритм с доказанной временной сложностью O(n log n). Эта статья посвящена тому, как устроен этот алгоритм и почему он важен для IT-индустрии.

Путь к этому открытию лежал через десятилетия упорной борьбы математиков с ограничениями вычислительной техники (примерно как попытки запустить Legacy-проект на свежей версии Node.js). Давайте проследим, как эволюционировал этот казалось бы незыблемый стек.

Исторический экскурс: от Карацубы до FFT

Чтобы понять революisонность результата Харви и ван дер Хувена, нужно оглянуться на историю развития алгоритмов умножения. До середины XX века человечество пользовалось методом «в столбик». Ситуация изменилась в 1960 году, когда советский математик Анатолий Карацуба предложил свой метод «разделяй и властвуй».

Алгоритм Карацубы разбивает два n-значных числа на половины. Вместо четырех умножений метод позволяет обойтись тремя, используя дополнительные сложения и вычитания. Его временная сложность составляет:

T(n) = 3T(n/2) + O(n) => O(n^(log_2 3)) ≈ O(n^1.585)

В 1971 году Арнольд Шёнхаге и Фолькер Штрассен совершили скачок, применив дискретное преобразование Фурье. Алгоритм Шёнхаге — Штрассена работал за время:

O(n log n log log n)

На протяжении почти полувека этот алгоритм оставался золотым стандартом для вычислений с огромными целыми числами (работает же, лучше не трогать!). Долгое время считалось, что множитель log log n неудаляем из-за природы переноса разрядов.

Избавиться от этого паразитного множителя удалось за счет принципиально иного подхода к структуре данных, о котором мы поговорим далее.

Как устроен новый алгоритм Харви — ван дер Хувена

Главный прорыв математиков заключается в обходе проблемы переноса разрядов (carry propagation). В классических подходах на базе FFT обработка переносов требовала дополнительных операций, которые и добавляли злополучный множитель log log n.

Вместо стандартного подходов авторы использовали:

  • Многомерное быстрое преобразование Фурье с быстрыми кольцевыми структурами.
  • Технику быстрой стабилизации коэффициентов для контроля переполнения разрядной сетки.
  • Оптимизированное разбиение полиномов высокой степени с комплексными коэффициентами.

За счет этого удалось снизить асимптотику до заветного предела:

O(n lo