积累系统性知识
积聚技术精华
  首页    个人中心    撰写积文    建立课题    订立目标    整理积文    管理课题    管理目标    技能Get    代码积累 
一个大整数运算类源码(BigInt)
error997 (error997)    2014-11-20 20:31:14      目标    课题
      本文提供大整数的运算,包含加减乘,次方,阶乘的运算。
   基本算法:
   大整数运算的基本算法比较简单,很多书上都有介绍,本文有一点要说明,本文采用的是万进制来运算。为什么采用万进制?因为万进制一个int字长可容纳4数字,这样就减少存储空间,同时大大提高了运算速度。照此说法还不如采用亿进制,原因在于乘法运算的过程中需要用到两个数相乘,而两个小于一万的数相乘小于一亿,也小于21亿,符合一个int字长,而采用亿进制会造成越界,处理起来麻烦,费时。
   次方运算采用了优化算法,实际上采用的是将指数化成二进制,然后拆开运算后相加得到结果。
   阶乘运算基本未使用优化策略,采用传统的递推算法。
   代码:
切换到: 纯代码  
   
   //
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
class BigInt
{
private:
    int sign;
    int nb;
    int *pData;
    void Init(int nnb);
    void ShowData(int m);
public:
    BigInt();
    BigInt(BigInt &bnum);
    BigInt(int num);

    ~BigInt();
切换到: 纯代码  
   
    void Show();//控制台显示
    void trim();//规范化
    BigInt &operator=(int num);
    BigInt &operator=(BigInt &bnum);
    int operator==(BigInt &bnum);
    int operator!=(BigInt &bnum);
    int operator>(BigInt &bnum);
    int operator<(BigInt &bnum);
    int operator>=(BigInt &bnum);
    int operator<=(BigInt &bnum);
    BigInt &operator+=(BigInt &bnum);
    BigInt &operator-=(BigInt &bnum);
    BigInt &operator*=(BigInt &bnum);
    int GetBit();//获取位数
    int GetSign();//获取符号
    void Cont();//相反数
    int ReadFromStr(char *str);//数字字符串转换为BigInt
    int WriteToStr(char *str);//转变为字符串
    friend BigInt operator-(BigInt &bnum);
};
BigInt::BigInt()
{
    sign=0;
    nb=1;
    pData=new int[nb];
    pData[0]=0;
}
BigInt::BigInt(BigInt &bnum)
{
    sign=bnum.sign;
    nb=bnum.nb;
    pData=new int[nb];
    for(int i=0;i<nb;i++)
    pData[i]=bnum.pData[i];
}
BigInt::BigInt(int num)
{
    *this=num;
}
BigInt::~BigInt()
{
    delete []pData;
}
void BigInt::Init(int nnb)
{
    delete []pData;
    nb=nnb;
    pData=new int[nb];
    for(int i=0;i<nb;i++)
    pData[i]=0;
}
void BigInt::ShowData(int m)
{
    printf("%c%c%c%c",pData[m]/1000+'0',(pData[m]%1000)/100+'0',(pData[m]%100)/10+'0',pData[m]%10+'0');
}
void BigInt::Show()//控制台显示
{
    int i;
    if(sign==-1)
    printf("-");
    for(i=nb-1;i>=0;i--)
    {
        ShowData(i);
    }
}
void BigInt::trim()//规范化
{
    int i,j;
    for(i=nb-1;i>0;i--)
    {
        if(pData[i]!=0)
        break;
    }
    if(i==nb-1)
    return;
    BigInt bnum=*this;
    Init(i+1);
    for(j=0;j<=i;j++)
    {
        pData[j]=bnum.pData[j];
    }
}
BigInt &BigInt::operator=(int num)
{
    int n=abs(num);
    if(num==0)
    sign=0;
    else if(num>0)
    sign=1;
    else
    sign=-1;
    if(n<10000)
    {
        Init(1);
        pData[0]=n;
    }
    else if(n<100000000)
    {
        Init(2);
        pData[1]=n/10000;
        pData[0]=n%10000;
    }
    else
    {
        Init(3);
        pData[2]=n/100000000;
        pData[1]=(n%100000000)/10000;
        pData[0]=n%10000;
    }
    return *this;
}
   BigInt &BigInt::operator=(BigInt &bnum)
{
    int i;
    if(this==&bnum)
    return *this;
    sign=bnum.sign;
    nb=bnum.nb;
    Init(nb);
    for(i=0;i<nb;i++)
    {
        pData[i]=bnum.pData[i];
    }
    return *this;
}
int BigInt::operator==(BigInt &bnum)
{
    if(this==&bnum)
    return 1;
    if(sign!=bnum.sign)
    return 0;
    trim();
    bnum.trim();
    if(nb!=bnum.nb)
    return 0;
    for(int i=0;i<nb;i++)
    {
        if(pData[i]!=bnum.pData[i])
        return 0;
    }
    return 1;
}
int BigInt::operator!=(BigInt &bnum)
{
    return !(*this==bnum);
}
int BigInt::operator>(BigInt &bnum)
{
    if(this==&bnum)
    return 0;
    if(sign>bnum.sign)
    return 1;
    if(sign<bnum.sign)
    return 0;
    if(sign==0)
    return 0;
    trim();
    bnum.trim();
    if(nb>bnum.nb)
    {
        if(sign>0)
        return 1;
        else
        return 0;
    }
    if(nb<bnum.nb)
    {
        if(sign>0)
        return 0;
        else
        return 1;
    }
    for(int i=nb-1;i>=0;i--)
    {
        if(pData[i]>bnum.pData[i])
        {
            if(sign>0)
            return 1;
            else
            return 0;
        }
        else if(pData[i]<bnum.pData[i])
        {
            if(sign>0)
            return 0;
            else
            return 1;
        }
    }
    return 0;
}
int BigInt::operator<(BigInt &bnum)
{
    return bnum>(*this);
}
int BigInt::operator>=(BigInt &bnum)
{
    return *this==bnum||*this>bnum;
}
int BigInt::operator<=(BigInt &bnum)
{
    return *this==bnum||*this<bnum;
}
///////////////////////////////////////////////////////////////
BigInt operator+(BigInt &bnum1,BigInt &bnum2)
{
    BigInt bnum3;
    bnum3=bnum1;
    bnum3+=bnum2;
    return BigInt(bnum3);
}
BigInt operator-(BigInt &bnum1,BigInt &bnum2)
{
    BigInt bnum3;
    bnum3=bnum1;
    bnum3-=bnum2;
    return BigInt(bnum3);
}
BigInt operator*(BigInt &bnum1,BigInt &bnum2)
{
    BigInt bnum3;
    bnum3=bnum1;
    bnum3*=bnum2;
    return BigInt(bnum3);
}
   ////////////////////////////////////////////////////////////////
