3 ms·

Thank you for the explanation. I was wondering how I can apply karatsuba's method to multiply for e.g. 103 X 1022.

svat 7y ago
(Was hoping someone else may answer your question, but as it appears that no one has…) Firstly, just in case it wasn't clear already, note that the algorithm is not intended for mental or manual arithmetic; its gains become apparent only when multiplying very large numbers (which is why I used 200 digits as an example). In particular, it wouldn't make sense to use it other than in cases where an addition and two subtractions are together faster than one multiplication at least — e.g. it wouldn't make sense to use it for numbers that can fit in a couple of machine words (say about 128 bits, or about 40 digits). If using it to multiply numbers by hand, I might use it for multiplying two 10-digit numbers but not anything smaller. So assuming you understand all that and are asking about the 103 * 1022 example just to see concretely what the idea is, then read on. With 1022 being a 4-digit number, we can take X=100, and write 103 as aX+b with a=1 and b=3, and similarly 1022 as cX+d with c=10 and d=22. Then just compute a+b, c+d, and the three products ac, bd, and (a+b)(c+d): a b a+b 1 03 4 10 22 32 c d c+d ac bd (a+b)(c+d) 10 66 128 (Each number in the last row above was computed by multiplying the two numbers directly above it.) Finally it only remains to compute (ad+bc) as a subtraction (here's where the savings come from; we don't have to multiply a with d, nor b with c — though in this example they'd be quite trivial anyway): 52 (a+b)(c+d)-ac-bd = 128-66-10 So we have the three quantities ac=10, (ad+bc)=52, and bd=66, giving the product to be (ac)X^2 + (ad+bc)X + bd (recall that X=100), which is 105266. Again, it's quite pointless to use this for such tiny examples, and in fact we haven't even used the recursive nature of the algorithm. If you write some code to multiply large integers (implementing the method), you can appreciate it better.

svat 7y ago

(Was hoping someone else may answer your question, but as it appears that no one has…) Firstly, just in case it wasn't clear already, note that the algorithm is not intended for mental or manual arithmetic; its gains become apparent only when multiplying very large numbers (which is why I used 200 digits as an example). In particular, it wouldn't make sense to use it other than in cases where an addition and two subtractions are together faster than one multiplication at least — e.g. it wouldn't make sense to use it for numbers that can fit in a couple of machine words (say about 128 bits, or about 40 digits). If using it to multiply numbers by hand, I might use it for multiplying two 10-digit numbers but not anything smaller. So assuming you understand all that and are asking about the 103 * 1022 example just to see concretely what the idea is, then read on. With 1022 being a 4-digit number, we can take X=100, and write 103 as aX+b with a=1 and b=3, and similarly 1022 as cX+d with c=10 and d=22. Then just compute a+b, c+d, and the three products ac, bd, and (a+b)(c+d): a b a+b 1 03 4 10 22 32 c d c+d ac bd (a+b)(c+d) 10 66 128 (Each number in the last row above was computed by multiplying the two numbers directly above it.) Finally it only remains to compute (ad+bc) as a subtraction (here's where the savings come from; we don't have to multiply a with d, nor b with c — though in this example they'd be quite trivial anyway): 52 (a+b)(c+d)-ac-bd = 128-66-10 So we have the three quantities ac=10, (ad+bc)=52, and bd=66, giving the product to be (ac)X^2 + (ad+bc)X + bd (recall that X=100), which is 105266. Again, it's quite pointless to use this for such tiny examples, and in fact we haven't even used the recursive nature of the algorithm. If you write some code to multiply large integers (implementing the method), you can appreciate it better.