Помните, как в школе умножали "столбиком"? Скажем, числа 52 и 37 умножают так:
Умножение двузначных чисел мы свели 1) к умножению однозначных (оно короткое), 2) к сложению, 3) и еще к сдвигу, эта операция настолько проста, что мы её и не замечаем. Она соответствует умножению на степень десятки, и «почти бесплатна»:
(50+2)×(30+7) = 5×3×100 + 2×3×10 + 5×7×10 + 2×7.
Умножение двух двузначных чисел требует четырех коротких умножений.
Умножение двух трехзначных чисел требует девяти коротких умножений.
И так далее.
Умножение двух N-значных чисел сводится к N² коротким умножениям (и ещё к сложениям и сдвигам).
Для компьютерных вычислений умножение – самая затратная по времени операция, а сложение и тем более сдвиг – нет; поэтому сложность алгоритма умножения длинных чисел оценивают числом коротких, «однозначных» умножений. (Внутри компьютера числа представляются не так, как в школьных тетрадках, основание счисления будет не 10, а какая-то степень двойки, но для оценки это непринципиально.)
Примерно в 1956 году А.Н.Колмогоров предположил, что алгоритм c N² “однозначными” умножениями – наилучший из всех возможных. В его семинаре участвовал молодой математик Анатолий Карацуба, который и опроверг гипотезу учителя. В 1960 году он придумал алгоритм, который работает быстрее.
Чтобы сосчитать (50+2)×(30+7), метод Карацубы требует только три коротких произведения: 5×3, 2×7 и (5+2)×(3+7).
Через них получается выражение для
2×3 + 5×7=(5+2)×(3+7)- 5×3-2×7.
А это все, что нужно знать, чтобы вычислить произведение:
(50+2)×(30+7) = 5×3×100 + (2×3 + 5×7)×10 + 2×7.
Нам потребовалось не N² операций, а только
Для умножения в столбик ручкой на бумаге этот метод неудобен. У него нет такой элегантной формы записи, им сложнее овладеть, да и выигрыша во времени в бытовых ситуациях он не дает. Но для компьютерного умножения очень длинных чисел это заметное улучшение.
Как это бывает в математике, после первого шага началась гонка за наилучшим результатом. Всегда приятно поставить рекорд: найти больше всех цифр числа π или самое большое простое число.
Немецкие математики Арнольд Шёнхаге и Фолькер Штрассен в 1971 году придумали, как использовать быстрое преобразование Фурье, чтобы умножать большие числа еще быстрее. Они свели задачу умножения чисел к задаче умножения многочленов, и применили к таким функциям быстрое преобразование Фурье. (По версии журнала Computing in Science & Engineering БПФ – один из 10 важнейших алгоритмов ХХ столетия.) Теперь можно было умножать за
операций. И в XX веке все компьютеры так и умножали. Но сами Арнольд Шёнхаге и Фолькер Штрассен выдвинули две гипотезы: 1) что можно умножать еще быстрее – за N log (N), и 2) что это уже нижняя граница, быстрее умножить не получится.
В 2007 году Мартин Фюрер предложил алгоритм еще шустрее, но который все же не достиг идеала в N log (N).
Его достигли в этом году Дэвид Харви и Йорис ван дер Ховен (DAVID HARVEY AND JORIS VAN DER HOEVEN). Они опубликовали два новых алгоритма, которые оба требуют N log (N) простых операций. Первый технически проще, но опирается на недоказанное предположение о простых числах в арифметических прогрессиях. Второй требует изощренной техники, но зато достигает идеала без всяких недоказанных предположений.
Первая гипотеза Шёнхаге и Штрассена таким образом доказана, а вторая еще ждет своих героев. Математики научились умножать быстро и еще быстрее, но пока не знают: правда ли, что быстрее уже некуда.