Швидше, ще швидше

Навіть великі вчені іноді помиляються. Коли в середині 1950-х років математик Андрій Колмогоров висловив гіпотезу: складність перемноження N-значних чисел пропорційна N у квадраті. Усього через кілька років його гіпотеза була спростована, а трохи згодом з'явився новий, ще швидший алгоритм, причому його творці висловили гіпотези про те, що швидке множення чисел пропорційно до N log (N) і це теоретична межа. Зовсім недавно, схоже, цієї межі вдалося досягти. Про те, в яких областях використовується множення по-справжньому великих чисел, як було досягнуто межі швидкості і чи не можна її подолати австралійський математик Девід Гарві, написав статтю під назвою «Ми знайшли спосіб швидше перемножувати по-справжньому великі числа».

Ми знайшли спосіб швидше перемножувати по-справжньому великі числа

Перемножити два числа - легко, так?

У початковій школі нас вчать, як помножити одну велику кількість на іншу.

Способи множення, подібні до цього, з'явилися тисячі років тому, їх знали вже древні шумери та єгиптяни.

Але чи можна вважати цей спосіб множення двох великих чисел один на одного найкращим?

При перемноженні великих чисел ми маємо помножити кожну цифру першого множника на кожну цифру другого множника. Якщо кожен з множників складається з N цифр, то виходить N2 (або N × N) множень. У прикладі N = 3, тому потрібно зробити 3у квадраті = 9 операцій.

Приблизно 1956 року видатний математик Андрій Колмогоров висунув гіпотезу, що це і є найкращий з усіх можливих способів помножити одне число на інше.

Тобто незалежно від того, як саме ви вважаєте, обсяг роботи, яку вам доведеться виконати, буде пропорційний як мінімум Nу квадраті. Збільшіть множники вдвічі - і вам доведеться зробити в чотири рази більше обчислень.

Колмогоров був упевнений, що якщо існував би спосіб хоч трохи скорочуючий цей шлях, його, напевно, вже відкрили б. Як не крути люди перемножують числа протягом тисяч років.

Це чудовий приклад логічної помилки, відомої як «аргумент до незнання».

Швидший спосіб

Вже за кілька років гіпотеза Колмогорова була вражаюче спростована.

У 1960 році Анатолій Карацуба, на той час 23-річний студент-математик, відкрив хитрий трюк алгебри, що дозволив скоротити необхідну кількість множень.

Наприклад, щоб перемножити два чотиризначні числа, замість необхідних 4 у квадраті = 16 перемножень метод Карацуби дозволяє обійтися всього дев'ятьма. При застосуванні його методу збільшення множників вдвічі вимагатиме зробити лише втричі більше обчислень.

Це давало вражаючу економію часу у міру того, як довжина множників зростала. У випадку з числами завдовжки тисячі знаків метод Карацуби вимагав у 17 разів менше обчислень, ніж при звичайному множенні.

Але навіщо взагалі комусь треба перемножувати такі великі числа?

Насправді ці операції застосовуються часто-густо. Одна з найбільш наочних та економічно значущих областей – криптографія.

Великі числа у нашому житті

Щоразу, коли ви встановлюєте захищене інтернет-з'єднання, - наприклад, заходите в особистий кабінет на сайті свого банку або задаєте пошуковий запит, - ваш пристрій здійснює запаморочливу кількість обчислень, у тому числі з числами завдовжки сотні, а то й тисячі знаків.

Швидше за все, ваш пристрій використовує трюк Карацуби, щоб упоратися з цією арифметикою. Це все частина дивовижної програмної екосистеми, що дозволяє нашим веб-сторінкам завантажуватися якнайшвидше.

Але для деяких менш доступних широкому розумінню цілей математикам доводиться перемножувати куди більші числа, що складаються з мільйонів, мільярдів і навіть трильйонів знаків. Для таких грандіозних обсягів навіть алгоритм Карацуби працює надто повільно.

