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.

$\underline{SplitMultiply(x, y,n):} \\ \hspace{0.4cm} if\space n = 1 \\ \hspace{1cm} return\space x · y \\ \hspace{0.42cm} else \\ \hspace{1cm} m ← ⌈n/2⌉ \\ \hspace{1cm} a←⌊x/10^m⌋; \space b←x\space mod\space 10^m \hspace{1cm} {\color{Red}〈〈x=10^m \space a+b〉〉 } \\ \hspace{1cm} c←⌊y/10^m⌋;\space d←y\space mod\space10^m \hspace{1cm} {\color{Red}〈〈y=10^m \space c+d〉〉 } \\ \hspace{1cm} e ← SplitMultiply(a, c, m) \\ \hspace{1cm} f ←SplitMultiply(b,d,m) \\ \hspace{1cm} g ← SplitMultiply(b, c, m) \\ \hspace{1cm} h←SplitMultiply(a,d,m) \\ \hspace{1cm} return\space 10^{2m}e + 10^m(g + h) + f$ ...