Wikipedia

Karatsuba algorithm

This is an old revision of this page, as edited by Jorge Stolfi (talk | contribs) at 06:08, 29 September 2008 (→Algorithm: Renamed the terms so that the lowest digit is 0 not 2; renamed X,Y to Z2,Z0; reworded analysis.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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 Θ. This makes it faster than the classical Θ(n2) algorithm (). The Karatsuba algorithm can be considered to be the earliest example of a binary splitting algorithm, or more generally, a divide and conquer algorithm.

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.

The basic step of Karatsuba's algorithm is a formula that allows us to compute the product of two large numbers x and y using three multiplications of smaller numbers, each with about half as many digits as x or y, plus some additions and digit shifts.

Let x and y be represented as n-digit strings in some base B. For any positive integer m less than n, one can split the two given numbers as follows

x = x1Bm + x0
y = y1Bm + y0

where x0 and y0 are less than Bm. The product is then

xy = (x1Bm + x0)(y1Bm + y0)
= z2 B2m + z1 Bm + z0

where

z2 = x1y1
z1 = x1y0 + x0y1
z0 = x0y0

These formulas require four multiplications. Karatsuba observed that we can compute xy in only three multiplications, at the cost of a few extra additions:

Let z2 = x1y1
Let z0 = x0y0
Let z1 = (x1 + x0)(y1 + y0) - z2 - z0

since

z1 = (x1y1 + x1y0 + x0y1 + x0y0) - x1y1 - x0y0
= x1y0 + x0y1

To compute these three products of m-digit numbers, we can recursively employ Karatsuba multiplication again, until the numbers become so small that their product can be computed directly. One typically chooses B so that this condition is verified when the numbers are 1 digit each. In a computer with a full 32-bit by 32-bit multiplier, for example, one could choose B = 232 or B = 109, and store each digit as a separate 32-bit binary word.

Karatsuba's basic step works for any base B and any m, but the recursive algorithm is most efficient when, and m is equal to n/2, rounded up. In particular, if n is 2k, for some integer k, and the recursion stops only when n is 1, then the recursive Karatsuba algorithm performs at most 3k multiplications of 1-digit numbers; that is, nc where c = log23. When n is large, Karatsuba's algorithm is much faster than the grade school method, which requires n2 single-digit multiplications. If n = 210 = 1024, for example, it requires 310 59,049 instead of (210)2 = 1,048,576 single-digit multiplies.

Since the additions, subtractions, and digit shifts (multiplications by powers of B) in Karasuba's basic step take time proportional to n, their cost of all becomes negligible as n increases.

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

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.

References

Retrieved from "https://en.wikipedia.org/w/index.php?title=Karatsuba_algorithm&oldid=241711532"