Have Geek Brain

Fastest method to implement multiplication of numbers in strings (1,000,000 digits)

I want to write the fastest possible algorithm for 2 number multiplication. Each number has maximum digits of about 1,000,000 and is contained in the string.

Anyone would like to share this issue? I am looking for a really quick solution.

+2


a source to share


2 answers


You have to convert your string to binary representation of a number. After that, one of the fastest multiplication algorithms I know of is Karatsuba's .



+4


a source


To expand on Pablo's answer, let's say each number is a string of 1000008 decimal digits long. You can convert this as 111112 9-digit decimal numbers, each stored in UInt32. You have a multiplication algorithm. (Note that you will need to use UInt64 to store the result of the multiplication of the two UInt32 partitions, so you might need a 64-bit machine.) This should give you a 9 ^ 2 or 9 ^ log2 (3) speedup factor of 10, depending on from the algorithm.



0


a source






More articles:


All Articles