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

21.35K views
0

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

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