3
$\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?

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

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ (And to begin thinking about factors of dissimilar magnitude, check out "Toom-Cook-2.5"/"Toom32".) $\endgroup$
    – greybeard
    Oct 16, 2017 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.