Алгоритм Карацубы

Умножение Карацубы — метод быстрого умножения, который позволяет перемножать два n-значных числа с битовой вычислительной сложностью:

$T(n)=O(n^{{\log }_2<!--\; \; -->3}),{\log }_2<!--\; \; -->3=\mathrm{1,584}9\dots <!--\; \dots \; -->$$T(n)=O(n^{\log _{2}3}),\quad \log _{2}3=1{,}5849\ldots$.

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

ИсторияПравить

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

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

Описание методаПравить

 

Сравнение алгоритма Карацубы и умножения в столбик. Внизу схематически показано дерево рекурсивных вызовов алгоритма для всё меньших и меньших чисел. Количество вершин на последнем его уровне соответствует количеству элементарных умножений. Очевидно, что у алгоритма Карацубы ширина дерева растёт значительно медленнее.

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

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

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

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

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

$=ac{x}^2+((a+b)(c+d)-<!--\; -\; -->ac-<!--\; -\; -->bd)x+bd.$$={\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}\ .$ 

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

$T(n)=3T\left(\frac{n}{2}\right)+O(n)=O(n^{{\log }_2<!--\; \; -->3}).$$T(n)=3T\left({\frac {n}{2}}\right)+O(n)=O(n^{\log _{2}3})\ .$ 

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

$T(n)=4T\left(\frac{n}{2}\right)+O(n)=O(n^{{\log }_2<!--\; \; -->4})=O(n^2).$$T(n)=4T\left({\frac {n}{2}}\right)+O(n)=O(n^{\log _{2}4})=O(n^{2})\ .$ 

ПримерыПравить

 

Графическая иллюстрация другого примера: умножения 1234 на 567 по алгоритму Карацубы. Сначала выполняются нижние шаги $(A),(B),(C)$$(A),\ (B),\ (C)$ , а потом их результаты подставляются в верхнюю схему.

Для удобства изложения будем использовать десятичную систему, то есть аргументы многочлена вида $x={10}^k$$x=10^{k}$  вместо $x=2^k$$x=2^{k}$ . Цветовая разметка цифр не связана с предыдущим разделом, а обозначает лишь, из какого числа вычленяется та или иная часть.

Вычислим $1213\cdot <!--\; \cdot \; -->2311$${\color {red}1213}\cdot {\color {blue}2311}$ :

• заметим, что $12+13=25,23+11=34$${\color {red}12}+{\color {red}13}=25,\ {\color {blue}23}+{\color {blue}11}=34$  и вычислим $25\cdot <!--\; \cdot \; -->34$${\color {darkorange}25}\cdot {\color {magenta}34}$ :
  • заметим, что $2+5=7,3+4=7$${\color {darkorange}2}+{\color {darkorange}5}=7,\ {\color {magenta}3}+{\color {magenta}4}=7$  и вычислим $7\cdot <!--\; \cdot \; -->7=49$$7\cdot 7=49$ 
  • вычислим $2\cdot <!--\; \cdot \; -->3=6$${\color {darkorange}2}\cdot {\color {magenta}3}=6$ 
  • вычислим $5\cdot <!--\; \cdot \; -->4=20$${\color {darkorange}5}\cdot {\color {magenta}4}=20$ 
  • складывая результаты, получим, что $25\cdot <!--\; \cdot \; -->34=6\cdot <!--\; \cdot \; -->{10}^2+(49-<!--\; -\; -->6-<!--\; -\; -->20)\cdot <!--\; \cdot \; -->10+20=850$${\color {darkorange}25}\cdot {\color {magenta}34}=6\cdot 10^{2}+(49-6-20)\cdot 10+20=850$ 
• вычислим $12\cdot <!--\; \cdot \; -->23$${\color {red}12}\cdot {\color {blue}23}$  как $12\cdot <!--\; \cdot \; -->23$${\color {darkorange}12}\cdot {\color {magenta}23}$ :
  • заметим, что $1+2=3,2+3=5$${\color {darkorange}1}+{\color {darkorange}2}=3,\ {\color {magenta}2}+{\color {magenta}3}=5$  и вычислим $3\cdot <!--\; \cdot \; -->5=15$$3\cdot 5=15$ 
  • вычислим $1\cdot <!--\; \cdot \; -->2=2$${\color {darkorange}1}\cdot {\color {magenta}2}=2$ 
  • вычислим $2\cdot <!--\; \cdot \; -->3=6$${\color {darkorange}2}\cdot {\color {magenta}3}=6$ 
  • складывая результаты, получим, что $12\cdot <!--\; \cdot \; -->23=2\cdot <!--\; \cdot \; -->{10}^2+(15-<!--\; -\; -->2-<!--\; -\; -->6)\cdot <!--\; \cdot \; -->10+6=276$${\color {darkorange}12}\cdot {\color {magenta}23}=2\cdot 10^{2}+(15-2-6)\cdot 10+6=276$ 
• вычислим $13\cdot <!--\; \cdot \; -->11$${\color {red}13}\cdot {\color {blue}11}$  как $13\cdot <!--\; \cdot \; -->11$${\color {darkorange}13}\cdot {\color {magenta}11}$ :
  • заметим, что $1+3=4,1+1=2$${\color {darkorange}1}+{\color {darkorange}3}=4,\ {\color {magenta}1}+{\color {magenta}1}=2$  и вычислим $4\cdot <!--\; \cdot \; -->2=8$$4\cdot 2=8$ 
  • вычислим $1\cdot <!--\; \cdot \; -->1=1$${\color {darkorange}1}\cdot {\color {magenta}1}=1$ 
  • вычислим $3\cdot <!--\; \cdot \; -->1=3$${\color {darkorange}3}\cdot {\color {magenta}1}=3$ 
  • складывая результаты, получим, что $13\cdot <!--\; \cdot \; -->11=1\cdot <!--\; \cdot \; -->{10}^2+(8-<!--\; -\; -->1-<!--\; -\; -->3)\cdot <!--\; \cdot \; -->10+3=143$${\color {darkorange}13}\cdot {\color {magenta}11}=1\cdot 10^{2}+(8-1-3)\cdot 10+3=143$ 
• складывая результаты, получим, что $1213\cdot <!--\; \cdot \; -->2311=276\cdot <!--\; \cdot \; -->{10}^4+(850-<!--\; -\; -->276-<!--\; -\; -->143)\cdot <!--\; \cdot \; -->{10}^2+143=2803243$${\color {red}1213}\cdot {\color {blue}2311}=276\cdot 10^{4}+(850-276-143)\cdot 10^{2}+143=2803243$ 

СсылкиПравить

• http://212.cmc-msu.ru/files/kniga.html
• https://web.archive.org/web/20071031012910/http://gersoo.free.fr/docs/karat/kar.html
• http://numbers.computation.free.fr/Constants/Algorithms/representation.html
• https://web.archive.org/web/20160417193210/http://www-math.uni-paderborn.de/mca/mult.html
• http://www-2.cs.cmu.edu/~cburch/251/karat/
• http://www.cs.pitt.edu/~kirk/cs1501/animations/
• https://web.archive.org/web/20070125091442/http://www.cs.princeton.edu/introcs/79crypto/Karatsuba.java.html
• http://www.ccas.ru/personal/karatsuba/divcru.htm
• http://www.ccas.ru/personal/karatsuba/alg.htm