Обзор СМИ
Умножить большие числа быстро и по-новому: доказана гипотеза Шёнхаге — Штрассена
Знакомое со школы умножение в столбик предполагает умножение каждой цифры первого числа на каждую цифру второго, далее несколько сложений и расположение результата в правильном порядке. Число процедур увеличивается пропорционально числу знаков в перемножаемых числах, возведенному в квадрат. Для больших чисел количество шагов алгоритма становится практически огромным.
В середине прошлого века советский математик Анатолий Карацуба нашел способ уменьшить сложность алгоритма умножения. В нем число шагов увеличивается не быстрее, чем N1,58, что существенно меньше, чем N2. Но метод сложный, и преимущество проявляется, начиная с чисел, имеющих не менее 10000 десятичных разрядов.
Затем проблемой занялись два немецких математика, предложившие еще более экономичный алгоритм — с числом шагов не больше, чем N * logN * log(logN) – алгоритм Шёнхаге-Штрассена. Но ни предложить конкретный способ, ни даже доказать его возможность не удавалось вплоть до настоящего времени. Именно эту задачу и решили Харви и Ван дер Хэвен, предложив способ построения именно такого алгоритма.
По словам Харви, чтобы перемножить большие числа с миллиардом десятичных знаков обычным способом современному компьютеру понадобится почти месяц. С применение алгоритма Шёнхаге-Штрассена – 30 секунд. А алгоритм, способ построения которого предложили Харви и Ван дер Хэвен, справится с задачей еще быстрее. Математики предполагают, что это и есть теоретически возможная предельная скорость умножения. Строго доказать эту гипотезу им пока не удалось, но если это так, данную математическую задачу можно считать окончательно решенной.