
Karatsuba algorithm

The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962. It reduces the multiplication of two "n"-digit numbers to at most formula_1 single-digit multiplications in general (and exactly formula_2 when "n" is a power of 2). It is therefore asymptotically faster than the traditional algorithm, which requires formula_3 single-digit products. For example, the Karatsuba algorithm requires 310 = 59,049 single-digit multiplications to multiply two 1024-digit numbers ("n" = 1024 = 210), whereas the traditional algorithm requires (210)2 = 1,048,576 (a speedup of 17.75 times).
The Karatsuba algorithm was the first multiplication algorithm asymptotically faster than the quadratic "grade school" algorithm.
The Toom–Cook algorithm (1963) is a faster generalization of Karatsuba's method, and the Schönhage–Strassen algorithm (1971) is even faster, for sufficiently large "n".
History.
The standard procedure for multiplication of two "n"-digit numbers requires a number of elementary operations proportional to formula_4, or formula_5 in big-O notation. Andrey Kolmogorov conjectured that the traditional algorithm was "asymptotically optimal," meaning that any algorithm for that task would require formula_6 elementary operations.
In 1960, Kolmogorov organized a seminar on mathematical problems in cybernetics at the Moscow State University, where he stated the formula_6 conjecture and other problems in the complexity of computation. Within a week, Karatsuba, then a 23-year-old student, found an algorithm (later it was called "divide and conquer") that multiplies two "n"-digit numbers in formula_8 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 the Proceedings 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 by Yuri 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.
Algorithm.
Basic step.
The basic step of Karatsuba's algorithm is a formula that allows one to compute the product of two large numbers formula_9 and formula_10 using three multiplications of smaller numbers, each with about half as many digits as formula_9 or formula_10, 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 formula_9 and formula_10 be represented as formula_15-digit strings in some base formula_16. For any positive integer formula_17 less than formula_15, one can write the two given numbers as
where formula_21 and formula_22 are less than formula_23. The product is then
formula_24
where
These formulae require four multiplications and were known to Charles Babbage. Karatsuba observed that formula_28 can be computed in only three multiplications, at the cost of a few extra additions. With formula_29 and formula_30 as before one can observe that
An issue that occurs, however, when computing formula_32 is that the above computation of formula_33 and formula_34 may result in overflow (will produce a result in the range formula_35), which require a multiplier having one extra bit. This can be avoided by noting that
This computation of formula_37 and formula_38 will produce a result in the range of formula_39. 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 formula_37 and formula_38 to perform an unsigned multiplication, after which the result may be negated when both signs originally differed. Another advantage is that even though formula_42 may be negative, the final computation of formula_32 only involves additions.
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 ("B""m" = "1000"), as:
Only three multiplications, which operate on smaller integers, are used to compute three partial results:
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" like for the input operands):
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 "x"1 + "x"0 and "y"1 + "y"0 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.
Asymmetric Karatsuba-like formulae.
Karatsuba's original formula and other generalizations are themselves symmetric. For example, the following formula computes 
with 6 multiplications in formula_45, where formula_46 is the Galois field with two elements 0 and 1.
where formula_48 and formula_49.
We note that addition and subtraction are the same in fields of characteristic 2.
This formula is symmetrical, namely, it does not change if we exchange formula_50 and formula_51 in formula_52 and formula_53.
Based on the second Generalized division algorithms, Fan et al. found the following asymmetric formula:
where formula_55 and formula_56.
It is asymmetric because we can obtain the following new formula by exchanging formula_50 and formula_51 in 
formula_59 and formula_60.
where formula_62 and formula_63.
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 "n""c" 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 formula_64.
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
for some constants "c" and "d". For this recurrence relation, the master theorem for divide-and-conquer recurrences gives the asymptotic bound formula_66.
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. The point of positive return depends on the computer platform and context. As a rule of thumb, Karatsuba's method is usually faster when the multiplicands are longer than 320–640 bits.
Pseudocode.
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.
The second argument of the split_at function specifies the number of digits to extract from the "right": for example, split_at("12345", 3) will extract the 3 final digits, giving: high="12", low="345".
procedure karatsuba(num1, num2)
 if (num1 < 10) or (num2 < 10)
 return num1 × num2
 /* Calculates the size of the numbers. */
 m = min(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 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