Karatsuba algorithm

From Wikipedia, the free encyclopedia

The Karatsuba multiplication algorithm, a technique for quickly multiplying large numbers, was discovered by Anatolii Alexeevich Karatsuba and published together with Yu. Ofman in 1962. Its time complexity is Θ $(n^{\log_23})$ . This makes it faster than the classical Θ(n²) algorithm ( $\log_23 \approx 1.585$ ).

1 Algorithm
2 Example
3 Complexity
4 References

[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 most computers today. Choosing a number m less than n, we can write

x = x₁B^m + x₂

y = y₁B^m + y₂

where x₂ and y₂ are less than B^m; it is easily seen that there is a unique representation. We now have

xy = (x₁B^m + x₂)(y₁B^m + y₂)

= x₁y₁B^2m + (x₁y₂ + x₂y₁)B^m + x₂y₂

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

Let X = x₁y₁

Let Y = x₂y₂

Let Z = (x₁ + x₂)(y₁ + y₂) - X - Y

We note that

Z = (x₁y₁ + x₁y₂ + x₂y₁ + x₂y₂) - x₁y₁ - x₂y₂

= x₁y₂ + x₂y₁

Thus xy = X B^2m + Y + Z B^m; we have cut down the number of multiplications from four to three.

To compute these three products of m-digit numbers, we can employ Karatsuba multiplication again, effectively using recursion. 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 ⋅ 10² + 34

56 78 = 56 ⋅ 10² + 78

X = 12 ⋅ 56 = 672

Y = 34 ⋅ 78 = 2652

Z = (12 + 34)(56 + 78) - X - Y = 46 ⋅ 134 - 672 - 2652 = 2840

X 10^2⋅2 + Y + Z 10² = 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 Θ(n^{log(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 2³²⁰ are faster with Karatsuba. [1][2] Toom-Cook multiplication is a faster generalization of Karatsuba's, and is further surpassed by the fastest known, the Schönhage-Strassen algorithm.

[edit] References

A. Karatsuba and Yu Ofman, "Multiplication of Many-Digital Numbers by Automatic Computers." Doklady Akad. Nauk SSSR Vol. 145 (1962), pp. 293–294. Translation in Physics-Doklady 7 (1963), pp. 595–596.
Karatsuba Multiplication on MathWorld
Bernstein, D. J., "Multidigit multiplication for mathematicians". Covers Karatsuba and many other multiplication algorithms.

Retrieved from "http://en.wikipedia.org../../../k/a/r/Karatsuba_algorithm.html"

Category: Arbitrary precision algorithms