Karatsuba algorithm: Difference between revisions

Revision as of 14:29, 5 January 2021

Revision as of 21:09, 7 April 2021

Line 30:

The standard procedure for multiplication of two ''n''-digit numbers requires a number of elementary operations proportional to <math>n^2\,\!</math>, or <math>O(n^2)\,\!</math> in [[big-O notation]]. [[Andrey Kolmogorov]] conjectured that the traditional algorithm was ''[[asymptotically optimal]],'' meaning that any algorithm for that task would require <math>\Omega(n^2)\,\!</math> elementary operations.

In 1960, Kolmogorov organized a seminar on mathematical problems in [[cybernetics]] at the [[Moscow State University]], where he stated the <math>\Omega(n^2)\,\!</math> conjecture and other problems in the [[Computational complexity theory|complexity of computation]]. Within a week, Karatsuba, then a 23-year-old student, found an algorithm (later it was called "divide and conquer") that multiplies two ''n''-digit numbers in <math>O(n^{\log_2 3})</math> elementary steps, thus disproving the conjecture. Kolmogorov was very excited about the discovery; he communicated it at the next meeting of the seminar, which was then terminated. Kolmogorov gave some lectures on the Karatsuba result at conferences all over the world (see, for example, "Proceedings of the International Congress of Mathematicians 1962", pp.&nbsp; 351–356, and also "6 Lectures delivered at the International Congress of Mathematicians in Stockholm, 1962") and published the method in 1962, in the [[Proceedings of the USSR Academy of Sciences]]. The article had been written by Kolmogorov and contained two results on multiplication, Karatsuba's algorithm and a separate result by [[Yuri Petrovich Ofman|Yuri Ofman]]; it listed "A. Karatsuba and Yu. Ofman" as the authors. Karatsuba only became aware of the paper when he received the reprints from the publisher.<ref name="kara1995"/>

"6 Lectures delivered at the International Congress of Mathematicians in Stockholm, 1962") and published the method in 1962, in the [[Proceedings of the USSR Academy of Sciences]]. The article had been written by Kolmogorov and contained two results on multiplication, Karatsuba's algorithm and a separate result by [[Yuri Petrovich Ofman|Yuri Ofman]]; it listed "A. Karatsuba and Yu. Ofman" as the authors. Karatsuba only became aware of the paper when he received the reprints from the publisher.<ref name="kara1995"/>

==Algorithm==

Line 90 ⟶ 89:

===Asymmetric Karatsuba-like formulae===

Karatsuba's original formula and other generalizations are themselves symmetric. For example, the following formula computes

the following formula computes

:<math>c(x)=c_4x^4+c_3x^3+c_2x^2+c_1x+c_0=a(x)b(x)=(a_2x^2+a_1x+a_0)(b_2x^2+b_1x+b_0)</math>

with 6 multiplications in <math>{\text{GF}}(2)[x]</math>, where <math>{\text{GF}}(2)</math> is the Galois field with two elements 0 and 1.

Line 111 ⟶ 109:

This formula is symmetrical, namely, it does not change if we exchange <math>a</math> and <math>b</math> in <math>p_i, \ \ p_{ij}</math> and <math>p_{ijk}</math>.

Based on the second [[Euclidean division|Generalized division algorithms]],<ref>Haining Fan, Ming Gu, Jiaguang Sun, Kwok-Yan Lam,"Obtaining More Karatsuba-Like Formulae over the Binary

,<ref>Haining Fan, Ming Gu, Jiaguang Sun, Kwok-Yan Lam,"Obtaining More Karatsuba-Like Formulae over the Binary

Field", IET Information security Vol. 6 No. 1 pp. 14-19, 2012.</ref> Fan et al. found the following asymmetric formula:

Line 126 ⟶ 123:

}\right.

\end{align}</math>

where <math>m_{3}=(a_{01}+a_{2})(b_{10}+b_{2}), \ \ m_{4}=(a_{10}+a_{21})(b_{01}+b_{12})</math> and <math>m_{5}=(a_{0}+a_{12})(b_{0}+b_{21})</math>.

where

<math>m_{3}=(a_{1}+a_{2})(b_{0}+b_{2}), \ \ m_{4}=(a_{0}+a_{1})(b_{1}+b_{2})</math> and

<math>m_{5}=(a_{0}+a_{2})(b_{0}+b_{1})</math>.

It is asymmetric because we can obtain the following new formula by exchanging <math>a</math> and <math>b</math> in

Line 144 ⟶ 139:

}\right.

\end{align}</math>

where <math>m_{3}=(a_{10}+a_{2})(b_{01}+b_{2}), \ \ m_{4}=(a_{01}+a_{12})(b_{10}+b_{21})</math> and <math>m_{5}=(a_{0}+a_{1})(b_{0}+b_{2})</math>.

where

<math>m_{3}=(a_{0}+a_{2})(b_{1}+b_{2}), \ \ m_{4}=(a_{1}+a_{2})(b_{0}+b_{1})</math> and <math>m_{5}=(a_{0}+a_{1})(b_{0}+b_{2})</math>.

==Efficiency[[Time complexity]] analysis==

Karatsuba's basic step works for any base ''B'' and any ''m'', but the recursive algorithm is most efficient when ''m'' is equal to ''n''/2, rounded up. In particular, if ''n'' is 2^''k'', for some integer ''k'', and the recursion stops only when ''n'' is 1, then the number of single-digit multiplications is 3^''k'', which is ''n''^''c'' where ''c'' = log₂3.