Умножение Карацубы — метод быстрого умножения, позволяющий перемножать два ${\displaystyle n}$ - значных числа с битовой вычислительной сложностью ${\displaystyle T(n)=O(n^{\log _{2}3})}$ .

Изобретён Анатолием Карацубой в 1960 году . Является исторически первым алгоритмом умножения, превосходящим тривиальный по асимптотической сложности .

История

В 1960 году Колмогоров проводил семинар, посвящённый математическим задачам кибернетики. Одной из рассматриваемых на семинаре задач стало умножение двух ${\displaystyle n}$ -разрядных целых чисел. Основным известным методом умножения в то время было умножение «в столбик», которое при алгоритмической реализации требовало ${\displaystyle O(n^{2})}$ элементарных операций (сложений или умножений одноразрядных чисел). Колмогоров выдвинул гипотезу, что умножение «в столбик» является оптимальным алгоритмом умножения двух чисел в том смысле, что время работы любого метода умножения не меньше ${\displaystyle n^{2}}$ по порядку величины. На правдоподобность «гипотезы ${\displaystyle n^{2}}$ » указывало то, что метод умножения «в столбик» известен не менее четырёх тысячелетий, и если бы был более быстрый метод умножения, то он, вероятно, уже был бы найден. Однако, через неделю 23-летний Карацуба предложил новый метод умножения двух ${\displaystyle n}$ -значных чисел с оценкой времени работы ${\displaystyle O(n^{\log _{2}3})}$ и тем самым опроверг «гипотезу ${\displaystyle n^{2}}$ ».

Метод Карацубы относится к алгоритмам вида « разделяй и властвуй », наравне с такими алгоритмами как двоичный поиск , быстрая сортировка и др. Формулы рекурсивного сведения, используемые в методе Карацубы, были известны ещё Чарльзу Бэббиджу , который, однако, не обратил внимания на возможность использования лишь трёх рекурсивных умножений вместо четырёх .

Алгоритм

Два ${\displaystyle n}$ -битовых числа можно представить в виде ${\displaystyle ax+b}$ , ${\displaystyle cx+d}$ , где ${\displaystyle x=2^{\lceil {n/2}\rceil }}$ и ${\displaystyle a,b,c,d<2^{\lceil {n/2}\rceil }}$ .

Умножение на ${\displaystyle 2^{\lceil {n/2}\rceil }}$ ( битовый сдвиг ) и сложение делаются за постоянное время ${\displaystyle O(1)}$ . Поэтому задача умножения сводится к вычислению коэффициентов многочлена ${\displaystyle (ax+b)(cx+d)}$ . Используя тождество:

${\displaystyle {\color {green}(a+b)(c+d)}={\color {red}ac}+{\color {darkorange}(ad+bc)}+{\color {blue}bd}\ }$ ,

этот многочлен можно представить в виде:

${\displaystyle (ax+b)(cx+d)={\color {red}ac}x^{2}+{\color {darkorange}(ad+bc)}x+{\color {blue}bd}=}$

${\displaystyle ={\color {red}ac}x^{2}+{\color {darkorange}{\Big (}}{{\color {green}(a+b)(c+d)}-{\color {red}ac}-{\color {blue}bd}}{\color {darkorange}{\Big )}}x+{\color {blue}bd}}$ .

В последнем выражении участвуют три произведения ${\displaystyle \left({\left\lceil {\frac {n}{2}}\right\rceil +1}\right)}$ -значных чисел. Если вычислять каждое из них по той же схеме, получится алгоритм с рекуррентной оценкой времени работы :

${\displaystyle T(n)=3T\left({\frac {n}{2}}\right)+O(n)=O\left(n^{\log _{2}3}\right)}$ .

Для сравнения, аналогичный алгоритм, производящий отдельно все четыре умножения ${\displaystyle ac}$ , ${\displaystyle ad}$ , ${\displaystyle bc}$ , ${\displaystyle bd}$ , требовал бы обычного времени:

${\displaystyle T(n)=4T\left({\frac {n}{2}}\right)+O(n)=O\left(n^{\log _{2}4}\right)=O\left(n^{2}\right)}$ .

Примеры

Для умножения двух восьмизначных (в десятичной записи) чисел ${\displaystyle N=11113333}$ и ${\displaystyle M=55557777}$ каждое из них представляется в виде суммы двух чисел вдвое меньшей разрядности, одно из которых взято со сдвигом :

${\displaystyle {\begin{cases}N=1111\cdot 10000+3333\\M=5555\cdot 10000+7777\end{cases}}}$

Раскрывая скобки, произведение ${\displaystyle N}$ и ${\displaystyle M}$ можно переписать как:

${\displaystyle (1111\cdot 10000+3333)(5555\cdot 10000+7777)=1111\cdot 5555\cdot 10000^{2}+10000(1111\cdot 7777+5555\cdot 3333)+3333\cdot 7777}$

Карацуба нашёл, что вместо четырёх умножений вдвое более коротких чисел, можно делать лишь три: ${\displaystyle 1111\cdot 5555}$ , ${\displaystyle (1111+3333)\cdot (5555+7777)}$ и ${\displaystyle 3333\cdot 7777}$ , в результате чего выражение преобразуется к виду:

${\displaystyle 1111\cdot 5555\cdot 10000^{2}+10000((1111+3333)\cdot (5555+7777)-1111\cdot 5555-3333\cdot 7777)+3333\cdot 7777}$ .

Для умножения укороченных вдвое чисел применяется тот же алгоритм: ${\displaystyle 1111\cdot 5555}$ представляется как ${\displaystyle (11\cdot 100+11)(55\cdot 100+55)}$ и так далее. На практике для достаточно коротких чисел применяется уже обычное умножение как более эффективное.

Подход работает в любой системе счисления, в том числе и в двоичной, используемой вычислительной техникой. Например, вычисление произведения двух 4096-битных двоичных чисел методом Карацубы требует ${\displaystyle 3^{12}\approx 5,3\cdot 10^{5}}$ элементарных однобитовых умножений вместо ${\displaystyle (2^{12})^{2}\approx 1,68\cdot 10^{7}}$ при умножении наивным методом.

Примечания

Ссылки