Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?


share|cite|improve this question
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

2 Answers 2

up vote 5 down vote accepted

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.

share|cite|improve this answer
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 ]( , 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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.