The Karatsuba algorithm is a fast multiplication algorithm for integers. It was discovered by Anatoly Karatsuba in 1960 and published in 1962. It is a divide-and-conquer algorithm that reduces the multiplication of two n-digit numbers to three multiplications of n/2-digit numbers and, by repeating this reduction, to at most n log 2 3 ≈ n 1.58 {\displaystyle n^{\log _{2}3}\approx n^{1.58}} single-digit multiplications. It is therefore asymptotically faster than the traditional algorithm, which performs n 2 {\displaystyle n^{2}} single-digit products. The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm. The Toom–Cook algorithm (1963) is a faster generalization of Karatsuba's method, and the Schönhage–Strassen algorithm (1971) is even faster, for sufficiently large n.
History The standard procedure for multiplication of two n-digit numbers requires a number of elementary operations proportional to n 2 {\displaystyle n^{2}\,\!} , or O ( n 2 ) {\displaystyle O(n^{2})\,\!} in big-O notation. Andrey Kolmogorov conjectured that the traditional algorithm was asymptotically optimal, meaning that any algorithm for that task would require Ω ( n 2 ) {\displaystyle \Omega (n^{2})\,\!} elementary operations. In 1960, Kolmogorov organized a seminar on mathematical problems in cybernetics at the Moscow State University, where he stated the Ω ( n 2 ) {\displaystyle \Omega (n^{2})\,\!} conjecture and other problems in the complexity of computation. Within a week, Karatsuba, then a 23-year-old student, found an algorithm that multiplies two n-digit numbers in O ( n log 2 3 ) {\displaystyle O(n^{\log _{2}3})} 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. 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 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.
Algorithm
Basic step The basic principle of Karatsuba's algorithm is divide-and-conquer, using a formula that allows one to compute the product of two large numbers x {\displaystyle x} and y {\displaystyle y} using three multiplications of smaller numbers, each with about half as many digits as x {\displaystyle x} or y {\displaystyle y} , plus some additions and digit shifts. This basic step is, in fact, a generalization of a similar complex multiplication algorithm, where the imaginary unit i is replaced by a power of the base. Let x {\displaystyle x} and y {\displaystyle y} be represented as n {\displaystyle n} -digit strings in some base B {\displaystyle B} . For any positive integer m {\displaystyle m} less than n {\displaystyle n} , one can write the two given numbers as
x = x 1 B m + x 0 , {\displaystyle x=x_{1}B^{m}+x_{0},}
y = y 1 B m + y 0 , {\displaystyle y=y_{1}B^{m}+y_{0},}
where x 0 {\displaystyle x_{0}} and y 0 {\displaystyle y_{0}} are less than B m {\displaystyle B^{m}} . The product is then
… excerpt ends here. Continue reading the full article.
