Математична загадка, яка все ще не вирішена
У школі діти навчають таблицю множення. Запам’ятовують її напам’ять. Успіху тобі з тризначними числами! Тут у справу вступають алгоритми. Ти вибудовуєш цифри у стовпчик. Примножуєш рядково. Тисячоліттями ми вважали, що краще за це нічого не придумаєш. Це повільно. Моторошно повільно для великих обсягів даних. Але 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) у реальному світі?
Можливо, коли оброблятимемо набори даних розміром з галактики.
До того часу ми чекаємо.
Наступний трюк.
Або найкращого обладнання, яке приховає нашу лінощі.
Відповідь може бути все ще квадратичною.
Він може бути лінійним.
Ми поки що не знаємо.
