Анатолию Карацубе было 23 года, когда в 1960 году он обнаружил способ умножения чисел, более быстрый, чем известные до тех пор, и положил тем самым начало всей области быстрых алгоритмов.
История этого открытия описана вкратце в его обзорной
статье о сложности вычислений (математика там довольно сухая, зато есть интересный исторический обзор об умножении в древности). Великий математик Колмогоров стремился доказать, что умножение двух n-размерных чисел требует примерно n^2 элементарных операций, и меньшим числом не обойтись. Например, представьте, что вы умножаете 1234 * 5678 в столбик: вам надо по сути дела умножить каждую цифру числа 1234 на каждую цифру числа 5678, т.е. сделать 16 элементарных умножений цифры на цифру; плюс еще много раз складывать промежуточные результаты и приписывать нули в конце. Но общее число операций будет порядка 16 (может, в два или три раза больше, чтобы учесть все сложения и приписывания). А если вы умножаете два числа по 1000 цифр в каждом, то общее число операций будет 1000^2, т.е. миллион (может, в 2-3 раза больше, но это несущественно). Колмогоров считал несомненным, что нет какого-то магического способа умножать числа быстрее, чем умножение в столбик, которым люди пользуются уже 2000 лет. Но он не мог это доказать.
Карацуба: "Осенью 1960 г. в Московском университете на механико-математическом факультете начал работать семинар по математическим вопросам кибернетики под руководством А.Н. Колмогорова, где А.Н. Колмогоровым была сформулирована гипотеза n^2 и поставлен ряд задач об оценке сложности решений линейных систем уравнений и других сходных вычислений. Я активно стал размышлять над гипотезой n^2 и ровно через неделю обнаружил, что алгоритм, которым я надеялся получить нижнюю оценку, дает оценку вида O(n^1,549...). После очередного заседания семинара я сообщил А.Н. Колмогорову о новом алгоритме умножения и об опровержении гипотезы n^2. Это сильно взволновало А.Н. Колмогорова, так как противоречило его довольно правдоподобной гипотезе. На следующем заседании семинара мой метод умножения был рассказан самим А.Н. Колмогоровым, и на этом семинар прекратил свою работу."
Попытаюсь объяснить суть открытия Карацубы в упрощенном виде. Представьте себе, что перед вами поставили задачу перемножить два числа, например 1234 * 5678, но при этом все операции сложения и приписывания нулей вам дают "бесплатно", а вот за каждое умножение двух цифр надо платить, ну не знаю, доллар. Может, кому-то удалось запатентовать таблицу умножения? Понятно, что это можно "обойти", сделав умножение через сложение, но давайте притворимся, что мы так не умеем, и что каждый раз, когда надо умножить две цифры, мы честно платим доллар; естественно, мы хотим делать как можно меньше умножений.
Если умножать в столбик обычным способом, то будет 16 умножений (каждая цифра на каждую), ничего не поделать. Но можно попробовать вывернуться как-то. Что если мы разделим каждое 4-х значное число на два двузначных?
1234 * 5678 = (12*100 + 34) * (56*100 + 78)
Здесь *100 не является по-настоящему умножением (это всего лишь приписывание нулей в конце, бесплатно). Если мы раскроем скобки, то получим сложную формулу в которой будут участвовать произведения чисел 12, 34, 56, 78, плюс всякие нули и сложения. Сколько умножений надо сделать? На первый взгляд четыре, когда мы раскрываем скобки: 12*56, 12*78, 34*56, 34*78. Если мы предполагаем, что два двузначных числа мы перемножаем в столбик, по 4 умножения цифр для каждого (а лучше мы пока не умеем), то выходит всего 4*4 = 16 умножений, и мы ничего не улучшили.
И тут открытие Карацубы. Обратим внимание, что нам на самом деле нужно получить, для окончательного сложения, три вещи: 12*56 (к нему приписать четыре нуля), 34*78 (не приписывать нулей), и 12*78+34*56 (к этому приписать два нуля). Если бы эту сумму двух произведений можно было как-то получить с помощью всего одного умножения, то вместе четырех мы бы получили три двузначных произведения. Карацуба заметил, что если мы скомпонуем вместе 12+34, и 56+78 - это весьма неинтуитивно, потому что мы складываем сотни и тысячи с десятками и единицами, казалось бы, зачем - и умножим, то получим:
(12+34)*(56+78) = 12*56 + 34*78 + 12*78 + 34*56.
Но первые два произведения мы и так уже вычисляем: 12*56 и 34*78. А оставшиеся два - это как раз то, что нам нужно. Значит, достаточно сделать только три умножения:
12*56
34*78
(12+34)*(56+78)
И из результата третьего вычесть первые два, чтобы получить все, что нам нужно для результата (после приписывания нулей и сложений, которые бесплатны). Если каждое из этих трех умножений двузначных чисел (да, 56+78 оказывается трехзначным, но это крохотное усложнение, которое легко учесть и не меняет сути) занимает, как раньше, 4 умножения, теперь у нас всего требуется только 3*4=12 умножений двух цифр. А ведь каждое умножение двухзначных чисел можно по такому же принципу свести к 3-м, а не 4-м умножениям, и тогда выходит всего 3*3=9 умножений, вместо исходных 16.
Это и есть алгоритм Карацубы, в одном из его видов. Естественно, это все становится важным, только когда мы умножаем 50-значные или 1000-значные числа, а не такие маленькие. Но суть в том, чтобы свести задачу к меньшей, с под-задачами на числах в 2 раза короче, но благодаря этому странному трюку оказывается надо делать не 4 под-задачи, а только три. Эти под-задачи в свою очередь разбиваются на три поменьше, и так далее. Кропотливый математический анализ показывает, что число операций для умножения двух n-разрядных чисел становится не n в квадрате, а примерно в степени полтора. А для очень длинных чисел это играет важную роль.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
