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.