Два математика из Австралии и Франции, решая алгоритмическую головоломку, которая почти полвека озадачивала величайших математиков, разработали новый способ умножения. Он позволит значительно сократить время вычисления произведения больших чисел. Однако их решение требует подтверждения других математиков.
Проблемы традиционного умножения
Для большинства из нас способ умножения относительно небольших чисел заключается в запоминании невероятно удобной таблицы умножения, впервые предложенной вавилонянами около 4000 лет назад. Но что, если числа будут больше? В этом случае (конечно, при условии, что у нас отсутствует калькулятор или компьютера большинство из нас обратится к умножению в столбик - еще одному полезному и надежному способу умножения любых двух чисел, которому учат в начальной школе.
Однако у этого метода есть одна проблема: он требует времени. Причина в том, что для каждой отдельной цифры в каждом числе нужно выполнить отдельную операцию умножения, а затем сложить все результаты вычислений.
Это не представляет большой проблемы для обычных людей, которые, как правило, редко прибегают к умножению в столбик. Однако с этим недостатком хорошо знакомы школьники, кропотливо выполняющие расчеты, изучая магию умножения.
Что еще более важно, это проблема для компьютеров, поскольку их собственные узкие места в выполнении вычислений налагаются пределами абстрактной математики, которую мы сами можем понять. По сути, умножение столбиком - это алгоритм, но он не очень эффективный, поскольку неизбежно является трудоемким процессом.
Сложность вычислений
Как оказалось, у математиков есть способ вычислить, насколько сложным является умножение в столбик.
Как объясняет математик Дэвид Харви из Университета Нового Южного Уэльса в Австралии, в умножении, где оба числа состоят из трех цифр (n = 3), количество отдельных операций умножения фактически равно 9, то есть n2.
Проблема заключается в том, что по мере того, когда числа становятся больше, объем вычислений также увеличивается, поскольку всегда равен квадрату числа разрядов множителей.
История оптимизации вычислений
Несмотря на свою низкую эффективность, алгоритм умножения в столбик до 1960-х годов был фактически самым лучшим, пока советский математик Анатолий Карацуба не открыл возможность сокращения числа операций до n1,58496.
Десять лет спустя пара немецких математиков совершила еще один прорыв в математике. Они на основе метода быстрого преобразования Фурье разработали алгоритм Шенхаге-Штрассена, который предполагал возможность дальнейших уточнений.
«Они предсказали, что должен существовать алгоритм, который умножает n-значные числа, используя, по существу, n * log (n) базовых операций», - объясняет Харви. - «Наша статья дает первый известный пример алгоритма, который достигает этого».
Преимущества нового алгоритма
По мнению исследователей, умножение двух чисел с миллиардами цифр обычным методом требует месяцев работы компьютера. При использовании алгоритма Шенхаге-Штрассена это займет менее 30 секунд, а новое решение позволяет еще больше ускорить этот процесс и теоретически может стать самым быстрым алгоритмом умножения, который математически возможен.
«В этом смысле наша работа, как ожидается, станет окончательным решением этой проблемы, хотя мы пока не знаем, как это строго доказать», - говорит Дэвид Харви. - «Люди охотились за этим алгоритмом почти 50 лет. Кому-то, в конечном итоге, должно было повезти».
Область применения алгоритма
Стоит отметить, что новый алгоритм будет полезен только для умножения очень больших чисел. Насколько больших?
«Мы понятия не имеем», - объясняют исследователи, хотя в примере, который они приводят в статье, используется 10214857091104455251940635045059417341952, что является очень, очень, очень большим числом.
Мировое математическое сообщество все еще проверяет новое открытие, которые еще не прошло рецензирование, но уже произвело много шума.
«Я был очень удивлен, что это было сделано», - сказал ученый-теоретик Мартин Фюрер из Университета штата Пенсильвания. Он пытался обновить алгоритм Шенхаге-Штрассена более десяти лет назад, но в итоге прекратил работу, поскольку эта задача показалось ему совершенно безнадежной.
В ожидании проверки
Теперь надежда восстановлена, если другие математики смогут проверить работу исследователей.
«Если результат окажется верным, то это будет главным достижением в теории вычислительной сложности», - считает математик и ученый Фредрик Йоханссон из Института математики Бордо. - «Новые идеи в этой работе, вероятно, вдохновят на дальнейшие исследования и могут привести к практическим улучшениям в будущем».
Тем временем Харви и его соавтор Йорис ван дер Хувен из Французской политехнической школы говорят, что их алгоритм должен быть оптимизирован, и они надеются, что они ничего не напутали в своем доказательстве.
«Большая часть работы убедила нас в том, что он действительно правильный», - говорит Харви. - «Я все еще боюсь, что он может оказаться неверным».
