Karatsuba's equation to reduce the amount of time it takes in brute force multiplication is as follows (I believe this is a divide-and-conquer algorithm):
$$ x y = 10^n(ac) + 10^{n/2}(ad + bc) + bd $$
My question is this. Where did the $10^{n/2}$ and $10^n$ come from?
Thanks
Karatsuba multiplication is a way to translate a multiplication of two "very large" numbers $x$ and $y$ into $3$ multiplications of "smaller" numbers, plus a number of additions. This makes sense if the numbers are large enough that multiplication is much more expensive than addition.
Let $x = a10^n + b$ and $y = c10^n + d$, and $a,b,c,d < 10^n$. Then to find the product $xy$, one notes that $xy = ac10^{2n} + (ad + bc)10^n + bd$. Further $(ad+bc) = (a+b)(c+d) - ac - bd$. Thus computing the three products $ac, bd,$ and $(a+b)(c+d)$ and performing some additions gives the answer. Further, each of $a, b, c, d$ are smaller (typically having half as many digits) as $x$ and $y$, so those multiplications are faster.
You'll note that I use $2n$ and $n$ instead of $n$ and $n/2$, but the idea is the same.