В школе дети учат таблицу умножения. Запоминают её наизусть. Удачи тебе с трёхзначными числами! Тут в дело вступают алгоритмы. Ты выстраиваешь цифры в столбик. Умножаешь построчно. Тысячелетиями мы считали, что лучше этого ничего не придумаешь. Это медленно. Жутко медленно для больших объёмов данных. Но в 1960 году всё изменил 23-летний парень. Загадка скорости умножения до сих пор остаётся открытой.
Почему это важно
Умножение — это не просто школьное задание. Оно заставляет работать весь интернет. Шифрование, искусственный интеллект, обработка звука. Всё это опирается на умножение. Интенсивное умножение. Когда тебе нужно умножать огромные числа миллионы раз в секунду, каждый шаг имеет значение. Даже незначительный рост эффективности экономит миллиарды.
Посмотрите на школьный метод. Два разряда означают четыре умножения однозначных чисел. Три разряда? Девять. Он масштабируется квадратично. Удвой длину числа — работа увеличится вчетверо. Удвой ещё раз — работа вырастет в 16 раз. Компьютерные учёные не считают секунды. Железо и так становится быстрее. Они считают шаги. Мы называем это записью «О большое» (Big O notation). Школьный метод — это O(n²). Квадратичный. Если длина числа вырастет в 1000 раз, объём работы взорвётся в миллион раз.
Нагрузка возрастает пропорционально квадрату количества разрядов.
С древних времён математические гении считали этот квадратичный предел законом природы. Андрей Колмогоров, советская легенда, в 1960 году в своей лекции поставил на это своё имя. Он сказал студентам МГУ: «Это занимает O(n²)». Это было формальное предположение. Бросок вызова. Ждите, кто-нибудь докажет это или опровергнет.
Пропшла всего неделя. Анатолий Карацуба сидел в аудитории. Ему было 23 года. Он вернулся с доказательством того, что Колмогоров ошибся. Профессор был в шоке. Колмогоров буквально сам написал статью для престижного журнала, но поставил имя Карацубы как автора. Юноша узнал об этом только тогда, когда по почте пришли репринты.
Хитрость
Карацуба понял простую, но глубокую вещь. Умножения — дорогие операции. Сложения — дешёвые. Почему бы не поменять их местами?
Возьмём 12 × 34.
Разбейте их.
12 — это 10 + 2.
34 — это 30 + 4.
Традиционно вы делаете четыре умножения:
1×3
1×4
2×3
2×4
Карацуба нашёл способ сделать это за три умножения.
Вычислите первую часть: 1×3 = 3.
Вычислите последнюю часть: 2×4 = 8.
Теперь середина. Обычно вы бы сделали (1×4) + (2×3). Два умножения. Вместо этого сложите первые числа: 1+2=3. Сложите последние: 3+4=7. Умножьте эти суммы: 3×7=21. Вычтите уже известные части. 21 — 3 — 8 = 10.
Вуаля. Вы получили средний член за одно дополнительное умножение.
Окупается ли это?
Для малых чисел — нет. Накладные расходы на разбиение и сложение стоят вам дороже.
Но для 1234 × 5678? Разделите пополам. Рекурсия. Разделите эти половины. Делайте снова. Экономия складывается.
Сложность алгоритма падает примерно до O(n^1.585).
Для тысячезначных чисел раньше требовался миллион умножений однозначных цифр. Теперь нужно меньше 57 000 шагов. Огромная разница.
Это не просто теория. Это есть в Python.
Python использует стандартную школьную математику для малых входных данных. Плавненько.
Но как только вы достигаете примерно 63 десятичных разрядов (в зависимости от разрядной сетки машины), Python переключает тумблер. Включается Карацуба. Вы этого не видите. Но он там. Обрабатывает ваше шифрование.
Галактические алгоритмы
Гонка продолжалась десятилетиями. Можно ли идти ещё быстрее?
2019 год принёс новейший сюрприз. Дэвид Харви и Жорис ван дер Хёвен опубликовали алгоритм, который оставляет Карацубу далеко позади.
O(n log n).
Прочитайте это ещё раз.
Логарифмы растут невероятно медленно.
n log n лишь ненамного больше, чем n.
По сути, умножение двух огромных чисел теперь занимает примерно столько же времени, сколько чтение самих чисел.
Это ошеломляет. Кажется, что теоретический предел уже достигнут.
Или, может быть, нет.
Вот подвох.
Он не работает для чисел, которые нас интересуют.
Алгоритм Харви и ван дер Хёвена становится быстрее, чем у Карацубы, только когда числа становятся очень большими. Не «большими, как номер кредитной карты». Галактически большими.
В компьютерной науке для этого есть термин: галактический алгоритм.
Красивая теория. Ноль практической пользы. Требуемые числа больше, чем сумма всех цифровых транзакций в истории человечества.
Мы застряли посередине.
Используем трюки из 60-х годов для большинства наших повседневных вычислений.
Носим костюмы 21 века поверх математики 20 века.
Используем ли мы когда-нибудь O(n log n) в реальном мире?
Возможно, когда будем обрабатывать наборы данных размером с галактики.
До тех пор мы ждём.
Следующего трюка.
Или лучшего оборудования, которое скроет нашу лень.
Ответ может быть всё ещё квадратичным.
Он может быть линейным.
Мы пока не знаем.
