What are the min and max number of single digit multiplications, involved in recursive karatsubha multiplication of two 6 digit decimal numbers?

I found different results on different numbers. But I found a general answer of 12 to all such multiplications in the following source https://onlinecourses.nptel.ac.in/programming101/link?unit=156 (Question 3) Whats your comment on the authenticity of the answer?

  • $\begingroup$ This is a good homework question, as it requires you to not only understand how to do the Karatsuba method, but to derive the complexity of the algorithm. The exercise is lost if you do not attempt to reason through with an answer. So, what have you tried? $\endgroup$ – user109879 Oct 13 '14 at 21:26
  • $\begingroup$ @Chantry Cargill I have tried it on 132423 X 143412 and got 21 multiplications.. On higher numbers I've got even higher numbers. I expect the above multiplication to be the least. I've no idea how the answer is 12 to all numbers.. I've drilled my head continuously for past 2 days.. $\endgroup$ – Hari Oct 13 '14 at 21:31
  • $\begingroup$ 21 can be reduced to 18 in fact.. $\endgroup$ – Hari Oct 13 '14 at 21:34
  • $\begingroup$ I'm looking at his result, and it appears to be best case scenario. I'll see if I can post an example if I have some time, but multiplications can definitely be greater than 12. $\endgroup$ – user109879 Oct 13 '14 at 21:50
  • $\begingroup$ Best case scenario I got is 18 that what im saying.. PLease post an example of 12 multis,, U cant multiply 111111 X 111111 though... I feel the question is absurd that which was asked on the link.. @Chantry Cargill $\endgroup$ – Hari Oct 13 '14 at 21:52

I'll do an example.


We split abcdef into abc and def and ghijkl into ghi and jkl we have

We have abcdef(ghijkl) = abc(ghi)($B^{2m}$) + $B^m$((abc + def)(ghi + jkl) - abc(ghi) - def(jkl)) + def(jkl).

Now, lets be ultra conservative. Lets assume that each of the additions stay within 3 digits.

abc(ghi) = a(g)($B^{2m}$) + $B^m$((a + bc)(g + hi) - a(g) - bc(hi)) + bc(hi)

Lets assume a(g) is 1 multiplication. Our counter can now be set to 1 multiplication. Now stepping down with bc(hi) we have 3 more multiplications which adds to 4 total now.

Lets assume both (a + bc) and (g + hi) are 2 digit numbers. Then the multiplication produces 3 new multiplications, now totalling 7. Notice all of these came from multiplying abc(ghi). If we move up to def(jkl), we automatically hit 14 multiplications. Then 21 from (abc + def)(ghi + jkl).

So your logic is sound. 12 is too small of a number.

  • $\begingroup$ Wanna know how I got 18? abc(ghi), ag can be used twice, thus reducing one multiplication. On total, 3 multiplications (taking inti account other 3X3 mutiplications). BUt the source is from IIT madras, a very very nice institution(u can check qs rankings computer science or mathematics).So does such errors happen with profs of such prestigious situations also? Whats your experience? $\endgroup$ – Hari Oct 13 '14 at 22:12
  • $\begingroup$ I've never gone to a prestigious institution, but everyone makes mistakes. It appears he was cutting the algorithm short, but I'm not sure where the 4 came into his calculations. $\endgroup$ – user109879 Oct 13 '14 at 22:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.