2
$\begingroup$

I was studying Karatsuba multiplication where the complexity is reduced as compared to classical algorithm by splitting each number into two parts.

Now I'm trying to understand how the multiplication will take place when a number is divided into three parts instead of two.

I tried to solve the math but only came up with more number of multiplications than in Karatsuba.

Can someone help me out with this problem?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Donald Knuth, The Art of Computer Programming. $\endgroup$ – gnasher729 Oct 16 '17 at 6:31
  • 1
    $\begingroup$ Have you checked the Wikipedia page on Karatsuba's algorithm? $\endgroup$ – Yuval Filmus Oct 16 '17 at 7:47
2
$\begingroup$

The algorithm you are looking for seems to be the Toom-3 algorithm.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ (And to begin thinking about factors of dissimilar magnitude, check out "Toom-Cook-2.5"/"Toom32".) $\endgroup$ – greybeard Oct 16 '17 at 8:47

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.