大数运算——加减乘除和求平方根

大数加法，从低位开始，依次运算，注意进位即可。
大数减法，从低位开始，按位依次做减法，注意借位即可。
大数乘法（此处为高精度*高精度），用到移位和加法（都是对数组进行操作）。以123*456为例说明算法运行过程。先令结果ans数组置零，第一步，计算6*123，结果保存在数组temp1中，再向左移动0位，低位补零。再将ans与temp1相加，相加的结果保存在ans中。第二步，用5*123,结果保存在temp1中，再向左移动1位，低位补零。再将ans与temp1相加，相加的结果保存在ans中.第三步，用4*123,结果保存在temp1中，再向左移动2位，低位补零。再将ans与temp1相加，相加的结果保存在ans中。
大数除法，就是不断做减法的过程,以7654/23为例，说明算法运行过程，设”7654”的长度为len1=4,”23”为len2=2,nTimes=len1-len2=2;第一步，将”23”左移nTimes位，低位补零，即变为“2300”.在用“7654”-“2300”,够减，则用结果“5354”替代“7654”,以便进行下一次运算。并且ans[nTimes]++。然后，用“5354-2300”,够减，则用结果“3054”替代“5354”,以便进行下一次运算。并且ans[nTimes]++.再用“3054”-“2300”，,够减，则用结果“754”替代“3054”,以便进行下一次运算。并且ans[nTimes]++.再用“754”-“2300”，不够减，则将“23”左移nTimes-1位，低位补零，变为“230”.用“754”-“230”,够减，则用结果“524”替代“754”,以便进行下一次运算。并且ans[nTimes-1]++.继续用“524”-“230”，,够减，则用结果“294”替代“524”,以便进行下一次运算。并且ans[nTimes-1]++，继用“294”-“230”，,够减，则用结果“64”替代“294”,以便进行下一次运算。并且ans[nTimes-1]++，继续用“64”-“230”，不够减，则将“23”左移nTimes-2位，低位补零，变为“23”.在用“64”-“23”,够减，则用结果“41”替代“64”,以便进行下一次运算。并且ans[nTimes-2]++。在用“41”-“23”,够减，则用结果“18”替代“41”,以便进行下一次运算。并且ans[nTimes-2]++。在用“18”-“23”,不够减。算法结束。逆序输出ans的值即为结果.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int compare(int a[],int b[],int len1,int len2);
int add(int a[],int len2);
int sub(int a[],int b[],int len1,int len2);
int mul(int a[],int len2,int ans[]);
int division(int a[],int ans[]);
int main()
{
    char ch;
    char input[25];
    int i,j,k,len1,len2,num;
    int a[12],b[12],ans[25];
    memset(a,0,sizeof(a));
    memset(b,sizeof(b));
    memset(ans,sizeof(ans));
    for(i=0;scanf("%c",&input[i])==1&&input[i]!='n';i++);
    ch=input[0];
    for(j=i-1,k=0;input[j]!=' ';j--,k++)
    {
        b[k]=input[j]-'0';
    }
    len2=k;
    for(i=j-1,k=0;input[i]!=' ';i--,k++)
    {
        a[k]=input[i]-'0';
    }
    len1=k;
    if(ch=='+')
    {
        num=add(a,b,len2);
        if(num==-1)
        {
            printf("0n");
            return 0;
        }
        else
        {
            for(i=num;i>=0;i--)
                printf("%d",a[i]);
        }
    }
    else if(ch=='-')
    {
        if(compare(a,len2)==0)
        {
            printf("0n");
            return 0;
        }
        else if(compare(a,len2)>0)
        {
            num=sub(a,len2);
            if(num==-1)
            {
                printf("0n");
                return 0;
            }
            else
            {
                for(i=num;i>=0;i--)
                    printf("%d",a[i]);
            }
        }
        else if(compare(a,len2)<0)
        {
            num=sub(b,a,len1);
            if(num==-1)
            {
                printf("0n");
                return 0;
            }
            else
            {
                printf("-");
                for(i=num;i>=0;i--)
                    printf("%d",b[i]);
            }
        }
    }
    else if(ch=='*')
    {
        num=mul(a,ans);
        if(num==-1)
        {
            printf("0n");
            return 0;
        }
        else
        {
            for(i=num;i>=0;i--)
                printf("%d",ans[i]);
        }
    }
    else if(ch=='/')
    {
        if(compare(a,len2)==0)
        {
            printf("1n");
            return 0;
        }
        else if(compare(a,len2)>0)
        {
            num=division(a,ans);
            if(num==-1)
            {
                printf("0n");
                return 0;
            }
            else
            {
                for(i=num;i>=0;i--)
                    printf("%d",ans[i]);
            }
        }
        else if(compare(a,len2)<0)
        {
            printf("0n");
            return 0;
        }
    }

    printf("n");
    return 0;
}


