5
$\begingroup$

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

  • 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.2012-08-04

2 Answers 2

5

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.

  • 0
    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 wrong2012-08-04
  • 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).2012-08-04
  • 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 ](http://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.2012-08-04
  • 0
    @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?2012-08-04
  • 0
    @mixedmath ohhh so you just foil it out into $xy = ac10^{2n}$ etc..2012-08-04
  • 0
    @David: Exactly. I suppose it's not particularly deep. I happen to have written another [answer](http://math.stackexchange.com/a/178492/9754) involving this and a slightly harder but related multiplication method just the other day.2012-08-04
  • 0
    Actually, $10^n$ is just a special choice of base. You could use any integer $\ge 2$ instead of $10$. Quite obviously, for modern computers, $2$ is a common choice with $n=8, 16$, or $32$, say.2012-08-04
  • 0
    No, the formula just given is NOT the full Karatsuba multiplication!!! In particular, this formula requires *4* multiplications. It gives NO SAVINGS in time. To do real Karatsuba multiplication, you must trick-compute the middle term. The trick is that $ad + bc = (a + b)(c + d) - ac - bd$. Since you already need to compute $ac$ and $bd$, you can store them, and this reduces the cost to 3 multiplications, and so there is a savings.2012-10-07
0

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