Loooooong Loooooong Loooooong Loooooong Loooooong Man

in elementary school, we were taught a simple way of multiplying numbers, but it is of course not the most efficient way for multiplying n digit numbers. let’s say we want to multiply the following two $n = 8$ digit numbers: $39475928 \times 1689347$ using the elementary school method, we will have multiple $8 \times 8$ single digits. in general, multiplying two $n$ digit numbers by this method requires $n^2$ single digit multiplications (and a similar number of single digit additions). in contrast, consider writing these numbers as: $x = x_1 \cdot 10^{n/2} + x_0$ and $y = y_1 \cdot 10^{n/2} + y_0$ where $x_0, x_1, y_0, y_1$ are all $n/2$-digit long numbers. the product can now be written as $$x \cdot y = (x_1 \cdot 10^{n/2} + x_0) \times (y_1 \cdot 10^{n/2} + y_0)$$ expanding this, we get $$x \cdot y = x_1 y_1 \cdot 10^n + (x_1 y_0 + x_0 y_1) \cdot 10^{n/2} + x_0 y_0$$ notice how this requires four multiplications of n/2 digit long numbers. we can reduce it from four to three by rewriting $(x_1 y_0 + x_0 y_1)$ as $(x_0 + x_1)(y_0 + y_1) - x_1 \cdot y_1 - x_0 \cdot y_0$.

making the formula cleaner: $z_0 = x_0 \cdot y_0$ $z_1 = (x_0 + x_1)(y_0 + y_1)$ $z_2 = x_1 \cdot y_1$ so, our original problem becomes: $$x \cdot y = z_2 \cdot 10^n + (z_1 - z_0 - z_2) \cdot 10^{n/2} + z_0$$ congratulations 🎉, you’ve just learnt Karatsuba multiplication.