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?
I'll do an example.
abcdef(ghijkl)
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.