读书人
栏目▼

求帮优化 小弟我的高精度加减法以及乘

发布时间： 2013-09-29 11:07:08 作者： rapoo

求帮优化 我的高精度加减法以及乘法模块
本帖最后由 SureEdding 于 2013-09-04 21:24:22 编辑 



//高精度加法

void plus(char *a, char *b, char *c)
{
int i, j, l;
int length1, length2;
int A[10005] = { 0 }, B[10005] = { 0 }, C[10005] = { 0 }, D[10005] = { 0 };
length1 = strlen(a);
length2 = strlen(b);
int counter = 0;

if (length1 >= length2)//取A和B较长的长度
l = length1;
else
l = length2;

for (i = 0; i < length1; i++)//将字符串转化为整形数组

{

A[i] = a[length1 - i - 1] - '0';

}

for (i = 0; i < length2; i++)
{

B[i] = b[length2 - 1 - i] - '0';

}

for (i = 0; i < l; i++)

{

C[i] += A[i] + B[i];   //c[i]表示结果的第i位

if (C[i] >= 10)   //当前的位和大于等于10 需进位

{

C[i + 1]++;   //下一位加1

C[i] -= 10;  //当前位减去10

}

}

if (C[l] > 0) l++; //处理最高位是否进位

//如999+1=1000 此时长度为l+1
for (i = 0; i < l; i++)
D[i] = C[l - i - 1];

j = 0;
for (i = 0; i < l; i++)
{
if (D[i] == 0)
{
counter++;
continue;
}
else
{
c[j++] = D[i] + '0';
goto o;
}
}
o:
for (j; j < l - counter; j++)
{
c[j] = D[++i] + '0';
}
c[j] = '\0';
if (c[0] == '\0')
{
c[0] = '0';
c[1] = '\0';
}
return;
}

//高精度减法

void minus(char *a, char *b, char *c)
{
int i, l;
int length1, length2;
int A[10005] = { 0 }, B[10005] = { 0 }, C[10005] = { 0 }, D[10005] = { 0 };
length1 = strlen(a);
length2 = strlen(b);

if (length1 > length2)
{
p:
if (length1 >= length2)//取A和B较长的长度
l = length1;
else
l = length2;

for (i = 0; i < length1; i++)//将字符串转化为整形数组

{

A[i] = a[length1 - i - 1] - '0';

}

for (i = 0; i < length2; i++)
{

B[i] = b[length2 - 1 - i] - '0';

}
for (i = 0; i < l; i++)

{

C[i] += (A[i] - B[i]);

if (C[i] < 0)  //借位操作

{

C[i + 1]--;

C[i] += 10;

}

}

while (C[l] == 0 && l > 0)

{

l--;

}

for (i = 0; i < l + 1; i++)
c[i] = C[l - i] + '0';

c[l + 1] = '\0';for (i = 0; i <= l; i++)
return;
}
else if (length1 < length2)
{
q:
if (length1 >= length2)//取A和B较长的长度
l = length1;
else
l = length2;

for (i = 0; i < length1; i++)//将字符串转化为整形数组

{

A[i] = a[length1 - i - 1] - '0';

}

for (i = 0; i < length2; i++)
{

B[i] = b[length2 - 1 - i] - '0';

}
for (i = 0; i < l; i++)

{

C[i] += (B[i] - A[i]);

if (C[i] < 0)  //借位操作

{

C[i + 1]--;

C[i] += 10;

}

}

while (C[l] == 0 && l > 0)

{

l--;

}

c[0] = '-';
for (i = 1; i < l + 2; i++)
c[i] = C[l - i + 1] + '0';

c[l + 2] = '\0';
return;
}
else
{
int P = strcmp(a, b);
if (P > 0)
goto p;
else if (P < 0)
goto q;
else
{
for (i = 0; i < length1; i++)
if (i == length1 - 1)
{
c[0] = '0';
c[1] = '\0'; 
 
}
}
}

}

//高精度乘法

void multiply(char* a, char* b, char* c)
{
int i, j, ca, cb, *s;
ca = strlen(a);
cb = strlen(b);
s = (int*) malloc(sizeof(int) * (ca + cb));
for (i = 0; i < ca + cb; i++)
s[i] = 0;
for (i = 0; i < ca; i++)
for (j = 0; j < cb; j++)
s[i + j + 1] += (a[i] - '0') * (b[j] - '0');
for (i = ca + cb - 1; i >= 0; i--)
if (s[i] >= 10)
{
s[i - 1] += s[i] / 10;
s[i] %= 10;
}
i = 0;
while (s[i] == 0)
i++;
for (j = 0; i < ca + cb; i++, j++)
c[j] = s[i] + '0';
c[j] = '\0';
free(s);
}

进行超大数据运算的时候觉得耗时太多

