Karatsuba Multiplication 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
 A: 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.
A: n represents the number of digits of the factors that are being multiplied.
For example:
1234 x 5678 = 7006652
So 1234 as 4 digits, as for 5678. Then we say n = 4 because each factor as 4 digits.
Now apply the equation and see for yourself:
1234*5678 = 10^4(12*56) + 10^2(12*78 + 34*56) + 34*78 = 7006652
