Karatsuba Multiplication

It is possible to perform Multiplication of Large Numbers in (many) fewer operations than the usual brute-force technique of ``long multiplication.'' As discovered by Karatsuba and Ofman (1962), Multiplication of two $n$-Digit numbers can be done with a Bit Complexity of less than $n^2$ using identities of the form

$$(a+b\cdot 10^n)(c+d\cdot 10^n) = ac+[(a+b)(c+d)-ac-bd]10^n+bd\cdot 10^{2n}.$$ (1)

Proceeding recursively then gives Bit Complexity ${\mathcal O}(n^{\lg 3})$, where $\lg 3=1.58\ldots<2$ (Borwein et al. 1989). The best known bound is ${\mathcal O}(n\lg n\lg \lg n)$ steps for $n\gg 1$ (Schönhage and Strassen 1971, Knuth 1981). However, this Algorithm is difficult to implement, but a procedure based on the Fast Fourier Transform is straightforward to implement and gives Bit Complexity ${\mathcal O}((\lg n)^{2+\epsilon}n)$ (Brigham 1974, Borodin and Munro 1975, Knuth 1981, Borwein et al. 1989).

As a concrete example, consider Multiplication of two numbers each just two ``digits'' long in base $w$,

$$N_1 = a_0 + a_1 w$$ (2)

$$N_2 = b_0 + b_1 w,$$ (3)

then their Product is

$$P \equiv N_1N_2$$

$$= a_0 b_0 + (a_0 b_1 + a_1 b_0) w + a_1 b_1 w^2$$

$$= p_0 + p_1 w + p_2 w^2.$$ (4)

Instead of evaluating products of individual digits, now write

$$q_0 = a_0 b_0$$ (5)

$$q_1 = (a_0 + a_1)(b_0 + b_1)$$ (6)

$$q_2 = a_1 b_1.$$ (7)

The key term is $q_1$, which can be expanded, regrouped, and written in terms of the $p_j$ as

$$q_1 = p_1 + p_0 + p_2.$$ (8)

However, since $p_0 = q_0$, and $p_2 = q_2$, it immediately follows that

$$p_0 = q_0$$ (9)

$$p_1 = q_1 - q_0 - q_2$$ (10)

$$p_2 = q_2,$$ (11)

so the three ``digits'' of $p$ have been evaluated using three multiplications rather than four. The technique can be generalized to multidigit numbers, with the trade-off being that more additions and subtractions are required.

Now consider four-``digit'' numbers

$$N_1 = a_0 + a_1 w + a_2 w^2 + a_3 w^3,$$ (12)

which can be written as a two-``digit'' number represented in the base $w^2$,

$$N_1 = (a_0 + a_1 w) + (a_2 + a_3 w)*w^2.$$ (13)

The ``digits'' in the new base are now

$$a'_0 = a_0 + a_1 w$$ (14)

$$a'_1 = a_2 + a_3 w,$$ (15)

and the Karatsuba algorithm can be applied to $N_1$ and $N_2$ in this form. Therefore, the Karatsuba algorithm is not restricted to multiplying two-digit numbers, but more generally expresses the multiplication of two numbers in terms of multiplications of numbers of half the size. The asymptotic speed the algorithm obtains by recursive application to the smaller required subproducts is ${\mathcal O}(n^{\lg 3})$ (Knuth 1981).

When this technique is recursively applied to multidigit numbers, a point is reached in the recursion when the overhead of additions and subtractions makes it more efficient to use the usual ${\mathcal O}(n^2)$ Multiplication algorithm to evaluate the partial products. The most efficient overall method therefore relies on a combination of Karatsuba and conventional multiplication.

See also Complex Multiplication, Multiplication, Strassen Formulas

References

Borodin, A. and Munro, I. The Computational Complexity of Algebraic and Numeric Problems. New York: American Elsevier, 1975.

Borwein, J. M.; Borwein, P. B.; and Bailey, D. H. ``Ramanujan, Modular Equations, and Approximations to Pi, or How to Compute One Billion Digits of Pi.'' Amer. Math. Monthly 96, 201-219, 1989.

Brigham, E. O. The Fast Fourier Transform. Englewood Cliffs, NJ: Prentice-Hall, 1974.

Brigham, E. O. Fast Fourier Transform and Applications. Englewood Cliffs, NJ: Prentice-Hall, 1988.

Cook, S. A. On the Minimum Computation Time of Functions. Ph.D. Thesis. Cambridge, MA: Harvard University, pp. 51-77, 1966.

Hollerbach, U. ``Fast Multiplication & Division of Very Large Numbers.'' sci.math.research posting, Jan. 23, 1996.

Karatsuba, A. and Ofman, Yu. ``Multiplication of Many-Digital Numbers by Automatic Computers.'' Doklady Akad. Nauk SSSR 145, 293-294, 1962. Translation in Physics-Doklady 7, 595-596, 1963.

Knuth, D. E. The Art of Computing, Vol. 2: Seminumerical Algorithms, 2nd ed. Reading, MA: Addison-Wesley, pp. 278-286, 1981.

Schönhage, A. and Strassen, V. ``Schnelle Multiplikation Grosser Zahlen.'' Computing 7, 281-292, 1971.

Toom, A. L. ``The Complexity of a Scheme of Functional Elements Simulating the Multiplication of Integers.'' Dokl. Akad. Nauk SSSR 150, 496-498, 1963. English translation in Soviet Mathematics 3, 714-716, 1963.

Zuras, D. ``More on Squaring and Multiplying Large Integers.'' IEEE Trans. Comput. 43, 899-908, 1994.