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