。。PS
如果我想将高精度乘法改成万进制该如何修改？？
[解决办法]
思路跟你学的10进制是一样的，
你把超大整数很多1位数，这边把超大整数 每4位分解成一个short的整数

1位数的加算 --》 4位数的加算，也就是2个short的加算，
超过10000，就进位，

static void Ladd(const short *a, const short *b, const int n, short *c)
{
short i, cy = 0;

for (i = n- 1; i >= 0; i--) {
c[i] = a[i] + b[i] + cy;
if (c[i] < 10000) {
cy = 0;
} else {
c[i] = c[i] - 10000;
cy = 1;
}
}
}
[解决办法]
GMP库参考一下。如果嫌庞大，参考下面：
#include <iostream>
#include <string>
using namespace std;
inline int compare(string str1,string str2) {//相等返回0，大于返回1，小于返回-1
         if (str1.size()>str2.size()) return 1; //长度长的整数大于长度小的整数
    else if (str1.size()<str2.size()) 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 { //把两个整数对齐，短整数前面加0补齐
            string::size_type L1,L2;
            int i;
            L1=str1.size();
            L2=str2.size();
            if (L1<L2) {
                for (i=1;i<=L2-L1;i++) str1="0"+str1;
            } else {
                for (i=1;i<=L1-L2;i++) str2="0"+str2;
            }
            int int1=0,int2=0; //int2 记录进位
            for (i=str1.size()-1;i>=0;i--) {
                int1=(int(str1[i])-'0'+int(str2[i])-'0'+int2)%10;
                int2=(int(str1[i])-'0'+int(str2[i])-'0'+int2)/10; 
 
                str=char(int1+'0')+str;
            }
            if (int2!=0) str=char(int2+'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 {
        int res=compare(str1,str2);
        if (res==0) return "0";
        if (res<0) {
            sign=-1;
            string temp =str1;
            str1=str2;
            str2=temp;
        }
        string::size_type tempint;
        tempint=str1.size()-str2.size();
        for (i=str2.size()-1;i>=0;i--) {
            if (str1[i+tempint]<str2[i]) {
                j=1;
                while (1) {//zhao4zhong1添加
                    if (str1[i+tempint-j]=='0') {
                        str1[i+tempint-j]='9';
                        j++;
                    } else {
                        str1[i+tempint-j]=char(int(str1[i+tempint-j])-1);
                        break;
                    }
                }
                str=char(str1[i+tempint]-str2[i]+':')+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 i,j;
    string::size_type L1,L2;
    L1=str1.size();
    L2=str2.size();
    for (i=L2-1;i>=0;i--) { //模拟手工乘法竖式
        string tempstr;
        int int1=0,int2=0,int3=int(str2[i])-'0';
        if (int3!=0) {
            for (j=1;j<=(int)(L2-1-i);j++) tempstr="0"+tempstr;
            for (j=L1-1;j>=0;j--) {
                int1=(int3*(int(str1[j])-'0')+int2)%10; 
 
                int2=(int3*(int(str1[j])-'0')+int2)/10;
                tempstr=char(int1+'0')+tempstr;
            }
            if (int2!=0) tempstr=char(int2+'0')+tempstr;
        }
        str=ADD_INT(str,tempstr);
    }
    //去除结果中的前导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 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 {
        string::size_type 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'));//zhao4zhong1添加
            if (tempstr.empty()) tempstr="0";//zhao4zhong1添加
            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);
}
int main() {
    char ch;
    string s1,s2,res;

    while (cin>>s1>>ch>>s2) {
        switch (ch) {
            case '+':res=ADD_INT(s1,s2);break;
            case '-':res=SUB_INT(s1,s2);break;
            case '*':res=MUL_INT(s1,s2);break;
            case '/':res=DIV_INT(s1,s2);break;
            case '%':res=MOD_INT(s1,s2);break;
            default :                   break;
        }
        cout<<res<<endl;
    }
    return(0);
}

[解决办法]
大数运算，不是有对应的算法么，用算法优化才是真的。大师的算法，你就自己去网上查吧。
我给你说个简单的吧，比如A,B为1000位整数,令A=a1*10^500+a2,B=b1*10^500 + b2,
那么A*B = a1*b1*10^1000 + (a1*b2+a2*b1)*10^500 + a2*b2
= a1*b1*10^1000 + [(a1+b1)*(a2+b2) - a1*b1 - a2*b2]*10^500 + a2*b2
如此便能用归并的思想递归。
计算下2者的复杂度,假设2个大数都为N位，主要考虑乘法运算的次数，那么你的不用说就是N^2。
而归并，第二步的优化后，计算式只需3次乘法。每个函数调用3个子函数，层数为logN - 1，那么总的复杂度为3*3^(logN - 1) = 3^logN。
或许你认为指数级的要高，但你用10w，100w，去试试就知道N^2 和 3^logN差多少了。

读书人网 >C语言

热点推荐

触屏版 | 电脑版

读书人网 m.reader8.net