注：搬运自我的csdn博客 http://blog.csdn.net/qq_30172585
思想
高精度计算的核心思想很简单，就是模拟我们笔算的过程，因此，关键在于如何准确地模拟笔算
基础代码
因为高精度乘除法中会用到高精度加减法和比较大小函数，所以就先把加减和比较函数贴出来咯
int compare(string str1,string str2) //比较字符串型的“数字”大小，相等返回0，大于返回1，小于返回-1
{
if (str1.length() > str2.length()) return 1; //长度长的整数大于长度小的整数
else if (str1.length() < str2.length()) return -1;
else return str1.compare(str2); //若长度相等，则头到尾按位比较
}
string SUB_INT(string str1,string str2);
string ADD_INT(string str1,string str2) {//高精度加法
int sign = 1; //sign 为符号位
string str;
if (str1[0] == '-') //如果其中一个是负数，那么可以转化成高精度减法；如果都是负数，那么确定下结果为负数，然后擦除负号后相加
{
if (str2[0] == '-')
{
sign = -1;
str = ADD_INT(str1.erase(0,1),str2.erase(0,1));
}
else
{
str = SUB_INT(str2,str1.erase(0,1));
}
}
else
{
if (str2[0] == '-')
{
str = SUB_INT(str1,str2.erase(0,1));
}
else
{
int L1,L2;
L1 = str1.length();
L2 = str2.length();
if (L1 < L2) //在长度小的前面加0补齐，使得两数对齐
{
for (int i = 1;i <= L2-L1; i++) str1="0"+str1;
}
else
{
for (int i = 1;i <= L1-L2; i++) str2="0"+str2;
}
int int1 = 0,carry = 0; //carry 记录进位
for (int i = str1.length()-1;i >= 0; i--)
{
int1 = (int(str1[i])-'0'+ int(str2[i])-'0'+carry) % 10;
carry = (int(str1[i])-'0'+ int(str2[i])-'0'+carry) / 10;
str = char(int1 + '0') + str;
}
if (carry != 0) str = char(carry+'0') + str;
}
}
if ((sign==-1)&&(str[0]!='0')) str="-"+str; //处理符号位
return str;
}
string SUB_INT(string str1,string str2) {//高精度减法
int sign=1; //sign 为符号位
string str;
int i,j;
if (str2[0] == '-') //减一个负数等于加上它的相反数
{
str = ADD_INT(str1,str2.erase(0,1));
}
else
{
if (str1[0] == '-') //负数减去正数
{
sign = -1;
str = ADD_INT(str1.erase(0,1),str2);
}
else
{
int res = compare(str1,str2);
if (res == 0) return "0"; //两数相等则结果是0
if (res < 0) //被减数比较小，则符号先确定为负
{
sign = -1;
string temp = str1;
str1 = str2;
str2 = temp;
}
int tempint;
tempint=str1.length()-str2.length();
for (i=str2.length()-1;i>=0;i--)
{
if (str1[i+tempint]<str2[i]) //需要向前借位的情况
{
j=1;
while (1)
{
if (str1[i+tempint-j]=='0') //被借的位如果是 0 ，那么继续借位，并把当前的 0 变成 9
{
str1[i+tempint-j]='9';
j++;
}
else
{
str1[i+tempint-j]=char(int(str1[i+tempint-j])-1); // 被借的位如果不是 0 ，那么减去 1
break;
}
}
str=char(str1[i+tempint]-str2[i]+'0'+10)+str;
}
else
{
str=char(str1[i+tempint]-str2[i]+'0')+str;
}
}
for (i=tempint-1;i>=0;i--) str=str1[i]+str;
}
}
//去除结果中多余的前导0
str.erase(0,str.find_first_not_of('0'));
if (str.empty()) str="0";
if ((sign==-1) && (str[0]!='0')) str ="-"+str;
return str;
}
整数高精度乘法实现
乘法其实可以分解成多个一位数和高精度数相乘，然后相加的过程。只是要注意其中的进位补零。话不多说，代码才是真理：
string MUL_INT(string str1,string str2) { //高精度乘法
int sign = 1; //sign 为符号位
string str;
if (str1[0]=='-')
{ //确定结果正负
sign *= -1;
str1 = str1.erase(0,1);
}
if (str2[0]=='-')
{
sign *= -1;
str2 = str2.erase(0,1);
}
int L1,L2;
L1 = str1.length();
L2 = str2.length();
for (int i = L2-1;i >= 0;i--) //模拟手工乘法竖式
{
string temps; //temps存当前str2某一位乘于str1的结果
int int_res=0,carry=0,int2=str2[i]-'0'; //carry存进位的数量，int2存str2的某一位
if (int2 != 0)
{
for (int j = 1;j <= L2-1-i; j++) temps = "0"+temps; //这里就是上面所说的加上相应位数的 0 的操作
for (int j = L1-1;j >= 0;j--)
{
int_res = (int2 * (int(str1[j]) - '0') + carry) % 10;
carry = (int2 *(int(str1[j]) - '0') + carry) / 10;
temps = char(int_res + '0') + temps;
}
if (carry != 0) temps = char(carry +'0') + temps;
}
str = ADD_INT(str,temps); //这里就是上面所说的乘法是基于加法的
}
//去除结果中的前导0
str.erase(0,str.find_first_not_of('0'));
if (str.empty()) str = "0";
if ((sign==-1) && (str[0]!='0')) str = "-" + str;
return str;
}
----------------------------写在文章中间-------------------------------------------------
其实下面要介绍的整除和 高精度浮点数运算 其实用处不大，我也是因为这次PROJECT才心血来潮写的，有时间有兴趣的就看看吧，程序设计还有很多更值得你花时间的东西，所以不一定要花时间在这里。
----------------------------写在文章中间-------------------------------------------------
整数高精度除法（整除）实现
整除的话要先判断除数是不是0，其次判断被除数有没有比除数小，如果有的话，直接返回 0 ，否则才进行试商--这是除法最核心的的步骤：
（PS:整除的同时其实也是取模的过程，因此可以一个函数当两个用）
上代码：
string DIVIDE_INT(string str1,string str2,int flag) {//高精度除法。flag==1时,返回商; flag==0时,返回余数
string quotient,residue; //定义商和余数
int sign1=1,sign2=1;
if (str2 == "0")
{ //判断除数是否为0
quotient= "ERROR!";
residue = "ERROR!";
if (flag==1) return quotient;
else return residue ;
}
if (str1=="0")
{ //判断被除数是否为0
quotient="0";
residue ="0";
}
if (str1[0]=='-')
{
str1 = str1.erase(0,1);
sign1 *= -1;
sign2 = -1;
}
if (str2[0]=='-')
{
str2 = str2.erase(0,1);
sign1 *= -1;
}
int res=compare(str1,str2);
if (res<0)
{
quotient="0";
residue =str1;
} else if (res == 0)
{
quotient="1";
residue ="0";
} else
{
int L1,L2;
L1=str1.size();
L2=str2.size();
string tempstr;
tempstr.append(str1,0,L2-1);
for (int i=L2-1;i<L1;i++) { //模拟手工除法竖式
tempstr=tempstr+str1[i];
tempstr.erase(0,tempstr.find_first_not_of('0'));
if (tempstr.empty()) tempstr="0";
for (char ch='9';ch>='0';ch--)
{ //试商
string str;
str=str+ch;
if (compare(MUL_INT(str2,str),tempstr)<=0)
{
quotient=quotient+ch;
tempstr =SUB_INT(tempstr,MUL_INT(str2,str));
break;
}
}
}
residue=tempstr;
}
//去除结果中的前导0
quotient.erase(0,quotient.find_first_not_of('0'));
if (quotient.empty()) quotient="0";
if ((sign1==-1)&&(quotient[0]!='0')) quotient="-"+quotient;
if ((sign2==-1)&&(residue [0]!='0')) residue ="-"+residue ;
if (flag==1) return quotient;
else return residue ;
}
string DIV_INT(string str1,string str2) {//高精度除法,返回商
return DIVIDE_INT(str1,str2,1);
}
string MOD_INT(string str1,string str2) {//高精度除法,返回余数
return DIVIDE_INT(str1,str2,0);
}
浮点数的高精度运算
1.加法和减法，只需要将小数点对齐，不足的地方用 0 补全，然后擦除小数点就可以运算了，最后别忘了把小数点加进去
2.乘法的话，记下两个数小数点后面的位数，然后擦除小数点像整数一样运算，同样最后别忘了在结果上加上小数点
3.除法比较复杂，还要考虑除不尽的，这个东西在这里说简直一言难尽，唉，直接上代码吧（加减和乘法容易实现，就不贴代码了）
void TurnInt(string &s1,string &s2)
{
int after_point1,after_point2;
int pos1 = s1.find_first_of('.');
int pos2 = s2.find_first_of('.');
int L1=s1.length() ;
int L2=s2.length() ;
if(pos1 >= 0 && pos1 < L1-1) after_point1 = s1.length() - pos1 -1;
else after_point1 = 0;
if(pos2 >= 0 && pos2 < L2-1) after_point2 = s2.length() - pos2 -1;
else after_point2 = 0;
int ab = abs(after_point1 - after_point2);
if(after_point1!=0 && after_point1 < after_point2)
{
s1.erase(pos1,1);
for (int i = 1;i <= ab; i++) s1= s1 + "0";
s2.erase(pos2,1);
}
else if(after_point2!=0 && after_point1 >= after_point2)
{
s1.erase(pos1,1);
for (int i = 1;i <= ab; i++) s2= s2 + "0";
s2.erase(pos2,1);
}
else if(after_point1 == 0)
{
s2.erase(pos2,1);
for (int i = 1;i <= ab; i++) s1= s1 + "0";
}
else if(after_point2 == 0)
{
s1.erase(pos1,1);
for (int i = 1;i <= ab; i++) s2= s2 + "0";
}
}
string DIVIDE_INT(string str1,string str2) {//高精度浮点数除法。
string quotient,residue; //商和余数
int sign1=1,sign2=1;
if (str2 == "0") { //判断除数是否为0
return "ERROR!";
}
if (str1[0]=='-') {
str1 = str1.erase(0,1);
sign1 *= -1;
sign2 = -1;
}
if (str2[0]=='-') {
str2 = str2.erase(0,1);
sign1 *= -1;
}
if((str1.find_first_of('.')>=0 && str1.find_first_of('.')<=str1.length()-1) || (str2.find_first_of('.')>=0 && str2.find_first_of('.')<=str2.length()-1))
{
TurnInt(str1,str2);
}
str1.erase(0,str1.find_first_not_of('0'));
str2.erase(0,str2.find_first_not_of('0'));
int L1,L2;
L1=str1.length();
L2=str2.length();
string tempstr;
tempstr.append(str1,0,L2-1);
int i=L2-2;
int cnt = 0;
while(i++,tempstr!="0" || i<=L1-1) //模拟手工除法竖式
{
if(i>L1-1)
{
if(cnt >= 50) break; //确定保留的最大位数
cnt++;
tempstr=tempstr+"0";
}
else
tempstr=tempstr+str1[i];
tempstr.erase(0,tempstr.find_first_not_of('0'));
if (tempstr.empty()) tempstr="0";
for (char ch='9';ch>='0';ch--) //试商
{
string str;
str=str+ch;
if (compare(MUL_INT(str2,str),tempstr)<=0)
{
quotient=quotient+ch;
tempstr =SUB_INT(tempstr,MUL_INT(str2,str));
break;
}
}
}
int ql = quotient.length();
if(cnt > 0) quotient.insert(ql-cnt,".");
if(quotient[0] == '.') quotient = "0" + quotient;
if(quotient[quotient.find_first_not_of('0')] != '.') quotient.erase(0,quotient.find_first_not_of('0')); //去除结果中的前导0
if (quotient.empty()) quotient="0";
if ((sign1==-1)&&(quotient[0]!='0')) quotient="-"+quotient;
return quotient;
}
网友评论