What is the best algorithm for multiplying very large numeric strings (50k or more digits)?
If we want to multiply strings with 100k digits or more, which algorithm is fast enough to achieve this ?
Algorithmist 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)]
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 ---
goli202084 Changed status to publish
Write your answer.