CODEWITHSUNDEEP
calgorithmbigintegerlargenumber
Marko
Marko

Reputation: 1000

Toom-Cook multiplication algorithm implementation

I have a task to implement Toom-Cook 3-way multiplication algorithm. I'm following description on wikipedia http://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication , and I managed to store two big numbers into strings and split the strings into smaller ones according to the "Splitting" step on the wikipedia page. The next step is "evaluation", and I have to calculate a new number p0 = m0 + m2 ("Faster evaluation" by Bordrato - found on the same page) where m0 and m2 are the digits which I created by splitting the large number (in the previous step). The problem is that I cannot simply add up m0 and m2, since those two numbers can still be very large and impossible to add together in a standard way. Does this mean that I have to implement my own algorithm for adding large numbers (as well as substracting and dividing, since they are also needed), or am I missing something? If anyone could link me a possible implementation or even a pseudo code, it would be appreciated.

Upvotes: 0

Views: 4825

Answers (2)

Doug Currie
Doug Currie

Reputation: 41180

LibTomMath is open source and includes a Toom-Cook multiplication; have a look.

Upvotes: 0

rendon
rendon

Reputation: 2363

You have to implement your own methods for addition, subtraction, modulo, etc. Sometime ago I was trying to implement a BigInteger library and I have found some resources that may be useful for you.

  • BigNum Math book (as pointed by the previous answer)
  • Java OpenJdk BigInteger implementation, with documentation
  • Algorithms and data structures The basic toolbox, (I have learned Karatsube of this book).

By the way, I recommend to use base 2 for your numbers(see here.) because you can take advantage of the nature of the computer to make your operations more easy and fast.

Upvotes: 1

Related Questions