Дэвид Харви, сотрудник университета Нового Южного Уэльса в Сиднее, и его французский коллега Йорис Ван дер Хэвен решили задачу, поставленную математиками еще полвека назад. Речь идет о доказательстве гипотезы Шёнхаге — Штрассена. Согласно этой гипотезе, возможен такой алгоритм перемножения целых N-значных чисел, что число шагов алгоритма с возрастанием числа не будет увеличиваться быстрее, чем N * logN.
Простейший алгоритм умножения знаком всем с начальной школы, это так называемое умножение в столбик. Чтобы перемножить два числа, надо по существу умножить каждую цифру первого числа на каждую цифру второго, а потом еще выполнить несколько сложений и расположить результаты в правильном порядке. Ключевой этап — перемножение цифр: если наши числа трехзначные, придется обратиться к таблице умножения 9 раз, а если пятизначные — 25 раз. В общем случае число таких процедур увеличивается пропорционально числу знаков в перемножаемых числах, возведенному в квадрат. И если эти числа достаточно велики, то количество шагов алгоритма становится поистине огромным.
В 1950-х годах советский математик Анатолий Карацуба обнаружил способ уменьшить сложность алгоритма умножения. В его алгоритме число шагов увеличивается не быстрее, чем N1,58 — это существенно меньше, чем N2. Впрочем, если читателю вздумается ознакомиться с алгоритмом Карацубы, он обнаружит, что при этом сам метод существенно сложнее обычного школьного умножения. Согласно оценкам, его преимущество проявляется, начиная с чисел, имеющих не менее 10 000 десятичных разрядов.
Десять лет спустя проблемой занялись два немецких математика, которые предложили еще более экономичный алгоритм — с числом шагов не больше чем N * logN * log(logN). Алгоритм Шёнхаге — Штрассена, однако, тоже не оптимален, эти же математики предположили, что возможно перемножать большие числа так, чтобы число шагов не росло быстрее чем N * logN. Однако ни предложить конкретный способ, ни даже доказать его возможность не удавалось вплоть до настоящего времени.
Именно эту задачу и решили Харви и Ван дер Хэвен. Они предложили способ построить именно такой алгоритм.
Насколько подобные математические приемы способны ускорить реальные вычисления? По словам Харви, чтобы перемножить два числа с миллиардом десятичных знаков, современному компьютеру понадобится около месяца. Применение алгоритма Шёнхаге — Штрассена позволит уложиться в 30 секунд. Алгоритм, способ построения которого предлагает сам Харви, справится с задачей еще быстрее. Более того, математики предполагают, что это, вероятно, и есть теоретически возможный предел скорости умножения, хотя строго доказать эту гипотезу им пока не удалось. Однако если это так, данную математическую задачу можно считать окончательно решенной.
Насколько большим должно быть число, чтобы алгоритм Харви — Ван дер Хэвена дал преимущество в скорости вычисления? «Понятия не имею», — честно отвечает Харви, однако в своей статье он приводит в качестве примера умножение, дающее результат 10214857091104455251940635045059417341952. Это действительно очень большое число: во всей видимой Вселенной, к примеру, содержится всего порядка 1080 элементарных частиц.
Однако тот факт, что столь большие числа не соответствуют количеству чего бы то ни было в реальном мире, вовсе не значит, что открытие математиков бесполезно. Умножение — неотъемлемая часть других вычислительных процедур, таких как деление или извлечение корней. Данный результат окажется полезным и тем, кто намерен вычислить много-премного знаков числа пи или, к примеру, расширить список известных человечеству простых чисел.
У этой работы есть еще одно интересное следствие. При обосновании преимуществ квантового компьютера нередко приводят в качестве примера алгоритмы шифрования. Эти алгоритмы часто построены на разложении очень больших чисел на множители. Квантовый алгоритм Шора справляется с этой задачей довольно легко, тогда как для классического алгоритма разложение достаточно большого числа потребует времени, сравнимого с возрастом Вселенной. Однако в этих примерах всегда неявно подразумевается, что эффективность классического алгоритма — величина, определенная раз и навсегда. Работа австралийского и французского математиков показывают, что это далеко не так. А вдруг математики будущего предложат настолько изящный классический способ разложения числа на множители, что существующие шифры легко можно будет взломать не только на квантовом, но и на классическом компьютере? Сравнение квантовых и классических алгоритмов некорректно, пока не показано, что и тот и другой действительно являются лучшими из теоретически возможных.
Остается добавить, что работа математиков пока опубликована онлайн, и их коллегам еще предстоит тщательно проверить все выкладки. Авторы выражают надежду, что они ничего не перепутали. Тем временем каждый из читателей имеет возможность самостоятельно проверить все вычисления и, возможно, найти в них ошибку.