//比较两个运算对象的大小.如果a>b,返回1.如果a==b,返回0.如果a<b,返回-1
int compare(int a[],int len2)
{
    if(len1>len2)
        return 1;
    else if(len1<len2)
        return -1;
    else if(len1==len2)
    {
        int i;
        for(i=len1;i>=0;i--)
        {
            if(a[i]>b[i])
                return 1;
            else if(a[i]<b[i])
                return -1;
        }
        if(i<0)
            return 0;
    }
}

//加法运算。运算结果为0,则返回-1.运算结果不为0,返回运算结果最高位的下标
//a,b存放两个操作数，运算结果存放于a中,len1代表数组a的维数,len2代表数组b的维数。
int add(int a[],int len2)
{
    int i,d=0;//d代表低位向高位的进位，即第i-1位对第i位(当前位)的进位。
    int num=len1>len2?len1:len2;
    for(i=0;i<num;i++)//当i=num时,计算的是a,b最高位向更高位的进位
    {
        int s=a[i]+b[i]+d;
        a[i]=s%10;
        d=s/10; } if(d) a[i]=d; for(i=num;i>=0;i--) { if(a[i]!=0) break; } return i; } //减法运算.a-b,并且运算结果存放在a中.运算结果为0,返回运算结果最高位的下标
int sub(int a[],int len2) {
    int i,d=0;//d代表低位向高位的借位。即第i-1位对第i位(当前位)的借位
    int num=len1>len2?len1:len2;
    for(i=0;i<num;i++)
    {
        int s=a[i]-b[i]-d;
        if(s>=0)
        {
            a[i]=s;
            d=0;
        }
        else
        {
            a[i]=s+10;
            d=1;
        }
    }
    for(i=num;i>=0;i--)
    {
        if(a[i]!=0)
            break;
    }
    return i;
}

//乘法运算,运算结果为0,返回运算结果最高位的下标
int mul(int a[],int ans[])
{
    int i,num,t=1,m=0;
    int temp1[25];
    for(i=0;i<len2;i++)
    {
        int c=0,k=0;
        memset(temp1,sizeof(temp1));
        for(j=0;j<len1;j++)
        {
            int s=b[i]*a[j]+c;
            temp1[k++]=s%10;
            c=s/10; } if(c)//最高位向更高位的进位
            temp1[k]=c; 
        for(j=k;j>=0;j--)//乘积结果temp1依次左移0位,1位,2位....
        {
            temp1[j+m]=temp1[j];
        }
        for(j=m-1;j>=0;j--)//低位补0
            temp1[j]=0;
        num=add(ans,temp1,t,k+m+1);
        t=num+1;
        m++;
    }
    for(i=num;i>=0;i--)
    {
        if(ans[i]!=0)
            break;
    }
    return i;
}

//除法运算,由于受main()中的条件控制，只有当a>b,才会调用该函数
//运算结果不为0,返回运算结果最高位的下标
int division(int a[],nTimes=len1-len2,temp1[12];//temp1用于存放除数移位后的数据
    for(i=0;i<=nTimes;i++)
    {
        memset(temp1,sizeof(temp1));
        //除数向高移nTimes-i位,低位补0,也就是左移nTimes-i位，低位补0.
        for(j=len2-1,k=j+nTimes-i;j>=0;j--,k--)
        {
            temp1[k]=b[j];
        }
        for(j=k;j>=0;j--)
        {
            temp1[j]=0;
        }
        while(compare(a,len2+nTimes-i)>=0)
        {
            len1=sub(a,len2+nTimes-i)+1;
            ans[nTimes-i]++;
        }
    }
    for(i=nTimes;i>=0;i--)
    {
        if(ans[i]!=0)
            break;
    }
    return i;
}

//改进的代码，主要是修改了乘法运算，并且增加了求根运算

//大数运算，包括加减乘除和求平方根
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXN 1100
char n[MAXN];
char m[MAXN];
int num1[MAXN];
int num2[MAXN];
int ans[MAXN];

int compare(int a[],int len2);
int sqrt(int ans[],int a[],int len);
int Div(int ans[],int len2);
int mul(int ans[],int len2);
int add(int a[],int len2);

