Математика всегда считалась одной из самых сложных дисциплин, особенно когда дело доходило до умножения больших чисел. Многие школьники и студенты помнят, как утомительно было выполнять долгие вычисления «столбиком». Но современные учёные продолжают искать более быстрые и эффективные методы, способные упростить этот процесс не только для учебников, но и для сложнейших вычислений в науке и технологиях. Именно таким открытием стало доказательство гипотезы, выдвинутой ещё в XX веке, которое может изменить представление о том, как работают вычисления с гигантскими числами.
Что вы узнаете из этой истории
Ещё в 1971 году немецкие математики Арнольд Шёнхаге и Фолькер Штрассен предсказали существование более быстрого алгоритма для умножения больших чисел. Однако их идея оставалась недоказанной десятилетиями.
Недавно математики из Австралии и Франции сумели доказать, что такой алгоритм действительно существует. Это открытие сделает операции умножения и другие виды вычислений гораздо эффективнее.
Прорыв может изменить подход к задачам, связанным с огромными числами: от вычисления миллиардов знаков числа до работы с гигантскими простыми числами.
Сложное умножение и поиск нового метода
С самого начала школьной программы сложное умножение воспринималось как настоящая головная боль. Тем не менее доцент Университета Нового Южного Уэльса в Сиднее нашёл способ умножать гигантские числа быстрее и эффективнее, чем привычное «столбиком», которому обучают детей с раннего возраста.
«Говоря более строго, мы доказали гипотезу Шёнхаге и Штрассена 1971 года о сложности умножения целых чисел», — поясняет доцент Дэвид Харви в одном из своих видео.
Алгоритм Шёнхаге–Штрассена
Алгоритм Шёнхаге–Штрассена, созданный двумя немецкими математиками, с 1971 по 2007 год считался самым быстрым методом умножения. В 2007 году появился ещё более быстрый способ, но он используется крайне редко.
Учёные Шёнхаге и Штрассен ещё полвека назад предположили: должен существовать алгоритм, который умножает n-значные числа, используя примерно n × log(n) элементарных операций. Именно Харви и его коллегам удалось впервые доказать, что такой алгоритм существует на практике.
Пример с числами
Чтобы объяснить идею, Харви приводит пример: 314 умножить на 159. На первый взгляд это большое уравнение, но в реальной жизни приходится иметь дело с числами куда масштабнее.
В привычном методе каждый знак одного числа умножается на все знаки другого. Затем результаты складываются. Например:
9 умножается на 4, 1 и 3;
потом 5 умножается на 4, 1 и 3;
и так продолжается для всех цифр.
В итоге получается 9 отдельных произведений.
Такой метод называют n² (n в квадрате), потому что нужно выполнить n × n операций. Ответ будет верным, но процесс занимает слишком много времени. Шёнхаге и Штрассен предложили метод быстрее, чем n². Однако он требовал решения задачи, связанной с n × log(n), и долгое время казался недосягаемым.
Роль логарифмов
Для многих уже одно слово «логарифм» способно вызвать тоску, как на уроках алгебры. Но напомним: логарифм — это инструмент, помогающий разбирать показатели степеней. Он объясняет, каким образом число возводится в квадрат, куб или ещё более высокую степень.
Например, 2⁵ равно 32. А в логарифмической форме это будет записано как log₂(32) = 5. Сначала кажется сложно, но именно логарифмы становятся незаменимыми, когда речь идёт о действительно огромных числах.
Преимущества нового алгоритма
По словам Харви, метод Шёнхаге–Штрассена работает очень быстро. Если компьютер будет использовать школьный метод n² для двух чисел с миллиардами знаков, то вычисления займут несколько месяцев. Но с алгоритмом Шёнхаге–Штрассена результат появится всего за 30 секунд.
Однако если числа становятся ещё больше — триллионы и более, — то новый алгоритм, разработанный Харви и его коллегой Жорисом ван дер Хувеном из Политехнической школы во Франции, решает задачу ещё быстрее.
«Это значит, что можно выполнять не только умножение, но и деление, извлечение квадратного корня и другие операции гораздо эффективнее, — объясняет Харви. — Также можно вычислять знаки числа быстрее, чем раньше. А ещё метод полезен для задач, связанных с огромными простыми числами».
Заключение
Учёный добавляет, что поиск такого алгоритма длился почти 50 лет. Не было никакой гарантии, что попытки увенчаются успехом. Теоретически могло оказаться, что Шёнхаге и Штрассен ошибались, и алгоритм попросту невозможен.
«Но теперь мы точно знаем, что это реально», — подытоживает Харви.
