TheKaratsuba algorithm is a fastmultiplication algorithm forintegers. It was discovered byAnatoly Karatsuba in 1960 and published in 1962.^[1][2][3] It is adivide-and-conquer algorithm that reduces the multiplication of twon-digit numbers to three multiplications ofn/2-digit numbers and, by repeating this reduction, to at most${\displaystyle n^{{\log }_{2}3}\approx n^{1.58}}$ single-digit multiplications. It is thereforeasymptotically faster than thetraditional algorithm, which performs${\displaystyle n^2}$ single-digit products.

The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm.TheToom–Cook algorithm (1963) is a faster generalization of Karatsuba's method, and theSchönhage–Strassen algorithm (1971) is even faster, for sufficiently largen.

The standard procedure for multiplication of twon-digit numbers requires a number of elementary operations proportional to${\displaystyle n^2}$, or${\displaystyle O(n^2)}$ inbig-O notation.Andrey Kolmogorov conjectured that the traditional algorithm wasasymptotically optimal, meaning that any algorithm for that task would require${\displaystyle \mathrm{\Omega }(n^2)}$ elementary operations.

In 1960, Kolmogorov organized a seminar on mathematical problems incybernetics at theMoscow State University, where he stated the${\displaystyle \mathrm{\Omega }(n^2)}$ conjecture and other problems in thecomplexity of computation. Within a week, Karatsuba, then a 23-year-old student, found an algorithm that multiplies twon-digit numbers in${\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 theProceedings 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 byYuri 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.^[2]

The basic principle of Karatsuba's algorithm isdivide-and-conquer, using a formula that allows one to compute the product of two large numbers${\displaystyle x}$ and${\displaystyle y}$ using three multiplications of smaller numbers, each with about half as many digits as${\displaystyle x}$ or${\displaystyle y}$, plus some additions and digit shifts. This basic step is, in fact, a generalization ofa similar complex multiplication algorithm, where theimaginary uniti is replaced by a power of thebase.

Let${\displaystyle x}$ and${\displaystyle y}$ be represented as${\displaystyle n}$-digit strings in some base${\displaystyle B}$. For any positive integer${\displaystyle m}$ less than${\displaystyle n}$, one can write the two given numbers as

${\displaystyle x=x_1{B}^m+x_0,}$

${\displaystyle y=y_1{B}^m+y_0,}$

where${\displaystyle x_0}$ and${\displaystyle y_0}$ are less than${\displaystyle B^m}$. The product is then

where

${\displaystyle z_2=x_1{y}_1,}$

${\displaystyle z_1=x_1{y}_0+x_0{y}_1,}$

${\displaystyle z_0=x_0{y}_0.}$

These formulae require four multiplications and were known toCharles Babbage.^[4] Karatsuba observed that${\displaystyle xy}$ can be computed in only three multiplications, at the cost of a few extra additions. With${\displaystyle z_0}$ and${\displaystyle z_2}$ as before and${\displaystyle z_3=(x_1+x_0)(y_1+y_0),}$ one can observe that

Thus only three multiplications are required for computing${\displaystyle z_0,z_1}$ and${\displaystyle z_2.}$

To compute the product of 12345 and 6789, whereB = 10, choosem = 3. We usem right shifts for decomposing the input operands using the resulting base (B^m =1000), as:

12345 =12 ·1000 +345

6789 =6 ·1000 +789

Only three multiplications, which operate on smaller integers, are used to compute three partial results:

z₂ =12×6 = 72

z₀ =345×789 = 272205

z₁ = (12 +345)× (6 +789) −z₂ −z₀ = 357× 795 − 72 − 272205 = 283815 − 72 − 272205 = 11538

We get the result by just adding these three partial results, shifted accordingly (and then taking carries into account by decomposing these three inputs in base1000 as for the input operands):

result =z₂ · (B^m)² +z₁ · (B^m)¹ +z₀ · (B^m)⁰, i.e.

result = 72 ·1000² + 11538 ·1000 + 272205 =83810205.

Note that the intermediate third multiplication operates on an input domain which is less than two times larger than for the two first multiplications, its output domain is less than four times larger, and base-1000 carries computed from the first two multiplications must be taken into account when computing these two subtractions.

Ifn is four or more, the three multiplications in Karatsuba's basic step involve operands with fewer thann digits. Therefore, those products can be computed byrecursive calls of the Karatsuba algorithm. The recursion can be applied until the numbers are so small that they can (or must) be computed directly.

In a computer with a full 32-bit by 32-bitmultiplier, for example, one could chooseB = 2³¹ and store each digit as a separate 32-bit binary word. Then the sumsx₁ +x₀ andy₁ +y₀ will not need an extra binary word for storing the carry-over digit (as incarry-save adder), and the Karatsuba recursion can be applied until the numbers to multiply are only one digit long.

Karatsuba's basic step works for any baseB and anym, but the recursive algorithm is most efficient whenm is equal ton/2, rounded up. In particular, ifn is 2^k, for some integerk, and the recursion stops only whenn is 1, then the number of single-digit multiplications is 3^k, which isn^c wherec = log₂3.

Since one can extend any inputs with zero digits until their length is a power of two, it follows that the number of elementary multiplications, for anyn, is at most${\displaystyle 3^{\lceil {\log }_{2}n\rceil }\le 3n^{{\log }_{2}3}}$.

Since the additions, subtractions, and digit shifts (multiplications by powers ofB) in Karatsuba's basic step take time proportional ton, their cost becomes negligible asn increases. More precisely, ifT(n) denotes the total number of elementary operations that the algorithm performs when multiplying twon-digit numbers, then

${\displaystyle T(n)=3T(\lceil n/2\rceil )+cn+d}$

for some constantsc andd. For thisrecurrence relation, themaster theorem for divide-and-conquer recurrences gives theasymptotic bound${\displaystyle T(n)=\mathrm{\Theta }(n^{{\log }_{2}3})}$.

It follows that, for sufficiently largen, Karatsuba's algorithm will perform fewer shifts and single-digit additions than longhand multiplication, even though its basic step uses more additions and shifts than the straightforward formula. For small values ofn, however, the extra shift and add operations may make it run slower than the longhand method.

Here is the pseudocode for this algorithm, using numbers represented in base ten. For the binary representation of integers, it suffices to replace everywhere 10 by 2.^[5]

The second argument of the split_at function specifies the number of digits to extract from theright: for example, split_at("12345", 3) will extract the 3 final digits, giving: high="12", low="345".

functionkaratsuba(num1,num2)if(num1<10ornum2<10)returnnum1×num2/* fall back to traditional multiplication *//* Calculates the size of the numbers. */m=max(size_base10(num1),size_base10(num2))m2=floor(m/2)/* m2 = ceil (m / 2) will also work *//* Split the digit sequences in the middle. */high1,low1=split_at(num1,m2)high2,low2=split_at(num2,m2)/* 3 recursive calls made to numbers approximately half the size. */z0=karatsuba(low1,low2)z1=karatsuba(low1+high1,low2+high2)z2=karatsuba(high1,high2)return(z2×10^(m2×2))+((z1-z2-z0)×10^m2)+z0

An issue that occurs when implementation is that the above computation of${\displaystyle (x_1+x_0)}$ and${\displaystyle (y_1+y_0)}$ for${\displaystyle z_1}$ may result in overflow (will produce a result in the range), which require a multiplier having one extra bit. This can be avoided by noting that

${\displaystyle z_1=(x_0-x_1)(y_1-y_0)+z_2+z_0.}$

This computation of${\displaystyle (x_0-x_1)}$ and${\displaystyle (y_1-y_0)}$ will produce a result in the range of. This method may produce negative numbers, which require one extra bit to encode signedness, and would still require one extra bit for the multiplier. However, one way to avoid this is to record the sign and then use the absolute value of${\displaystyle (x_0-x_1)}$ and${\displaystyle (y_1-y_0)}$ to perform an unsigned multiplication, after which the result may be negated when both signs originally differed. Another advantage is that even though${\displaystyle (x_0-x_1)(y_1-y_0)}$ may be negative, the final computation of${\displaystyle z_1}$ only involves additions.

• Karatsuba's Algorithm for Polynomial Multiplication
• Weisstein, Eric W."Karatsuba Multiplication".MathWorld.
• Bernstein, D. J., "Multidigit multiplication for mathematicians". Covers Karatsuba and many other multiplication algorithms.

• Computer arithmetic algorithms
• Multiplication
• Divide-and-conquer algorithms

• CS1 maint: postscript
• Articles with short description
• Short description matches Wikidata
• Articles with example pseudocode