Лучше, чем в столбик: новый способ перемножать большие числа

Австралийский математик нашел максимально эффективный алгоритм перемножения больших чисел.

Дэвид Харви, сотрудник университета Нового Южного Уэлльса в Сиднее, и его французский коллега Йорис Ван дер Хэвен, решили задачу, поставленную математиками еще полвека назад. Речь идет о доказательстве гипотезы Шёнхаге-Штрассена. Согласно этой гипотезе, возможен такой алгоритм перемножения целых N-значных чисел, что число шагов алгоритма с возрастанием числа не будет увеличиваться быстрее, чем N * logN.

Простейший алгоритм умножения знаком всем с начальной школы: это так называемое «умножение в столбик». Чтобы перемножить два числа, надо по существу умножить каждую цифру первого числа на каждую цифру второго, а потом еще выполнить несколько сложений и расположить результаты в правильном порядке. Ключевой этап — перемножение цифр: если наши числа трехзначные, придется обратиться к таблице умножения 9 раз, а если пятизначные — 25 раз. В общем случае число таких процедур увеличивается пропорционально числу знаков в перемножаемых числах, возведенному в квадрат. И если эти числа достаточно велики, то количество шагов алгоритма становится поистине огромным.

Фото: Depositphotos
Фото: Depositphotos

В 1950-х гг. Советский математик Анатолий Карацуба обнаружил способ уменьшить сложность алгоритма умножения. В его алгоритме число шагов увеличивается не быстрее, чем N<sup>1,58</sup> — это существенно меньше, чем N<sup>2</sup>. Впрочем, если читателю вздумается ознакомиться с алгоритмом Карацубы, он обнаружит, что при этом сам метод существенно сложнее обычного школьного умножения. Согласно оценкам, его преимущество проявляется начиная с чисел, имеющих не менее 10 000 десятичных разрядов.

Десять лет спустя проблемой занялись два немецких математика, которые предложили еще более экономичный алгоритм — с числом шагов не больше чем N * logN * log (logN). Алгоритм Шёнхаге-Штрассена, однако, тоже не оптимален: эти же математики предположили, что возможно перемножать большие числа так, чтобы число шагов не росло быстрее чем N * logN. Однако ни предложить конкретный способ, ни даже доказать его возможность не удавалось вплоть до настоящего времени.

Именно эту задачу и решили Харви и Ван дер Хэвен. Они предложили способ построить именно такой алгоритм.

Насколько подобные математические приемы способны ускорить реальные вычисления? По словам Харви, чтобы перемножить два числа с миллиардом десятичных знаков, современному компьютеру понадобится около месяца. Применение алгоритма Шёнхаге-Штрассена позволит уложиться в 30 секунд. Алгоритм, способ построения которого предлагает сам Харви, справится с задачей еще быстрее. Более того, математики предполагают, что это, вероятно, и есть теоретически возможный предел скорости умножения, хотя строго доказать эту гипотезу им пока не удалось. Однако если это так, данную математическую задачу можно считать окончательно решенной.

Фото: Natalie Choi / UNSW
Фото: Natalie Choi / UNSW
Перемножить два числа с миллиардом десятичных знаков, современному компьютеру понадобится около месяца. Применение алгоритма Шёнхаге-Штрассена позволит уложиться в 30 секунд.

Насколько большим должно быть число, чтобы алгоритм Харви-Ван-дер-Хэвена дал преимущество в скорости вычисления? «Понятия не имею», — честно отвечает Харви, однако в своей статье он приводит в качестве примера умножение, дающее результат 10<sup>214857091104455251940635045059417341952</sup>. Это действительно очень большое число: во всей видимой Вселенной, к примеру, содержится всего порядка 10<sup>80</sup> элементарных частиц.

Однако тот факт, что столь большие числа не соответствуют количеству чего бы то ни было в реальном мире, вовсе не значит, что открытие математиков бесполезно. Умножение — неотъемлемая часть других вычислительных процедур, таких как деление или извлечение корней. Данный результат окажется полезным и тем, кто намерен вычислить много-премного знаков числа «пи» или, к примеру, расширить список известных человечеству простых чисел.

У этой работы есть еще одно интересное следствие. При обосновании преимуществ квантового компьютера нередко приводят в качестве примера алгоритмы шифрования. Эти алгоритмы часто построены на разложении очень больших чисел на множители. Квантовый «алгоритм Шора» справляется с этой задачей довольно легко, тогда как для классического алгоритма разложение достаточно большого числа потребует времени, сравнимого с возрастом Вселенной. Однако в этих примерах всегда неявно подразумевается, что эффективность классического алгоритма — величина, определенная раз и навсегда. Работа австралийского и французского математиков показывают, что это далеко не так. А вдруг математики будущего предложат настолько изящный классический способ разложения числа на множители, что существующие шифры легко можно будет взломать не только на квантовом, но и на классическом компьютере? Сравнение квантовых и классических алгоритмов некорректно, пока не показано, что и тот и другой действительно являются лучшими из теоретически возможных.

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

Это тоже интересно: