Divide and Conquer

Break problem into smaller sub-problems.

example: multiplication

Multiplying by powers of ten is easy, so we can break a multiplication into smaller groups.

For instance, we can break \(n\) digit integer into:

\begin{equation} [x_1, x_2, \dots, x_{\frac{n}{2}}] \times 10^{\frac{n}{2}} + [x_{\frac{n}{2}+1}, x_{\frac{n}{2}+2}, \dots] \end{equation}

Then we can multiply two large values by writing:

\begin{align} x \times y &= \qty(a \times 10^{\frac{n}{2}} + b ) \qty(c \times 10^{\frac{n}{2}} + d) \\ &= \qty(a \times c ) 10^{n} + \qty(a \times d + c \times b) 10^{\frac{n}{2}} + \qty( b \times d) \end{align}

Doing this is still \(4^{\log_{2}\qty(n)} = n^{2}\), which is where we started.

Karatsuba Integer Multiplication

If we don’t have to compute 4 multiplication terms, it can be better. We can make this not 4 terms by observing that computing:

• \(ac\)
• \(bd\)
• \(\qty(a+b) \qty(c+d) = ac + bd + bc + ad\)

We can get the middle term by \(\qty(a+b) \qty(c+d) - ac - bd\). This is now \(3^{\log_{2}\qty(n)} \approx n^{1.6}\), which is more efficient.