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 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. This basic step is, in fact, a generalization of
a similar complex multiplication algorithm, where the
imaginary unit is replaced by a power of the
base. Let x and y be represented as n-digit strings in some base B. For any positive integer m less than n, one can write the two given numbers as :x = x_1 B^m + x_0, :y = y_1 B^m + y_0, where x_0 and y_0 are less than B^m. The product is then \begin{align} xy &= (x_1 B^m + x_0)(y_1 B^m + y_0) \\ &= x_1 y_1 B^{2m} + (x_1 y_0 + x_0 y_1) B^m + x_0 y_0 \\ &= z_2 B^{2m} + z_1 B^m + z_0, \\ \end{align} where :z_2 = x_1 y_1, :z_1 = x_1 y_0 + x_0 y_1, :z_0 = x_0 y_0. These formulae require four multiplications and were known to
Charles Babbage. Karatsuba observed that xy can be computed in only three multiplications, at the cost of a few extra additions. With z_0 and z_2 as before and z_3=(x_1 + x_0) (y_1 + y_0), one observes that : \begin{alignat}{2} z_1 &= x_1 y_0 + x_0 y_1 \\ &= x_1 y_0 + x_0 y_1 + x_1 y_1 + x_0 y_0 &&- x_1 y_1 - x_0 y_0 \\ &= (x_1 + x_0) (y_1 + y_0) &&- x_1 y_1 - x_0 y_0 \\ &= z_3 - z_2 - z_0. \\ \end{alignat} Thus only three multiplications are required for computing z_0, z_1 and z_2, and thus xy. An alternative form uses z_4 = (x_1 - x_0)(y_1 - y_0) instead: : \begin{align} z_1 &= \phantom{x_1 y_1 + x_0 y_0 - (x_1 y_1 - x_0 y_0 + {}} x_1 y_0 + x_0 y_1 \\ &= x_1 y_1 + x_0 y_0 - \phantom{(}x_1 y_1 - x_0 y_0 + x_1 y_0 + x_0 y_1 \\ &= x_1 y_1 + x_0 y_0 - (x_1 y_1 + x_0 y_0 - x_1 y_0 - x_0 y_1) \\ &= x_1 y_1 + x_0 y_0 - (x_1 - x_0) (y_1 - y_0)\\ &= z_2 + z_0 - z_4. \\ \end{align}
Example To compute the product of 12345 and 6789, where
B = 10, choose
m = 3. We use
m right shifts for decomposing the input operands using the resulting base (
Bm =
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: :
z2 =
12 × 6 = 72 :
z0 =
345 × 789 = 272205 :
z1 = (
12 +
345)
× (
6 +
789) −
z2 −
z0 = 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 base
1000 as for the input operands): : result =
z2 · (
Bm)
2 +
z1 · (
Bm)
1 +
z0 · (
Bm)
0, i.e. : result = 72 ·
10002 + 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.
Recursive application If
n is four or more, the three multiplications in Karatsuba's basic step involve operands with fewer than
n digits. Therefore, those products can be computed by
recursive 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-bit
multiplier, for example, one could choose
B = 231 and store each digit as a separate 32-bit binary word. Then the sums
x1 +
x0 and
y1 +
y0 will not need an extra binary word for storing the carry-over digit (as in
carry-save adder), and the Karatsuba recursion can be applied until the numbers to multiply are only one digit long.
Time complexity analysis Karatsuba's basic step works for any base
B and any
m, but the recursive algorithm is most efficient when
m is equal to
n/2, rounded up. In particular, if
n is 2
k, for some integer
k, and the recursion stops only when
n is 1, then the number of single-digit multiplications is 3
k, which is
nc where
c = log23. 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 any
n, is at most 3^{ \lceil\log_2 n \rceil} \leq 3 n^{\log_2 3}\,\!. Since the additions, subtractions, and digit shifts (multiplications by powers of
B) in Karatsuba's basic step take time proportional to
n, their cost becomes negligible as
n increases. More precisely, if
T(
n) denotes the total number of elementary operations that the algorithm performs when multiplying two
n-digit numbers, then :T(n) = 3 T(\lceil n/2\rceil) + cn + d for some constants
c and
d. For this
recurrence relation, the
master theorem for divide-and-conquer recurrences gives the
asymptotic bound T(n) = \Theta(n^{\log_2 3})\,\!. It follows that, for sufficiently large
n, 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 of
n, however, the extra shift and add operations may make it run slower than the longhand method. ==Implementation==