Notes by Gene Cooperman, © 2009 (may be freely copied as long as this copyright notice remains)
Suppose two integers, x and y, each have n bits.
How many 1-bit multiplies do
we need to multiply them?
Presumably, we just need to multiply all cross product terms.
To do this, multiply the i-th bit of x by the j-th bit
of y, and place the answer in the (i+j)-th column of the answer.
(In looking at the i-th and j-th column, we're considering the rightmost
bit or units column as the 0-th column,
the next bit to the left or the twos column as the 1-st column,
the fours column as the 2-nd column, etc.)
Then we add all the bits in a column, do any carries, etc.
But we only needed n2 bit multiplies.
So, we guess that integer multiplication has complexity
O(n2).
In fact, we will show that it requires only O(nlog_2 3)
≈ O(n1.59) multiplications.
The trick is to break up x into the upper bits xL
and the lower bits xR, and similarly for y.
Now, we need to compute something like the following four cross products:
xL yL
xL yR
xR yL
xR yR
But instead of computing all four cross product terms, we can just compute
the three products:
xL yL
xR yR
(xL + xR) (yL + yR)
If we use these products to construct the product x y, we would
usually object that we are missing the cross products:
xL yR +xR yL
But in fact,
xL yR + xR yL =
(xL + xR) (yL + yR)
- xL yL - xR yR
So, we can build the missing cross product using nothing but
addition and the three cross products that we actually did compute.
Hence, we have used three multiplies instead of the expected four multiplies.
If we continue to use this trick recursively, as we break xL,
xR, yL, and yR each into two parts,
then we can show that we end up having to do only O(nlog_2
3) bit multiplies. So, we win by using recursion!