高精度求平方根

高精度求平方根

高精度求平方根，思路就是二分+高精度加减乘除法 设数的长度为n，则需二分log(2,10^n)次即n*log(2,10) 约等于n*3.3，由于数的长度为n，朴素高精度乘法复杂度为o(n^2)。故朴素算法求解高精度平方根复杂度为O(n^3) 当然，你也可以用FFT优化下高精度乘法。 下面的代码实现了求大整数平方根的整数部分。

#include#include#include#includeusing namespace std;const int L=2015;string add(string a,string b) //只限两个非负整数相加{ string ans; int na[L]={0},nb[L]={0}; int la=a.size(),lb=b.size(); for(int i=0;ilb?la:lb; for(int i=0;i=0;i--) ans+=na[i]+'0'; return ans;}string sub(string a,string b) //只限大的非负整数减小的非负整数{ string ans; int na[L]={0},nb[L]={0}; int la=a.size(),lb=b.size(); for(int i=0;ilb?la:lb; for(int i=0;i0) ;lmax++; for(int i=lmax-1;i>=0;i--) ans+=na[i]+'0'; return ans;}string mul(string a,string b) //高精度乘法a,b,均为非负整数{ string s; int na[L],nb[L],nc[L],La=a.size(),Lb=b.size(); //na存储被乘数，nb存储乘数，nc存储积 fill(na,na+L,0);fill(nb,nb+L,0);fill(nc,nc+L,0); //将na,nb,nc都置为0 for(int i=La-1;i>=0;i--) na[La-i]=a[i]-'0'; //将字符串表示的大整形数转成i整形数组表示的大整形数 for(int i=Lb-1;i>=0;i--) nb[Lb-i]=b[i]-'0'; for(int i=1;i<=La;i++) for(int j=1;j<=Lb;j++) nc[i+j-1]+=na[i]*nb[j]; //a的第i位乘以b的第j位为积的第i+j-1位（先不考虑进位） for(int i=1;i<=La+Lb;i++) nc[i+1]+=nc[i]/10,nc[i]%=10; //统一处理进位 if(nc[La+Lb]) s+=nc[La+Lb]+'0'; //判断第i+j位上的数字是不是0 for(int i=La+Lb-1;i>=1;i--) s+=nc[i]+'0'; //将整形数组转成字符串 return s;}int sub(int *a,int *b,int La,int Lb){ if(La=0;i--) if(a[i]>b[i]) break; else if(a[i]=0;i--) if(a[i]) return i+1; //返回差的位数 return 0; //返回差的位数}string div(string n1,string n2,int nn) //n1,n2是字符串表示的被除数，除数,nn是选择返回商还是余数{ string s,v; //s存商,v存余数 int a[L],b[L],r[L],La=n1.size(),Lb=n2.size(),i,tp=La; //a，b是整形数组表示被除数，除数，tp保存被除数的长度 fill(a,a+L,0);fill(b,b+L,0);fill(r,r+L,0); //数组元素都置为0 for(i=La-1;i>=0;i--) a[La-1-i]=n1[i]-'0'; for(i=Lb-1;i>=0;i--) b[Lb-1-i]=n2[i]-'0'; if(La=0;i--) //将除数扩大10^t倍 if(i>=t) b[i]=b[i-t]; else b[i]=0; Lb=La; for(int j=0;j<=t;j++) { int temp; while((temp=sub(a,b+j,La,Lb-j))>=0) //如果被除数比除数大继续减 { La=temp; r[t-j]++; } } for(i=0;i=0) s+=r[i--]+'0'; //cout<=0) v+=a[i--]+'0'; if(v.empty()) v="0"; //cout<>t; while(t--) { cin>>n; n=DeletePreZero(n); cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。