📄 bigint.cpp
字号:
/****************************************************************/
//大数运算库文件：BigInt.cpp
/****************************************************************/
#include "stdafx.h"
#include "BigInt.h"
CBigInt::CBigInt()
{
m_nSign=1;
m_nLength=1;
for(int i=0;i<BI_MAXLEN;i++)m_ulValue[i]=0;
}
CBigInt::~CBigInt()
{
}
int CBigInt::Cmp(CBigInt& A)
{
if(m_nLength>A.m_nLength)return 1;
if(m_nLength<A.m_nLength)return -1;
for(int i=m_nLength-1;i>=0;i--)
{
if(m_ulValue[i]>A.m_ulValue[i])return 1;
if(m_ulValue[i]<A.m_ulValue[i])return -1;
}
return 0;
}
CBigInt& CBigInt::Mov(CBigInt& A)
{
m_nLength=A.m_nLength;
for(int i=0;i<BI_MAXLEN;i++)m_ulValue[i]=A.m_ulValue[i];
return *this;
}
CBigInt& CBigInt::Mov(unsigned __int64 A)
{
if(A>0xffffffff)
{
m_nLength=2;
m_ulValue[1]=(unsigned long)(A>>32);
m_ulValue[0]=(unsigned long)A;
}
else
{
m_nLength=1;
m_ulValue[0]=(unsigned long)A;
}
for(int i=m_nLength;i<BI_MAXLEN;i++)m_ulValue[i]=0;
return *this;
}
CBigInt CBigInt::Add(CBigInt& A)
{
CBigInt X;
if(X.m_nSign==A.m_nSign)
{
X.Mov(*this);
int carry=0;
unsigned __int64 sum=0;
if(X.m_nLength<A.m_nLength)X.m_nLength=A.m_nLength;
for(int i=0;i<X.m_nLength;i++)
{
sum=A.m_ulValue[i];
sum=sum+X.m_ulValue[i]+carry;
X.m_ulValue[i]=(unsigned long)sum;
if(sum>0xffffffff)carry=1;
else carry=0;
}
if(X.m_nLength<BI_MAXLEN)
{
X.m_ulValue[X.m_nLength]=carry;
X.m_nLength+=carry;
}
return X;
}
else{X.Mov(A);X.m_nSign=1-X.m_nSign;return Sub(X);}
}
CBigInt CBigInt::Add(long A)
{
CBigInt X;
if((m_nSign*A)>=0)
{
X.Mov(*this);
unsigned __int64 sum;
sum=A+X.m_ulValue[0];
X.m_ulValue[0]=(unsigned long)sum;
if(sum>0xffffffff)
{
int i=1;
while(X.m_ulValue[i]==0xffffffff){X.m_ulValue[i]=0;i++;}
X.m_ulValue[i]++;
if(i<BI_MAXLEN)X.m_nLength=i+1;
}
return X;
}
else return Sub(-A);
}
CBigInt CBigInt::Sub(CBigInt& A)
{
CBigInt X;
if(m_nSign==A.m_nSign)
{
X.Mov(*this);
int cmp=X.Cmp(A);
if(cmp==0){X.Mov(0);return X;}
int len,carry=0;
unsigned __int64 num;
unsigned long *s,*d;
if(cmp>0){s=X.m_ulValue;d=A.m_ulValue;len=X.m_nLength;}
if(cmp<0){s=A.m_ulValue;d=X.m_ulValue;len=A.m_nLength;X.m_nSign=1-X.m_nSign;}
for(int i=0;i<len;i++)
{
if((s[i]-carry)>=d[i])
{
X.m_ulValue[i]=s[i]-carry-d[i];
carry=0;
}
else
{
num=0x100000000+s[i];
X.m_ulValue[i]=(unsigned long)(num-carry-d[i]);
carry=1;
}
}
while(X.m_ulValue[len-1]==0)len--;
X.m_nLength=len;
return X;
}
else{X.Mov(A);X.m_nSign=1-X.m_nSign;return Add(X);}
}
CBigInt CBigInt::Sub(long A)
{
CBigInt X;
if((m_nSign*A)>=0)
{
X.Mov(*this);
if(X.m_ulValue[0]>=(unsigned long)A){X.m_ulValue[0]-=A;return X;}
if(X.m_nLength==1){X.m_ulValue[0]=A-X.m_ulValue[0];X.m_nSign=1-X.m_nSign;return X;}
unsigned __int64 num=0x100000000+X.m_ulValue[0];
X.m_ulValue[0]=(unsigned long)(num-A);
int i=1;
while(X.m_ulValue[i]==0){X.m_ulValue[i]=0xffffffff;i++;}
if(X.m_ulValue[i]==1)X.m_nLength--;
X.m_ulValue[i]--;
return X;
}
else return Add(-A);
}
CBigInt CBigInt::Mul(CBigInt& A)
{
CBigInt X,Y;
unsigned __int64 mul;
unsigned long carry;
for(int i=0;i<A.m_nLength;i++)
{
Y.m_nLength=m_nLength;
carry=0;
for(int j=0;j<m_nLength;j++)
{
mul=m_ulValue[j];
mul=mul*A.m_ulValue[i]+carry;
Y.m_ulValue[j]=(unsigned long)mul;
carry=(unsigned long)(mul>>32);
}
if(carry&&(Y.m_nLength<BI_MAXLEN)){Y.m_nLength++;Y.m_ulValue[Y.m_nLength-1]=carry;}
if(Y.m_nLength<BI_MAXLEN-i)
{
Y.m_nLength+=i;
for(int k=Y.m_nLength-1;k>=i;k--)Y.m_ulValue[k]=Y.m_ulValue[k-i];
for(k=0;k<i;k++)Y.m_ulValue[k]=0;
}
X.Mov(X.Add(Y));
}
if(m_nSign+A.m_nSign==1)X.m_nSign=0;
else X.m_nSign=1;
return X;
}
CBigInt CBigInt::Mul(long A)
{
CBigInt X;
unsigned __int64 mul;
unsigned long carry=0;
X.Mov(*this);
for(int i=0;i<m_nLength;i++)
{
mul=m_ulValue[i];
mul=mul*A+carry;
X.m_ulValue[i]=(unsigned long)mul;
carry=(unsigned long)((mul-X.m_ulValue[i])>>32);
}
if(carry&&(X.m_nLength<BI_MAXLEN)){X.m_nLength++;X.m_ulValue[X.m_nLength-1]=carry;}
if(A<0)X.m_nSign=1-X.m_nSign;
return X;
}
CBigInt CBigInt::Div(CBigInt& A)
{
CBigInt X,Y,Z;
int len;
unsigned __int64 num,div;
unsigned long carry=0;
Y.Mov(*this);
while(Y.Cmp(A)>0)
{
if(Y.m_ulValue[Y.m_nLength-1]>A.m_ulValue[A.m_nLength-1])
{
len=Y.m_nLength-A.m_nLength;
div=Y.m_ulValue[Y.m_nLength-1]/(A.m_ulValue[A.m_nLength-1]+1);
}
else if(Y.m_nLength>A.m_nLength)
{
len=Y.m_nLength-A.m_nLength-1;
num=Y.m_ulValue[Y.m_nLength-1];
num=(num<<32)+Y.m_ulValue[Y.m_nLength-2];
if(A.m_ulValue[A.m_nLength-1]==0xffffffff)div=(num>>32);
else div=num/(A.m_ulValue[A.m_nLength-1]+1);
}
else
{
X.Mov(X.Add(1));
break;
}
Z.Mov(div);
Z.m_nLength+=len;
for(int i=Z.m_nLength-1;i>=len;i--)Z.m_ulValue[i]=Z.m_ulValue[i-len];
for(i=0;i<len;i++)Z.m_ulValue[i]=0;
X.Mov(X.Add(Z));
Z.Mov(Z.Mul(A));
Y.Mov(Y.Sub(Z));
}
if(Y.Cmp(A)==0)X.Mov(X.Add(1));
if(m_nSign+A.m_nSign==1)X.m_nSign=0;
else X.m_nSign=1;
return X;
}
CBigInt CBigInt::Div(long A)
{
CBigInt X;
X.Mov(*this);
if(X.m_nLength==1){X.m_ulValue[0]=X.m_ulValue[0]/A;return X;}
unsigned __int64 div,mul;
unsigned long carry=0;
for(int i=X.m_nLength-1;i>=0;i--)
{
div=carry;
div=(div<<32)+X.m_ulValue[i];
X.m_ulValue[i]=(unsigned long)(div/A);
mul=(div/A)*A;
carry=(unsigned long)(div-mul);
}
if(X.m_ulValue[X.m_nLength-1]==0)X.m_nLength--;
if(A<0)X.m_nSign=1-X.m_nSign;
return X;
}
CBigInt CBigInt::Mod(CBigInt& A)
{
CBigInt X,Y;
int len;
unsigned __int64 num,div;
unsigned long carry=0;
X.Mov(*this);
while(X.Cmp(A)>0)
{
if(X.m_ulValue[X.m_nLength-1]>A.m_ulValue[A.m_nLength-1])
{
len=X.m_nLength-A.m_nLength;
div=X.m_ulValue[X.m_nLength-1]/(A.m_ulValue[A.m_nLength-1]+1);
}
else if(X.m_nLength>A.m_nLength)
{
len=X.m_nLength-A.m_nLength-1;
num=X.m_ulValue[X.m_nLength-1];
num=(num<<32)+X.m_ulValue[X.m_nLength-2];
if(A.m_ulValue[A.m_nLength-1]==0xffffffff)div=(num>>32);
else div=num/(A.m_ulValue[A.m_nLength-1]+1);
}
else
{
X.Mov(X.Sub(A));
break;
}
Y.Mov(div);
Y.Mov(Y.Mul(A));
Y.m_nLength+=len;
for(int i=Y.m_nLength-1;i>=len;i--)Y.m_ulValue[i]=Y.m_ulValue[i-len];
for(i=0;i<len;i++)Y.m_ulValue[i]=0;
X.Mov(X.Sub(Y));
}
if(X.Cmp(A)==0)X.Mov(0);
return X;
}
long CBigInt::Mod(long A)
{
if(m_nLength==1)return(m_ulValue[0]%A);
unsigned __int64 div;
unsigned long carry=0;
for(int i=m_nLength-1;i>=0;i--)
{
div=carry*0x100000000+m_ulValue[i];
carry=(unsigned long)(div-((div/A)*A));
}
return carry;
}
int CBigInt::InPutFromStr(CString& str, const unsigned int system=DEC)
{
int len=str.GetLength();
Mov(0);
for(int i=0;i<len;i++)
{
Mov(Mul(system));
int k=str[i]-48;
if (str[i]==65) //读的int 数为对应的ASCⅡ的什么字符
{
k=65-55;
}
if (str[i]==66)
{
k=66-55;
}
if (str[i]==67)
{
k=67-55;
}
if (str[i]==68)
{
k=68-55;
}
if (str[i]==69)
{
k=69-55;
}
if (str[i]==70)
{
k=70-55;
}
if (str[i]==71)
{
k=71-55;
}
if (str[i]==72)
{
k=72-55;
}
if (str[i]==73)
{
k=73-55;
}
if (str[i]==74)
{
k=74-55;
}
if (str[i]==75)
{
k=75-55;
}
if (str[i]==76)
{
k=76-55;
}
if (str[i]==77)
{
k=77-55;
}
if (str[i]==78)
{
k=78-55;
}
if (str[i]==79)
{
k=79-55;
}
if (str[i]==80)
{
k=80-55;
}
if (str[i]==81)
{
k=81-55;
}
if (str[i]==82)
{
k=82-55;
}
if (str[i]==83)
{
k=83-55;
}
if (str[i]==84)
{
k=84-55;
}
if (str[i]==85)
{
k=85-55;
}
if (str[i]==86)
{
k=86-55;
}
if (str[i]==87)
{
k=87-55;
}
if (str[i]==88)
{
k=88-55;
}
if (str[i]==89)
{
k=89-55;
}
if (str[i]==90)
{
k=90-55;
}
if (str[i]==97)
{
k=97-61;
}
if (str[i]==98)
{
k=98-61;
}
if (str[i]==99)
{
k=99-61;
}
if (str[i]==100)
{
k=100-61;
}
if (str[i]==101)
{
k=101-61;
}
if (str[i]==102)
{
k=102-61;
}
if (str[i]==103)
{
k=103-61;
}
if (str[i]==104)
{
k=104-61;
}
if (str[i]==105)
{
k=105-61;
}
if (str[i]==106)
{
k=106-61;
}
if (str[i]==107)
{
k=107-61;
}
if (str[i]==108)
{
k=108-61;
}
if (str[i]==109)
{
k=109-61;
}
if (str[i]==110)
{
k=110-61;
}
if (str[i]==111)
{
k=111-61;
}
if (str[i]==112)
{
k=112-61;
}
if (str[i]==113)
{
k=113-61;
}
if (str[i]==114)
{
k=114-61;
}
if (str[i]==115)
{
k=115-61;
}
if (str[i]==116)
{
k=116-61;
}
if (str[i]==117)
{
k=117-61;
}
if (str[i]==118)
{
k=118-61;
}
if (str[i]==119)
{
k=119-61;
}
if (str[i]==120)
{
k=120-61;
}
if (str[i]==121)
{
k=121-61;
}
if (str[i]==122)
{
k=122-61;
}
Mov(Add(k));
}
return 0;
}
int CBigInt::OutPutToStr(CString& str, const unsigned int system=DEC)
{
str="";
char ch;
CBigInt X;
X.Mov(*this);
while(X.m_ulValue[X.m_nLength-1]>0)
{
ch = X.Mod(system) + 48;
if (X.Mod(system)==10) //除的余数指定相应的字符
{
ch=65;
}
if (X.Mod(system)==11)
{
ch=66;
}
if (X.Mod(system)==12)
{
ch=67;
}
if (X.Mod(system)==13)
{
ch=68;
}
if (X.Mod(system)==14)
{
ch=69;
}
if (X.Mod(system)==15)
{
ch=70;
}
if (X.Mod(system)==16)
{
ch=71;
}
if (X.Mod(system)==17)
{
ch=72;
}
if (X.Mod(system)==18)
{
ch=73;
}
if (X.Mod(system)==19)
{
ch=74;
}
if (X.Mod(system)==20)
{
ch=75;
}
if (X.Mod(system)==21)
{
ch=76;
}
if (X.Mod(system)==22)
{
ch=77;
}
if (X.Mod(system)==23)
{
ch=78;
}
if (X.Mod(system)==24)
{
ch=79;
}
if (X.Mod(system)==25)
{
ch=80;
}
if (X.Mod(system)==26)
{
ch=81;
}
if (X.Mod(system)==27)
{
ch=82;
}
if (X.Mod(system)==28)
{
ch=83;
}
if (X.Mod(system)==29)
{
ch=84;
}
if (X.Mod(system)==30)
{
ch=85;
}
if (X.Mod(system)==31)
{
ch=86;
}
if (X.Mod(system)==32)
{
ch=87;
}
if (X.Mod(system)==33)
{
ch=88;
}
if (X.Mod(system)==34)
{
ch=89;
}
if (X.Mod(system)==35)
{
ch=90;
}
if (X.Mod(system)==36)
{
ch=97;
}
if (X.Mod(system)==37)
{
ch=98;
}
if (X.Mod(system)==38)
{
ch=99;
}
if (X.Mod(system)==39)
{
ch=100;
}
if (X.Mod(system)==40)
{
ch=101;
}
if (X.Mod(system)==41)
{
ch=102;
}
if (X.Mod(system)==42)
{
ch=103;
}
if (X.Mod(system)==43)
{
ch=104;
}
if (X.Mod(system)==44)
{
ch=105;
}
if (X.Mod(system)==45)
{
ch=106;
}
if (X.Mod(system)==46)
{
ch=107;
}
if (X.Mod(system)==47)
{
ch=108;
}
if (X.Mod(system)==48)
{
ch=109;
}
if (X.Mod(system)==49)
{
ch=110;
}
if (X.Mod(system)==50)
{
ch=111;
}
if (X.Mod(system)==51)
{
ch=112;
}
if (X.Mod(system)==52)
{
ch=113;
}
if (X.Mod(system)==53)
{
ch=114;
}
if (X.Mod(system)==54)
{
ch=115;
}
if (X.Mod(system)==55)
{
ch=116;
}
if (X.Mod(system)==56)
{
ch=117;
}
if (X.Mod(system)==57)
{
ch=118;
}
if (X.Mod(system)==58)
{
ch=119;
}
if (X.Mod(system)==59)
{
ch=120;
}
if (X.Mod(system)==60)
{
ch=121;
}
if (X.Mod(system)==61)
{
ch=122;
}
str.Insert(0,ch);
X.Mov(X.Div(system));
}
return 0;
}
CBigInt CBigInt::Euc(CBigInt& A)
{
CBigInt X,Y;
X.Mov(*this);
Y.Mov(A);
if((X.m_nLength==1)&&(X.m_ulValue[0]==1))return X;
if((Y.m_nLength==1)&&(Y.m_ulValue[0]==1)){X.Mov(X.Sub(1));return X;}
if(X.Cmp(Y)==1)X.Mov(X.Mod(Y));
else Y.Mov(Y.Mod(X));
X.Mov(X.Euc(Y));
Y.Mov(*this);
if(Y.Cmp(A)==1)
{
X.Mov(X.Mul(Y));
X.Mov(X.Sub(1));
X.Mov(X.Div(A));
}
else
{
X.Mov(X.Mul(A));
X.Mov(X.Add(1));
X.Mov(X.Div(Y));
}
return X;
}
CBigInt CBigInt::Mon(CBigInt& A, CBigInt& B)
{
CBigInt X,Y,Z;
X.Mov(1);
Y.Mov(*this);
Z.Mov(A);
while((Z.m_nLength!=1)||Z.m_ulValue[0])
{
if(Z.m_ulValue[0]&1)
{
Z.Mov(Z.Sub(1));
X.Mov(X.Mul(Y));
X.Mov(X.Mod(B));
}
else
{
Z.Mov(Z.Div(2));
Y.Mov(Y.Mul(Y));
Y.Mov(Y.Mod(B));
}
}
return X;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -