Быстрее, еще быстрее

Даже великие ученые иногда ошибаются. Когда в середине 1950-х годов советский математик Андрей Колмогоров высказал гипотезу: сложность перемножения N-значных чисел пропорциональна N². Всего через несколько лет его гипотеза была опровергнута, а чуть позже появился новый, еще более быстрый алгоритм, причем его создатели высказали гипотезы о том, что быстрое умножение чисел пропорционально N log (N) и это теоретический предел. Совсем недавно, похоже, этого предела удалось достичь. О том, в каких областях используется умножение по-настоящему больших чисел, как был достигнут предел скорости и нельзя ли его преодолеть, для британского издания The Conversation один из авторов недавнего открытия, австралийский математик Дейвид Харви, написал статью под названием «Мы нашли способ быстрее перемножать по-настоящему большие числа». Издание N + 1 предлагает своим читателям полный перевод этой статьи.

Мы нашли способ быстрее перемножать по-настоящему большие числа

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

В начальной школе нас учат, как умножить одно большое число на другое, — вот как в примере выше.

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

Но можно ли считать этот способ умножения двух больших чисел друг на друга наилучшим?

При перемножении больших чисел мы должны умножить каждую цифру первого множителя на каждую цифру второго множителя. Если каждый из множителей состоит из N цифр, то всего получается N² (или 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 измерениями. Это довольно трудно визуализировать, но с точки зрения математики это мало чем отличается от двухмерного преобразования.

Огромные, по-настоящему огромные числа

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

С другой стороны, мы надеемся улучшить его и приспособить для чисел с какими-нибудь миллиардами и триллионами знаков. Если нам это удастся, этот алгоритм может стать незаменимым инструментом в арсенале математических вычислений.

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

Лично я буду очень удивлен, если окажется что Шёнхаге и Штрассен ошибались. Но не следует забывать, что в свое время случилось с Колмогоровым. Математика порой способна преподносить сюрпризы.

Перевод с английского Дмитрия Иванова