# 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

-
Maybe there is somme secret code in use in that area, for all those who don't know this is would be helpful if you could reveal the relations between $x, y, a, b, c, d$ and $n$ to us. – user20266 Aug 4 '12 at 16:28

Karatsuba multiplication works like this:

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$. The advantage of the algorithm is that you can just calculate the products $ac, ad, bc$ and $bd$, all of which have much smaller sizes than the original (for large $n$).

You'll note that I use $2n$ and $n$ instead of $n$ and $n/2$, but the idea is the same.

-
What does n represent here? I understand that a, b is x split into two numbers and c,d is y split into two numbers. Please correct me if I'm wrong – The Internet Aug 4 '12 at 16:37
@David Johnson: $n$ is just some number, which may be different for each multiplication. For example, if $x = 123456$ and $y = 654321$, maybe I would use $n=3$ to write this as $123\cdot 10^3 + 456$ and $654\cdot 10^3 + 321$. The idea of using $n$ to be half the number of digits as the larger of the two numbers is the general use (and it's usually done in binary). – mixedmath Aug 4 '12 at 16:44
@mixedmath : Perfect answer, I was going to type what you have added in the comment, and you saved my effort of typing again , Thanks . But to add something, David, this types of strategies fall under something called " [Divide and conquer strategies ](en.wikipedia.org/wiki/Divide_and_conquer_algorithm) , where you divide the initial problem into pieces and later on assemble them into a the original problem. Rest of the thing is neatly explained in mixedmath's version. – Iyengar Aug 4 '12 at 16:48
@mixedmath Ah I see so n is just the number of integers of (a,b) or (c,d), so it will vary by input size. In your case 3 makes sense since you're splitting 123456. Is this thinking correct? – The Internet Aug 4 '12 at 16:51
@mixedmath ohhh so you just foil it out into $xy = ac10^{2n}$ etc.. – The Internet Aug 4 '12 at 16:52

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

-