BigInt &BigInt::operator+=(BigInt &bnum)
{
    if(this==&bnum)
    {
        BigInt bnum1=bnum;
        *this=bnum1+bnum1;
        return *this;
    }
    if(sign==0)
    {
        return bnum;
    }
    if(bnum.sign==0)
    {
        return *this;
    }
    int i,m;
    BigInt bnum0,*p1,*p2;
    if(sign<0&&bnum.sign<0)
    {
        this->sign=1;
        bnum0=bnum;
        bnum0.sign=1;
        *this+=bnum0;
        this->sign=-1;
        return *this;
    }
    if(sign>0&&bnum.sign<0)
    {
        bnum0=bnum;
        bnum0.sign=1;
        *this-=bnum0;
        return *this;
    }
    if(sign<0&&bnum.sign>0)
    {
        this->sign=1;
        bnum0=bnum;
        bnum0.sign=1;
        *this-=bnum0;
        this->sign=-1;
        return *this;
    }
    bnum0=*this;
    if(bnum.nb>bnum0.nb)
    {
        m=bnum.nb;
        p1=&bnum;
        p2=&bnum0;
    }
    else
    {
        m=bnum0.nb;
        p1=&bnum0;
        p2=&bnum;
    }
    if(p1->nb==p2->nb&&(p1->pData[m-1]+p2->pData[m-1])>=9999)
    Init(m+1);
    else if(p1->pData[m-1]>=9999)
    Init(m+1);
    else
    Init(m);
    sign=1;
    for(i=0;i<p2->nb;i++)
    {
        pData[i]=p1->pData[i]+p2->pData[i];
    }
    for(;i<p1->nb;i++)
    pData[i]=p1->pData[i];
    for(i=0;i<nb;i++)
    {
        if(pData[i]>=10000)
        {
            //pData[i+1]=pData[i+1]+pData[i]/10000;
            pData[i+1]+=1;
            pData[i]=pData[i]%10000;
        }
    }
    return *this;
}
BigInt &BigInt::operator-=(BigInt &bnum)
{
    if(this==&bnum||*this==bnum)
    {
        *this=0;
        return *this;
    }
    int i,m;
    BigInt bnum0,*p1,*p2;
    if(sign<0&&bnum.sign<0)
    {
        this->sign=1;
        bnum0=bnum;
        bnum0.sign=1;
        *this=bnum0-*this;
        return *this;
    }
    if(sign>0&&bnum.sign<0)
    {
        bnum0=bnum;
        bnum0.sign=1;
        *this+=bnum0;
        return *this;
    }
    if(sign<0&&bnum.sign>0)
    {
        this->sign=1;
        *this+=bnum;
        this->sign=-1;
        return *this;
    }
    bnum0=*this;
    if(bnum0>bnum)
    {
        m=bnum0.nb;
        p1=&bnum0;
        p2=&bnum;
        Init(m);
        sign=1;
    }
    else
    {
   m=bnum.nb;
        p1=&bnum;
        p2=&bnum0;
        Init(m);
        sign=-1;
    }
   for(i=0;i<p2->nb;i++)
    {
        pData[i]=p1->pData[i]-p2->pData[i];
    }
    for(;i<p1->nb;i++)
    pData[i]=p1->pData[i];
    for(i=0;i<nb;i++)
    {
        if(pData[i]<0)
        {
            pData[i]+=10000;
            pData[i+1]-=1;
        }
    }
    return *this;
}
BigInt &BigInt::operator*=(BigInt &bnum)
{
    if(this==&bnum)
    {
        BigInt bnum1=bnum;
        *this=bnum1*bnum1;
        return *this;
    }
    if(sign==0||bnum.sign==0)
    {
        *this=0;
        return *this;
    }
    int i,j,d=0,*temp;
    BigInt bnum0;
    bnum0=*this;
    temp=new int[bnum0.nb+1];
    Init(bnum0.nb+bnum.nb);
    sign=bnum0.sign*bnum.sign;
    for(i=0;i<bnum.nb;i++)
    {
        temp[bnum0.nb]=0;
        for(j=0;j<bnum0.nb;j++)
        {
            temp[j]=bnum0.pData[j]*bnum.pData[i];
        }
        for(j=0;j<bnum0.nb;j++)
        {
            if(temp[j]>=10000)
            {
                temp[j+1]=temp[j+1]+temp[j]/10000;
                temp[j]=temp[j]%10000;
            }
        }
        for(j=0;j<=bnum0.nb;j++)
        {
            pData[j+d]+=temp[j];
        }
        d++;
    }
    for(j=0;j<nb;j++)
    {
        if(pData[j]>=10000)
        {
            pData[j+1]=pData[j+1]+pData[j]/10000;
            pData[j]=pData[j]%10000;
        }
    }
    delete []temp;
    return *this;
}
int BigInt::GetBit()//获取位数
{
    int b;
    trim();
    b=(nb-1)*4;
    if(pData[nb-1]>=1000)
    b+=4;
    else if(pData[nb-1]>=100)
    b+=3;
    else if(pData[nb-1]>=10)
    b+=2;
    else
    b+=1;
    return b;
}
int BigInt::GetSign()//获取符号
{
    return sign;
}
int BigInt::ReadFromStr(char *str)//数字字符串转换为BigInt
{
    int i,j,len=strlen(str),sg=0,t;
    if(str[0]=='-')
    {
        sg=-1;
    }
    else if(str[0]=='+')
    {
        sg=1;
    }
    for(i=abs(sg);i<len;i++)
    {
        if(str[i]<'0'||str[i]>'9')
        return 0;
    }
    j=abs(sg);
    while(j<len)
    {
        if(str[j]!='0')
        break;
        j++;
    }
    if(len==j)
    {
        Init(1);
        return 1;
    }
    if((len-j)%4==0)
    {
        Init((len-j)/4);
        for(i=0;i<nb;i++)
        {
            t=4*i+1;
            pData[i]=(str[len-t]-'0')+(str[len-t-1]-'0')*10+(str[len-t-2]-'0')*100+(str[len-t-3]-'0')*1000;
        }
    }
    else
    {
        Init((len-j)/4+1);
        for(i=0;i<nb-1;i++)
        {
            t=4*i+1;
            pData[i]=(str[len-t]-'0')+(str[len-t-1]-'0')*10+(str[len-t-2]-'0')*100+(str[len-t-3]-'0')*1000;
        }
        i=abs(sg);
        if((len-j)%4==1)
        pData[nb-1]=str[i+0]-'0';
        else if((len-j)%4==2)
        pData[nb-1]=(str[i+0]-'0')*10+(str[i+1]-'0');
        else
        pData[nb-1]=(str[i+0]-'0')*100+(str[i+1]-'0')*10+str[i+2]-'0';
    }
    if(sg<0)
    sign=-1;
    else
    sign=1;
    return nb;
}
int BigInt::WriteToStr(char *str)//转变为字符串
{
    int i,len,k;
    trim();
    k=pData[nb-1];
    if(sign<0)
    k*=-1;
    itoa(k,str,10);
    len=strlen(str);
    for(i=nb-2;i>=0;i--)
    {
        k=nb-2-i;
        str[len+4*i]=pData[k]/1000+'0';
        str[len+4*i+1]=(pData[k]%1000)/100+'0';
        str[len+4*i+2]=(pData[k]%100)/10+'0';
        str[len+4*i+3]=pData[k]%10+'0';
    }
    len=GetBit();
    if(sign<0)
    len++;
    str[len]='/0';
    return len;
}
void BigInt::Cont()//相反数
{
    sign*=-1;
}
BigInt operator-(BigInt &bnum)
{
    BigInt bnum0;
    bnum0=bnum;
    bnum0.sign*=-1;
    return BigInt(bnum0);
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
BigInt Bfac(int m)//阶乘
{
    BigInt n1,n2;
    n2=1;
    for(int i=2;i<=m;i++)
    {
        n1=i;
        n2*=n1;
        n2.trim();
    }
    return BigInt(n2);
}
   ////////////////////////////////////////////////////////////////
int Pow(int x,int n)//x的n次方
{
    if(n==0)
    return 1;
    if(n<0)
    return 0;
    int k=n,t,s;
    t=x;
    s=1;
    while(1)
    {
        if(k%2==1)
        {
            s*=t;
        }
        k=k>>1;
        if(k==0)
        break;
        t=t*t;
    }
    return s;
}
BigInt BPow(BigInt &x,int n)//x的n次方
{
    if(n==0)
    return 1;
    if(n<0)
    return 0;
    int k=n;
    BigInt t,s;
    t=x;
    s=1;
    while(1)
    {
        if(k%2==1)
        {
            s*=t;
        }
        k=k>>1;
        if(k==0)
        break;
        t=t*t;
    }
    return BigInt(s);
}
BigInt BPow(int x,int n)//x的n次方
{
    BigInt c;
    if(n==1)
    {
        c=x;
        return BigInt(c);
    }
    if(n==2)
    {
        c=x*x;
        return BigInt(c);
    }
    if(n==3)
    {
        c=x*x*x;
        return BigInt(c);
    }
    double n1=log(2147483647),n2=log(x);
    int m=(int)(log(2147483647)/log(x));
    if(m>=n)
    {
        c=(int)pow(x,n);
        return BigInt(c);
    }
    int div=n/m,mod=n%m;
    BigInt s;
    c=(int)pow(x,m);
    s=BPow(c,div);
    c=(int)pow(x,mod);
    s*=c;
    return BigInt(s);
}
////////////////////////////////////////////////////////////////
int main()
{
    int i,j,s;
    clock_t t_begin,t_end;
    BigInt a,b,c,d,e;
    a=954654411;
    b=1921412412;
    c=1921412412;
    c.ReadFromStr("4353452543532542542542123456789");c.Show();printf("/n");
    char str[200];
    b.WriteToStr(str);
    printf("%s/n",str);
    d=c-a;
    //d=d+c;
    d.Show();
    printf("/n%d/n",d.GetBit());
    //printf("/n");
    c=a+b+b;
   t_begin=clock();
    for(i=0;i<10000;i++)
    c+=b;
    t_end=clock();
    printf("代码所用的时间:%.3f秒/n",(double)(t_end-t_begin)/CLOCKS_PER_SEC);
   
    c.Show();
    printf("/n");
    t_begin=clock();
    e=Bfac(1000);
    t_end=clock();
    printf("%d/n",e.GetBit());
    printf("代码所用的时间:%.3f秒/n",(double)(t_end-t_begin)/CLOCKS_PER_SEC);
    e.trim();
    e.Show();
    printf("/n");
    return 0;
}
   

   本文除法运算未提供,原因在于未找到高效的算法,现在基本思路是,先将大整数近似为double型或者long double,进行除法后,被除数减去乘数与近似近似商(整数)的积,得到一个新的大整数,用此大整数按照前面的步骤进行循环运算,直到不断得到新的大整数小于除数(此时即为余数),商就为各此近似商之和。

转自 http://blog.csdn.net/y___y/article/details/1415183
(+0)技能Get

建议楼主:搜索关键字 |参考其他资源 |回复 |追问
  error997(error997):   个人中心    课题    目标    代码积累