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,
  and add the three together:
            1921819752
       5197072263
  2490218121
  --------------------
  24902700919148119752
  which is 2839745624 * 8769342123

So if you suppose that a multi-digit addition or subtraction takes 
about n steps (n one-digit additions or subtractions, including 
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
you have any questions about this or need more help, please write back
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/