Take the 2-minute tour ×
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?

Thanks

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

1 Answer 1

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|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
1  
@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
1  
@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

Your Answer

 
discard

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.