Fast Multiplication

Divide-and-conquer algorithm

Two ancient algorithms for multiplying two $n$-digit numbers in $O(n^2)$ time are the grade-school lattice algorithm and the Egyptian peasant algorithm. Maybe we can get a more efficient algorithm by splitting the digit arrays in half and exploiting the following identity:

$$(10^ma + b)(10^mc + d) = 10^{2m}ac + 10^m(bc + ad) + bd$$

This recurrence immediately suggests the following divide-and-conquer algorithm to multiply two $n$-digit numbers, $x$ and $y$. Each of the four sub-products $ac, bc, ad,$ and $bd$ is computed recursively, but the multiplications in the last line are not recursive because we can multiply by a power of ten by shifting the digits to the left and filling in the correct number of zeros, all in $O(n)$ time.