Discrete Algebraic Methods

3.8 Multiplication and division

The classical method of multiplying two binary numbers of length n requires Θ(n2) operations. Let the two numbers r and s of 2k bits each be of the following form:

Here, A represents the k most significant bits of r and B the k least significant bits. Similar for C and D with respect to s. In other words, we can write r = A 2k + B and s = C 2k + D. From that we obtain

k

Instead of following this approach, Karatsuba’s algorithm (Anatoly Alexeyevich Karatsuba, 1937–2008) recursively computes the three products AC