Karatsuba algorithm

From Wikipedia, the free encyclopedia

The Karatsuba multiplication algorithm, a technique for quickly multiplying large numbers, was discovered by Anatolii Alexeevich Karatsuba in 1960 and published in the joint paper with Yu. Ofman in 1962. Its time complexity is Θ(n^{\log_23}). This makes it faster than the classical Θ(n2) algorithm (\log_23 \approx 1.585). The Karatsuba algorithm can be considered to be the earliest example of a binary splitting algorithm, or more generally, a divide and conquer algorithm.

Contents

[edit] Algorithm

The speed of this algorithm relies partly on the ability to do shifts faster than a standard multiply, with shifts typically taking linear time on a practical computer.

We assume two n-digit numbers x and y, represented in base B where B is a convenient value to shift with, like two in modern binary computers. Choosing a number m less than n, we can write

x = x1Bm + x2
y = y1Bm + y2

where x2 and y2 are less than Bm; it is easily seen that there is a unique representation. We now have

xy = (x1Bm + x2)(y1Bm + y2)
= x1y1B2m + (x1y2 + x2y1)Bm + x2y2

The standard method is to multiply the four subproducts separately, then finally shift and add; this is O(n2). However, Karatsuba observed that we can compute xy in only three multiplications:

Let X = x1y1
Let Y = x2y2
Let Z = (x1 + x2)(y1 + y2) - X - Y

We note that

Z = (x1y1 + x1y2 + x2y1 + x2y2) - x1y1 - x2y2
= x1y2 + x2y1

Thus xy = X B2m + Y + Z Bm; we have cut down the number of multiplications from four to three.

To compute these three products of m-digit numbers, we can recursively employ Karatsuba multiplication again. The shifts, additions and subtractions take linear time respectively, and can be considered negligible.

Karatsuba multiplication works best when the two operands are of similar size; thus while one can theoretically choose m arbitrarily, the best time bound would be achieved by choosing m such that the subproducts are roughly equal, that is setting m to be about n/2.

[edit] Example

Say we want to compute the product of 1234 and 5678. We choose B = 10 and m = 2. We have

12 34 = 12 × 102 + 34
56 78 = 56 × 102 + 78
X = 12 × 56 = 672
Y = 34 × 78 = 2652
Z = (12 + 34)(56 + 78) - X - Y = 46 × 134 - 672 - 2652 = 2840
X × 102×2 + Y + Z × 102 = 672 0000 + 2652 + 2840 00 = 7006652 = 1234 × 5678

[edit] Complexity

If T(n) denotes the time it takes to multiply two n-digit numbers with Karatsuba's method, then we can write

T(n) = 3 T(n/2) + cn + d

for some constants c and d, and this recurrence relation can be solved using the master theorem, giving a time complexity of Θ(nlog(3)/log(2)). The number log(3)/log(2) is approximately 1.585, so this method is significantly faster than long multiplication as n grows large. Because of the overhead of recursion, however, Karatsuba's multiplication is typically slower than long multiplication for small values of n; typical implementations therefore switch to long multiplication if n is below some threshold when computing the subproducts.

Implementations differ greatly on what the crossover point is when Karatsuba becomes faster than the classical algorithm, but generally numbers over 2320 are faster with Karatsuba. [1][2] Toom-Cook multiplication is a faster generalization of Karatsuba's, and is further surpassed by the Schönhage-Strassen algorithm.

[edit] References

[edit] External links