设计一个有效的算法，可以计算两个n位大整数的乘法运算。
如果按照我们日常的计算方法，应该就是将两个数逐位相乘，最后加起来得到最终的结果。由于是大整数乘法，那么我们用string来存储这两个数，因为是要做乘法，我们要从两个数的最低位开始乘，并且难免会有进位，所以我们打算翻转这两个string，使得更好操作一下。
string multiply(string num1,string num2)
{int len1=num1.length(),len2=num2.length();int len=len1+len2+1;reverse(num1.begin(),num1.end());reverse(num2.begin(),num2.end());//tmp储存每次乘法的结果，res储存最后相加的结果char res[len],tmp[len];for(int i=0;i<len;i++){res[i]='0'; tmp[i]='0';}for(int i=0;i<len1;i++){//jw储存每次乘法的进位，r_jw储存最后相加的进位int jw=0,r_jw=0;for(int j=0;j<len2;j++){tmp[j]=((num1[i]-'0')*(num2[j]-'0')+jw)%10+'0';int res_temp=(res[j+i]-'0')+(tmp[j]-'0')+r_jw;res[j+i]=res_temp%10+'0'; //储存最终结果jw=((num1[i]-'0')*(num2[j]-'0')+jw)/10;r_jw=res_temp/10;}//如果最高位有进位if(r_jw!=0||jw!=0){res[len2+i]=jw+r_jw+'0';//cout<<res[len2+i]<<endl; }}string result="";bool flag=false;for(int i=len-1;i>=0;i--){//遇到第一个正整数 if(res[i]!='0'&&!flag){result+=res[i];flag=true;}else if(flag)result+=res[i];}if(result=="") result="0";return result;
}
但是这样做算法复杂度是O(n^2)。我们想要用复杂度更低的算法来解决这个问题。
如果采取以上算法的话时间复杂度可以降低到O(n^log2(3))。
string Add(string num1,string num2)
{reverse(num1.begin(),num1.end());reverse(num2.begin(),num2.end());string res;int len1=num1.length();int len2=num2.length();int len=min(len1,len2);int jw=0;for(int i=0;i<len;i++){int tmp=(num1[i]-'0')+(num2[i]-'0')+jw;res+=char(tmp%10+'0');//cout<<"res1:"<<res[i]<<endl;jw=tmp/10;}if(len1<len2){for(int i=len;i<len2;i++){int tmp=(num2[i]-'0')+jw;res+=char(tmp%10+'0');//cout<<"res2:"<<res<<endl;jw=tmp/10;}if(jw)res+=jw+'0';}else if(len1>len2){for(int i=len;i<len1;i++){int tmp=(num1[i]-'0')+jw;res+=char(tmp%10+'0'); //cout<<"res3:"<<res<<endl;jw=tmp/10;}if(jw)res+=jw+'0';}elseif(jw)res+=jw+'0';reverse(res.begin(),res.end());return res;
}//num1>=num2
string Sub(string num1,string num2)
{reverse(num1.begin(),num1.end());reverse(num2.begin(),num2.end());int len1=num1.length();int len2=num2.length();int len=min(len1,len2);int jw=0;string res,result;for(int i=0;i<len;i++){int a=num1[i]-'0';int b=num2[i]-'0'+jw;if(a>=b){res+=char(a-b+'0');jw=0; }else{res+=char(a+10-b+'0');jw=1;}}for(int i=len;i<len1;i++){int a=num1[i]-'0';int b=jw;if(b==0)res+=num1[i];else if(a>=b){res+=char(a-b+'0');jw=0;}else if(a<b){res+=char(a+10-b+'0');jw=1;}}int flag=false;for(int i=res.length()-1;i>=0;i--){if(res[i]!='0'&&!flag){result+=res[i];flag=true;}else if(flag)result+=res[i];}return result;
}//两个n位大整数的乘法
string Multiply1(string num1,string num2,int n)
{string a,b,c,d,ac,ad,bc,bd,adbc;a=num1.substr(0,n/2);b=num1.substr(n/2);c=num2.substr(0,n/2);d=num2.substr(n/2);ac=multiply(a,c);ad=multiply(a,d);bc=multiply(b,c);bd=multiply(b,d);adbc=Add(ad,bc);for(int i=0;i<b.length()*2;i++)ac+="0";for(int i=0;i<b.length();i++)adbc+="0";string res=Add(ac,Add(adbc,bd));return res;
} //两个n位大整数的乘法
string Multiply2(string num1,string num2,int n)
{string a,b,c,d,a_b,c_d,ac,bd,a_bc_d,adbc;a=num1.substr(0,n/2);b=num1.substr(n/2);c=num2.substr(0,n/2);d=num2.substr(n/2);a_b=Add(a,b);c_d=Add(c,d);a_bc_d=multiply(a_b,c_d);ac=multiply(a,c);bd=multiply(b,d);adbc=Sub(a_bc_d,Add(ac,bd));for(int i=0;i<b.length()*2;i++)ac+="0";for(int i=0;i<b.length();i++)adbc+="0";string res=Add(ac,Add(adbc,bd));return res;
}
