What is the best algorithm for multiplying very large numeric strings (50k or more digits)?

1.12K viewsAlgorithms

If we want to multiply strings with 100k digits or more, which algorithm is fast enough to achieve this ?



Answered question

Fast multiplication of very large numeric strings can be easily achieved in O(n log n) time complexity using FFT multiplication.


Below is a python code which illustrates this for multiplication of strings with 1,60,000 digits. The algorithm is fast enough for even bigger strings than this.



import math
import time
  class Solution:
    def fft(self,num,opt):
        n = len(num)
        if n == 1:
            if opt == 1:
                return [complex(int(num[0]),0)]
                return [num[0]]
               A1 = self.fft(num[::2],opt)
        A2 = self.fft(num[1::2],opt)
        w1 = complex(math.cos(2*math.pi/n),opt*math.sin(2*math.pi/n))
        w = complex(1,0)
        A = [0]*n
                 for i in range(0, n//2):
            A[i] = A1[i] + w*A2[i]
            A[i+n//2] = A1[i] - w*A2[i]
            w = w * w1
                 return A

     def multiply(self, num1, num2):
        length = len(num1) + len(num2)
        n = 1
        while n < length:
            n = n<<1
        # n - That is, the number of digits after multiplication, satisfying the multiplication will not overflow, and is a power of 2
        A1 = self.fft(num1.zfill(n)[::-1],1)
        A2 = self.fft(num2.zfill(n)[::-1],1)
        A = [0]*n
        for i in range(n):
            A[i] = A1[i]*A2[i]
        Ans = self.fft(A,-1)
        rtn = ''
        #up - used for carry
        up = 0
        for num in Ans:
            hre = int(num.real/n+0.5+up)
            if hre >= 10:
                up = int(hre/10)
                rtn += str(int(hre%10))
                up = 0
                rtn += str(hre)
        rtn = rtn[::-1].lstrip('0')
        # Avoid returning an empty string when the result is 0
        if rtn == '':
            return '0'
        return rtn

   M = Solution()
   start_time = time.time()
   number = '123238534785435'
   # Replace above string with the ultra large string from this link:- https://pastebin.com/J1mHcrLs
   print (M.multiply(number, number))
   print("\n--- Multiplication of two 1,60,000 character strings took %s seconds ---" % (time.time() - start_time))

   # Output of the time taken for 160k digit multiplication:- --- Multiplication of two 1,60,000 character strings took 10.12393307685852 seconds ---



Changed status to publish
Golibrary (anonymous) 0 Comments

Try executing the above code on http://code.golibrary.co:8000

Changed status to publish
Write your answer.