Associated Topics || Dr. Math Home || Search Dr. Math

### Karatsuba Multiplication

```Date: 10/15/2007 at 14:57:11
From: Dylan
Subject: Karatsuba multiplication

I found this idea of multiplication but really don't totally
understand it.  Every example that I have found online is very complex
and not easy to understand.  I will continue to try to understand this
concept more but I thought I would ask you if you could explain it in
simple terms with examples.

```

```
Date: 10/19/2007 at 18:05:00
From: Doctor Vogler
Subject: Re: Karatsuba multiplication

Hi Dylan,

Thanks for writing to Dr. Math.  The idea is this:  When you have two
large numbers, say n digits each, and you want to multiply them, then
you have to multiply one digit from each number about n^2 times.
That's a lot of multiplies.  Consider a 10-digit multiplication:

2839745624
x 8769342123
-------------
8519236872
5679491248
2839745624
5679491248
11358982496
8519236872
25557710616
14198728120
17038473744
19878219368
--------------------
24902700919148119752

We had 100 one-digit multiplies, plus a lot of adding the carry
digits, and a final large addition.

The Karatsuba method saves a quarter of the multiplications by doing
three half-size multiplications (half-size makes them four times
smaller) at the cost of some extra additions and subtractions.  The
idea is to split up your two numbers like so:

2839745624 = 28397*100000 + 45624
8769342123 = 87693*100000 + 42123

so their product is given by

2839745624 * 8769342123
= (28397*10^5 + 45624) * (87693*10^5 + 42123)
= (28397*87693)*10^10
+ (45624*87693 + 28397*42123)*10^5 + (45624*42123).

So you see the first half-size multiply in the first coefficient, and
the second half-size multiply in the last coefficient.  The middle
part looks like two half-size multiplications (which doesn't save you
anything at all), but it can be computed using only one product, and
then the other two products that you already computed:

45624*87693 + 28397*42123
= (28397 + 45624)*(87693 + 42123) - (28397*87693) - (45624*42123).

So the bottom line is the following:

First compute the two sums:
28397 + 45624 = 74021
87693 + 42123 = 129816

Then compute the three half-size products:
28397*87693 = 2490218121
45624*42123 = 1921819752
(28397 + 45624)*(87693 + 42123) = 74021*129816 = 9609110136

Then compute
45624*87693 + 28397*42123 = 5197072263
as the difference of the third product with the sum of the first two
5197072263 = 9609110136 - 2490218121 - 1921819752
and shift the three results by 0, 5, and 10 digits,
1921819752
5197072263
2490218121
--------------------
24902700919148119752
which is 2839745624 * 8769342123

So if you suppose that a multi-digit addition or subtraction takes
relevant carries/borrows) and a multi-digit multiply takes about n^2
steps (n^2 one-digit multiplications, not counting various additions
and carries), then the cost of a regular multiplication is n^2, but
the cost of a Karatsuba multiplication is (following my steps above)

n/2
n/2
(n/2)^2
(n/2)^2
(n/2)^2
2(n/2)
2n

(I called the cost of the last add two full n-digit adds, although
really you're only adding the digits where they overlap, which is
about half of this.)  That's a total of (3/4)n^2 + 4n, which saves you

(1/4)n^2 - 4n = (n - 16)n/4.

So that means that it would save you work if n > 16.  Of course, in
many cases, one-digit multiplications are harder than one-digit
additions, and I mentioned that I put the cost of that last addition
rather high.  But in any case, this algorithm saves you time when your
number is large enough (where "enough" depends on the person or
computing machine doing the computations), but not when it is smaller.

So generally, if you have HUGE multiplications to do, you iterate this
idea.  First you trade one huge multiply for three half-size
multiplications and some additions.  Then since those half-size
multiplications are still large, you trade each of those for three
quarter-size multiplications.  If those are still large
multiplications, then you do it again.  But eventually you get
multiplications that are small enough that splitting them in half
again doesn't actually help, so you do the smallest multiplications
normally, and then you go back up the chain putting the pieces
together (with additions and subtractions) to get the full product.

Does that make sense?  I hope it cleared things up a little bit.  If
and show me what you have been able to do, and I will try to offer
further suggestions.

- Doctor Vogler, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Algorithms