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

493 viewsAlgorithms
0

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

 

 

Answered question
0
Golibrary (anonymous) 0 Comments

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

Changed status to publish
0

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)]
            else:
                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))
            else:
                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
Write your answer.

Categories