If we want to multiply strings with 100k digits or more, which algorithm is fast enough to achieve this ?
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)] else: return [num] 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 = *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 = *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 ---