5

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

The Internet
  • 297
  • 1
  • 2
  • 9
  • 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. –  Aug 04 '12 at 16:28
  • It is worth noting that the equation above is only one step of the algorithm and does not optimize anything by its own. The complexity is still squared. The optimization comes when using the trick +=(+)(+)−−. – ETO Mar 05 '20 at 18:27

2 Answers2

7

Karatsuba multiplication is a way to translate a multiplication of two "very large" numbers $x$ and $y$ into $3$ multiplications of "smaller" numbers, plus a number of additions. This makes sense if the numbers are large enough that multiplication is much more expensive than addition.

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$. Further $(ad+bc) = (a+b)(c+d) - ac - bd$. Thus computing the three products $ac, bd,$ and $(a+b)(c+d)$ and performing some additions gives the answer. Further, each of $a, b, c, d$ are smaller (typically having half as many digits) as $x$ and $y$, so those multiplications are faster.

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

davidlowryduda
  • 91,687
  • 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 04 '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). – davidlowryduda Aug 04 '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 , 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. – IDOK Aug 04 '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 04 '12 at 16:51
  • @mixedmath ohhh so you just foil it out into $xy = ac10^{2n}$ etc.. – The Internet Aug 04 '12 at 16:52
  • @David: Exactly. I suppose it's not particularly deep. I happen to have written another answer involving this and a slightly harder but related multiplication method just the other day. – davidlowryduda Aug 04 '12 at 17:02
  • 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. –  Aug 04 '12 at 17:03
1

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

Inês Barata Feio Borges
  • 121
  • 5