int main()
{
    int i,len;
    char c;
    printf("请输入两个数n");
    scanf("%s%s",n,m);
    printf("请输入运算符号（#代表求根号）n");
    getchar();
    scanf("%c",&c);
    int len1=strlen(n);
    for(i=0,j=len1-1;i<len1;i++,j--)
        num1[i]=n[j]-'0';
    int len2=strlen(m);
    for(i=0,j=len2-1;i<len2;i++,j--)
        num2[i]=m[j]-'0';
    if(c=='+')
    {
        len=add(num1,num2,len2);
        for(i=len-1;i>=0;i--)
            printf("%d",num1[i]);
    }
    else if(c=='-')
    {
        len=sub(num1,len2);
        for(i=len-1;i>=0;i--)
            printf("%d",num1[i]);
    }
    else if(c=='*')
    {
        len=mul(ans,num1,ans[i]);
    }
    else if(c=='/')
    {
        len=Div(ans,ans[i]);
    }
    else if(c=='#')
    {
        len=sqrt(ans,len1);
        printf("第一个操作数的平方根为：");
        for(i=len-1;i>=0;i--)
            printf("%d",ans[i]);
        printf("n第二个操作数的平方根为：");
        len=sqrt(ans,ans[i]);
    }
    printf("n");
    return 0;
}

//大数加法运算，运算结果保存在a中，函数返回运算结果的位数
int add(int a[],len=len1>len2?len1:len2,c=0,j;
    for(i=0;i<len;i++)
    {
        int s=a[i]+b[i]+c;
        c=s/10; a[i]=s%10; } if(c) a[i]=c; for(j=i;j>=0;j--) { if(a[j]) break; } return j+1; } //大数减法运算，运算结果保存在a中，函数返回运算结果位数
int sub(int a[],c=0;
    for(i=0;i<len;i++)
    {
        int s=a[i]-b[i]-c;
        if(s>=0)
        {
            c=0;
            a[i]=s;
        }
        else
        {
            c=1;
            a[i]=s+10;
        }
    }
    for(j=i;j>=0;j--)
    {
        if(a[j])
            break;
    }
    return j+1;
}

int mul(int ans[],j;
    memset(ans,sizeof(ans)*MAXN);
    for(i=0;i<len2;i++)
    {
        for(j=0;j<len1;j++)
        {
            ans[i+j]+=a[j]*b[i];
        }
    }
    for(i=0;i<len1+len2;i++)
    {
        ans[i+1]+=ans[i]/10;
        ans[i]=ans[i]%10;
    }
    for(j=len1+len2;j>=0;j--)
    {
        if(ans[j])
            break;
    }
    return j+1;
}

//除法运算，运算结果保存在ans中，函数返回运算结果位数
int Div(int ans[],int len2)
{
    int *temp=(int *)malloc(sizeof(int)*MAXN);
    memset(ans,sizeof(ans)*MAXN);
    int flag=compare(a,len2),nTimes,i,j;
    if(flag==-1)
        return 1;
    else if(flag==0)
    {
        ans[0]=1;
        return 1;
    }
    else
    {
        nTimes=len1-len2,j;
        for(i=nTimes;i>=0;i--)
        {
            //b[]左移i位,低位补零，存入temp中
            memset(temp,sizeof(*temp)*MAXN);
            for(j=len2-1;j>=0;j--)
                temp[j+i]=b[j];
            for(j=i-1;j>=0;j--)
                temp[j]=0;
            while(compare(a,temp,len2+i)>=0)
            {
                len1=sub(a,len2+i);
                ans[i]++;
            }
        }
    }
    for(i=nTimes;i>=0;i--)
    {
        if(ans[i])
            break;
    }
    return i+1;
}

//求数a的平方根，运算结果保存在ans中。函数返回运算结果的位数
int sqrt(int ans[],int len)
{
    int ansLen,flag;
    if(len%2==0)
        ansLen=len/2;
    else
        ansLen=len/2+1;
    int *temp=(int *)malloc(sizeof(int)*MAXN);
    memset(ans,sizeof(ans)*MAXN);
    for(i=ansLen-1;i>=0;i--)
    {
        memset(temp,sizeof(*temp)*MAXN);
        int tLen=1;
        while((flag=compare(temp,tLen,len))<0)
        {
            ans[i]++;
            tLen=mul(temp,ans,ansLen,ansLen);
        }
        if(flag>0)
            ans[i]--;
        else if(flag==0)
            break;
    }
    return ansLen;
}

//比较两个大数的大小,如果a>b,函数返回1.a=b，函数返回0.a<b,函数返回-1.
int compare(int a[],int len2)
{
    int i;
    if(len1<len2)
        return -1;
    else if(len1>len2)
        return 1;
    else 
    {
        for(i=len1-1;i>=0;i--)
        {
            if(a[i]>b[i])
                return 1;
            else if(a[i]<b[i])
                return -1;
        }
    }
    return 0;
}