Справжній прорив стався 1971 року, коли вийшла робота німецьких математиків Арнольда Шенхаге та Фолькера Штрассена. Вони показали, як можна використовувати недавно відкрите швидке перетворення Фур'є (FFT) для перемноження величезних багатозначних чисел. Сьогодні їхній метод повсюдно використовується для обробки чисел довжиною в мільярди знаків.

Швидке перетворення Фур'є стало одним із найважливіших алгоритмів ХХ століття. Одна з повсякденних областей його застосування — цифрове аудіо: коли ви слухаєте MP3-файл або музичний стрімінговий сервіс, або онлайн-радіо, саме FFT займається декодуванням звуку за кадром.

Ще швидший спосіб?

У своїй роботі 1971 Шенхаге і Штрассен висунули ще одну разючу гіпотезу. Щоб пояснити її суть, мені доведеться ненадовго поринути у деталі.

Перша частина їх гіпотези говорить: повинен бути працюючий спосіб перемножити N-значні числа за допомогою деякої кількості фундаментальних операцій, здебільшого пропорційних N log (N) (тобто N разів за натуральним логарифмом від N).

Їхній власний алгоритм не до кінця досягнув цієї мети: у них вийшло N, помножене на log (N) та помножене на log (log N) (логарифм від логарифму від N). Проте, чисто інтуїтивно вони відчували, що щось упускають і що N log (N) можна досягти.

За десятиліття, що минули після 1971 року, кільком дослідникам вдалося покращити алгоритм Шенхаге та Штрассена. Зокрема, алгоритм, розроблений Мартіном Фюрером в 2007 році, дражливо близько підійшов до значення N log (N).

Друга (і куди складніша) частина їх гіпотези свідчить, що N log (N) є фундаментальною межею швидкості обчислень - що жоден інший алгоритм не дозволить проводити перемноження великих чисел швидше.

Звучить знайомо, чи не так?

Чи досягнуто межу?

Кілька тижнів тому ми з Йорісом ван дер Говеном опублікували результати дослідження, що описують новий алгоритм множення, що досягає, нарешті, заповітного значення N log (N) і тим самим підтверджує першу, просту частину гіпотези Шенхаге і Штрассена.

Наше дослідження ще не пройшло рецензування, тому деякі сумніви залишаються. Це стандартна практика математиків — поширювати результати дослідження ще до того, як отримано фінальні рецензії.

Замість використання одномірного швидкого перетворення Фур'є — базової передумови всіх робіт із цієї проблеми починаючи з 1971 року — наш алгоритм використовує багатовимірні FFT. У них немає нічого нового: широко поширений формат зображень JPEG залежить від двовимірного FFT, а тривимірні FFT широко застосовуються у фізиці та інженерній справі.

Ми у своєму дослідженні використовували FFT з 1729 вимірами. Це досить важко візуалізувати, але з точки зору математики мало чим відрізняється від двомірного перетворення.

Величезні, по-справжньому величезні числа

Новий алгоритм у своєму нинішньому вигляді не дуже підходить для конкретних обчислень, тому що доказ, наведений у нашій статті, працює лише для абсурдно великих чисел. Якщо кожен знак одного з таких чисел записати на атомі водню, то в найближчому Всесвіті не вистачить місця, щоб воно вмістилося цілком.

З іншого боку, ми сподіваємося покращити його та пристосувати для чисел з якимись мільярдами та трильйонами знаків. Якщо нам це вдасться, цей алгоритм може стати незамінним інструментом у арсеналі математичних обчислень.

Якщо гіпотеза Шенхаге і Штрассена вірна цілком, тоді, з теоретичної погляду, новий алгоритм стане кінцевим пунктом цього шляху — нічого досконалішого придумати не вдасться.

Особисто я буду дуже здивований, якщо виявиться, що Шенхаге і Штрассен помилялися. Але не слід забувати, що свого часу сталося з Колмогоровим. Математика часом здатна підносити сюрпризи.