4 ms·

> in 1960, the 23-year-old Russian mathematician Anatoly Karatsuba took a seminar led by Andrey Kolmogorov [....] Kolmogorov asserted that there was no general

by svat 8y ago

> in 1960, the 23-year-old Russian mathematician Anatoly Karatsuba took a seminar led by Andrey Kolmogorov [....] Kolmogorov asserted that there was no general procedure for doing multiplication that required fewer than n^2 steps. Karatsuba thought there was—and after a week of searching, he found it. Karatsuba's method is beautiful and actually quite simple to explain. Suppose you want to multiply two 200-digit numbers. Write them as aX+b and cX+d, where X=10^100. We want to compute the product (aX+b)(cX+d), which is (ac)X^2 + (ad+bc)X + (bd). By the naive method, we'd end up effectively performing all four multiplications ac, ad, bc, bd. Karatsuba observed that we can do it with just three multiplications: ac, bd, and (a+b)(c+d) — and get our (ad+bc) as (a+b)(c+d)-ac-bd. Doing this recursively (so that T(n) = 3T(n/2) + O(n)) gives Karatsuba's method, cutting down the n^2 time of the naive method to about n^1.58 time. [1]: https://en.wikipedia.org/wiki/Karatsuba_algorithm https://en.wikipedia.org/wiki/Karatsuba_algorithm

mabbo 8y ago
You explain it really well. Thanks!
120bits 8y ago
Thank you for the explanation. I was wondering how I can apply karatsuba's method to multiply for e.g. 103 X 1022.
- svat 8y 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.
nopinsight 8y ago
Karatsuba’s algorithm is a shining example of creative applications of simple concepts. I used to teach math to gifted elementary school students and used some problems from Japanese exams for the talented. I think the creativity and complexity of thought required to come up with this algorithm is about the same as some solutions to a harder problem in those exams. (The creativity required to solve them is significantly more than for American Math Competition, which typically involves difficult but quite conventional thinking.) [1] More countries should adopt these Japanese-style problems in their gifted education as well as simpler versions for normal students. They are a great training ground for creative problem solving, which has become increasingly essential for successful careers in most fields. PS. Hong Kong holds annual creative math problem solving competition for primary and secondary school students: https://www.edb.gov.hk/en/curriculum-development/major-level-of-edu/gifted/resources_and_support/competitions/local/cps.html https://www.edb.gov.hk/en/curriculum-development/major-level... There was also at least one international math competition for primary students in Asia-Pacific which focuses on creative math problem solving. [1] AMC problems and solutions https://artofproblemsolving.com/wiki/index.php/AMC_Problems_and_Solutions https://artofproblemsolving.com/wiki/index.php/AMC_Problems_...
- brianpgordon 8y ago
  Interesting; I thought that a common criticism of Japanese-style education was that it's based to a large extent on rote memorization, whereas the West tends to focus more on concepts and creative thinking. Can you speak to that? Is the conventional wisdom wrong, or am I just wrong about what the conventional wisdom is?
  - jbay808 8y ago
    One anecdote: My North American math education seemed to focus on rote memorization, with little creative thinking at all. Did you have a different experience? Not sure how they teach math in Japan though.
    - 52-6F-62 8y ago
      Not necessarily related (and avoiding the attached political junk)— here in Ontario (Canada), the current government as ... strongly advocated... for going back to the "good old days" of rote memorization for the math curriculum versus modern discovery math methodology—ie: problem solving and creative thinking. There tend to be pillars of thought in NA.

by svat 8y ago

mabbo 8y ago

You explain it really well. Thanks!

120bits 8y ago

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

svat 8y 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.

nopinsight 8y ago

Karatsuba’s algorithm is a shining example of creative applications of simple concepts. I used to teach math to gifted elementary school students and used some problems from Japanese exams for the talented. I think the creativity and complexity of thought required to come up with this algorithm is about the same as some solutions to a harder problem in those exams. (The creativity required to solve them is significantly more than for American Math Competition, which typically involves difficult but quite conventional thinking.) [1] More countries should adopt these Japanese-style problems in their gifted education as well as simpler versions for normal students. They are a great training ground for creative problem solving, which has become increasingly essential for successful careers in most fields. PS. Hong Kong holds annual creative math problem solving competition for primary and secondary school students: https://www.edb.gov.hk/en/curriculum-development/major-level-of-edu/gifted/resources_and_support/competitions/local/cps.html https://www.edb.gov.hk/en/curriculum-development/major-level... There was also at least one international math competition for primary students in Asia-Pacific which focuses on creative math problem solving. [1] AMC problems and solutions https://artofproblemsolving.com/wiki/index.php/AMC_Problems_and_Solutions https://artofproblemsolving.com/wiki/index.php/AMC_Problems_...

brianpgordon 8y ago
Interesting; I thought that a common criticism of Japanese-style education was that it's based to a large extent on rote memorization, whereas the West tends to focus more on concepts and creative thinking. Can you speak to that? Is the conventional wisdom wrong, or am I just wrong about what the conventional wisdom is?
- jbay808 8y ago
  One anecdote: My North American math education seemed to focus on rote memorization, with little creative thinking at all. Did you have a different experience? Not sure how they teach math in Japan though.
  - 52-6F-62 8y ago
    Not necessarily related (and avoiding the attached political junk)— here in Ontario (Canada), the current government as ... strongly advocated... for going back to the "good old days" of rote memorization for the math curriculum versus modern discovery math methodology—ie: problem solving and creative thinking. There tend to be pillars of thought in NA.