Ещё тысячелетия назад люди научились умножать числа "в столбик", тратя
O(n^2) операций. Однако, потом произошёл сюжетный поворот. Далее пересказываю его, опираясь на достоверный источник - Википедию.Итак, некий старпёр из МГУ по имени Андрей Колмогоров в 1960 году проводил математический семинар. На нём он сказал: "Мы уже тысячелетиями знаем про столбик, но так и не нашли ничего быстрее. Наверное, это и есть теоретически оптимальный алгоритм для такой операции".
На семинаре присутствовал 23-летний Толян. В отличие от Колмогорова, Толян в математике разбирался и на авторитетные мнения срал с крыши небоскрёба. Уже через неделю он предложил новый быстрый метод умножения.
Для начала числа нужно разложить "пополам" в виде выражения
ax+b, где x это "круглое число", примерно равное корню из числа. Например, 11113333 = 1111 * 10^4 + 3333. То есть a и b это числа в 2 раза короче оригинального. Мы хотим умножить
ax + b и cx + d. (ax + b)(cx + d) = ac x^2 + (ad + bc) x + bd. Так, умножение 2 чисел длиной N мы превратили в 4 умножения длиной N/2 и парочку линейных операций.И тут Толян заметил fun fact:
ad + bc = ad + bc + ac + bd - ac - bd = (a+b)(c+d) - ac - bd. ac и bd мы уже умножаем и так для других коэффициентов, а (a+b)(c+d) это только одно дополнительное умножение вместо двух. Получается, что одно из 4 умножений можно сэкономить!Итоговая сложность:
k*N + 3*k*(N/2) + 9*k*(N/4) + .... ~ O(N^1.6). Метод так и назвали в честь Толяна - алгоритм Карацубы. В 1971 году к серверу подключились Шёнхаге и Штрассен - тот самый, кто придумал быстрое умножение матриц. В своём телеграм-канале они запостили алгоритм, умножающий числа за
O(N * log n * log (log n)). Число длины
N можно представить в виде полинома степени K от заданного основания B: x_0 + x_1 * B + x_2 * B^2 + ... У нас есть 2 таких полинома, и результатом их умножения является ещё один полином степени до 2K. Очевидно, подставляя любое значение вместо B, мы будем получать корректное равенство между произведением изначальных значений полинома и значением результирующего полинома.Алгоритм заключается в следующем: сначала вычисляем изначальные полиномы в
2K точках, потом умножаем между собой эти результаты (в выбираемых точках они маленькие), а дальше можно восстановить коэффициенты результирующего полинома по этим 2K точкам. Наивная имплементация этой логики даёт квадратичную сложность. Однако, быстрое дискретное преобразование Фурье, выбор правильной степени разложения и ряд других умных оптимизаций позволяют получить ту самую сложность
O(N * log n * log (log n)). Детали этого процесса за гранью моего понимания.В 2019 году был предложен метод, который в теории способен умножать числа за
O(N log N). К сожалению, спрятанная константа здесь настолько большая, что его не имеет смысла применять в каких-то реальных ситуациях. На текущий момент не доказано, что
O(N log N) - это нижняя грань сложности умножения 2 чисел. Лишь несуществование линейного алгоритма следует из одной из нерешённых проблем в Computer Science. Вот и живите теперь с этим.@knowledge_accumulator