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.

$$\begin{gathered} \underset{‾}{SplitMultiply(x,y,n):} \\ ifn=1 \\ returnx\cdot y \\ else \\ m\leftarrow \lceil n\mathrm{/}2\rceil \\ a\leftarrow \lfloor x\mathrm{/}10^m\rfloor ;b\leftarrow xmod10^m\text{〈〈}x=10^{m}a+b\text{〉〉} \\ c\leftarrow \lfloor y\mathrm{/}10^m\rfloor ;d\leftarrow ymod10^m\text{〈〈}y=10^{m}c+d\text{〉〉} \\ e\leftarrow SplitMultiply(a,c,m) \\ f\leftarrow SplitMultiply(b,d,m) \\ g\leftarrow SplitMultiply(b,c,m) \\ h\leftarrow Split \end{gathered}$$ ...