Karatsuba MultiplicationDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2015 The Math Forum
http://mathforum.org/dr.math/