Помните, как в школе умножали "столбиком"? Скажем, числа 52 и 37 умножают так:
Умножение двузначных чисел мы свели 1) к умножению однозначных (оно короткое), 2) к сложению, 3) и еще к сдвигу, эта операция настолько проста, что мы её и не замечаем. Она соответствует умножению на степень десятки, и «почти бесплатна»:
(50+2)×(30+7) = 5×3×100 + 2×3×10 + 5×7×10 + 2×7.
Умножение двух двузначных чисел требует четырех коротких умножений.
Умножение двух трехзначных чисел требует девяти коротких умножений.
И так далее.
Умножение двух N-значных чисел сводится к N² коротким умножениям (и ещё к сложениям и сдвигам).
Для компьютерных вычислений умножение – самая затратная по времени операция, а сложение и тем более сдвиг – нет; поэтому сложность алгоритма умножения длинных чисел оценивают числом коротких, «однозначных» умножений. (Внутри компьютера числа представляются не так, как в школьных тетрадках, основание счисления будет не 10, а какая-то степень двойки, но для оценки это непринципиально.)
Анатолий Карацуба в 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 веке все компьютеры так и умножали. Но теперь существуют алгоритмы ещё шустрее