📄 bigint.cpp
字号:
/****************************************************************/
//大数运算库源文件：BigInt.cpp
//作者：afanty@vip.sina.com
//版本：1.0 (2003.4.26)
//说明：适用于MFC
/****************************************************************/
#include "stdafx.h"
#include "BigInt.h"
//初始化大数为0
CBigInt::CBigInt()
{
m_nSign=1;
m_nLength=1;
for(int i=0;i<BI_MAXLEN;i++) m_ulValue[i]=0;
}
//采用缺省的解构函数
CBigInt::~CBigInt()
{
}
//大数比较，如果大数A位数比大数B多，当然A>B
//如果位数相同，则从高位开始比较，直到分出大小
int CBigInt::Compare(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::SetValue(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::SetValue(unsigned __int64 A)
{ ZeroMemory(m_ulValue,BI_MAXLEN*sizeof(long));
m_nLength=1;
m_ulValue[0]=(unsigned long)A;
if(A>0xffffffff)
{ m_nLength=2;
m_ulValue[1]=(unsigned long)(A>>32);
}
return *this;
}
/*
CBigInt& CBigInt::operator = (const unsigned __int64 A)
{
return SetValue(A);
}*/
//大数相加
//调用形式：N.Add(A)，返回值：N+A
//若两大数符号相同，其值相加，否则改变参数符号再调用大数相减函数
/******************************************************************/
/*
例如：
A B C
+ D E
--------------
= S F G H
其中，若C+E<=0xffffffff，则H=C+E，carry(进位标志)=0
若C+E>0xffffffff，则H=C+E-0x100000000，carry=1
若B+D+carry<=0xfffffff，则G=B+D，carry=0
若B+D+carry>0xfffffff，则G=B+D+carry-0x10000000，carry=1
若carry=0，则F=A，S=0
若carry=1，A<0xfffffff，则F=A+1，S=0
若carry=1，A=0xfffffff，则F=0，S=1
/*****************************************************************/
CBigInt CBigInt::Add(CBigInt& A)
{
CBigInt X;
if(X.m_nSign==A.m_nSign)
{
X.SetValue(*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.SetValue(A);
X.m_nSign=1-X.m_nSign;
return Sub(X);
}
}
CBigInt CBigInt::Add(long A)
{
CBigInt X;
if((m_nSign*A)>=0)
{
X.SetValue(*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);
}
//大数相减
//调用形式：N.Sub(A)，返回值：N-A
//若两大数符号相同，其值相减，否则改变参数符号再调用大数相加函数
/******************************************************************/
/*
例如：
A B C
- D E
--------------
= F G H
其中，若C>=E，则H=C-E，carry(借位标志)=0
若C<E，则H=C-E+0x100000000，carry=1
若B-carry>=D，则G=B-carry-D，carry=0
若B-carry<D，则G=B-carry-D+0x10000000，carry=1
若carry=0，则F=A
若carry=1，A>1，则F=A-1
若carry=1，A=1，则F=0
/*****************************************************************/
CBigInt CBigInt::Sub(CBigInt& A)
{
CBigInt X;
if(m_nSign==A.m_nSign)
{
X.SetValue(*this);
int cmp=X.Compare(A);
if(cmp==0){X.SetValue(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.SetValue(A);
X.m_nSign=1-X.m_nSign;
return Add(X);
}
}
CBigInt CBigInt::Sub(long A)
{
CBigInt X;
if((m_nSign*A)>=0)
{
X.SetValue(*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);
}
//大数相乘
//调用形式：N.Mul(A)，返回值：N*A
/******************************************************************/
/*
例如：
A B C
* D E
----------------
= S F G H
+ T I J K
----------------
= U V L M N
其中，SFGH=ABC*E，TIJK=ABC*D
而对于：
A B C
* E
-------------
= S F G H
其中，若C*E<=0xffffffff，则H=C*E，carry(进位标志)=0
若C*E>0xffffffff，则H=(C*E)&0xffffffff
carry=(C*E)/0xffffffff
若B*E+carry<=0xffffffff，则G=B*E+carry，carry=0
若B*E+carry>0xffffffff，则G=(B*E+carry)&0xffffffff
carry=(B*E+carry)/0xffffffff
若A*E+carry<=0xffffffff，则F=A*E+carry，carry=0
若A*E+carry>0xffffffff，则F=(A*E+carry)&0xffffffff
carry=(A*E+carry)/0xffffffff
S=carry
/*****************************************************************/
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.SetValue(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.SetValue(*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;
}
//大数相除
//调用形式：N.Div(A)，返回值：N/A
//除法的关键在于“试商”，然后就变成了乘法和减法
//这里将被除数与除数的试商转化成了被除数最高位与除数最高位的试商
CBigInt CBigInt::Div(CBigInt& A)
{ CBigInt X,Y,Z;
int len;
unsigned __int64 num,div;
unsigned long carry=0;
Y.SetValue(*this);
while(Y.Compare(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.SetValue(X.Add(1));
break;
}
Z.SetValue(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.SetValue(X.Add(Z));
Z.SetValue(Z.Mul(A));
Y.SetValue(Y.Sub(Z));
}
if(Y.Compare(A)==0)X.SetValue(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.SetValue(*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;
}
//大数求模
//调用形式：N.Mod(A)，返回值：N%A
//求模与求商原理相同
CBigInt CBigInt::Mod(CBigInt& A)
{ CBigInt X,Y;
int len;
unsigned __int64 num,div;
unsigned long carry=0;
X.SetValue(*this);
while(X.Compare(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.SetValue(X.Sub(A));
break;
}
Y.SetValue(div);
Y.SetValue(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.SetValue(X.Sub(Y));
}
if(X.Compare(A)==0)
X.SetValue(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 /*=AUTO */)
{ int autoSystem,len=str.GetLength();
register int i=0,k=0;
autoSystem=system;
if(autoSystem==AUTO)
{ autoSystem=DEC;
CString x(str.Left(2));
x.MakeLower();
if(x =="0x")
{
autoSystem=HEX;
i=2;
}
}
SetValue(0);
for(;i<len;i++)
{ if(i==0 && str[i]=='-')
m_nSign=0;
else
{
SetValue(Mul(autoSystem));
k=str[i]-48;
SetValue(Add(k));
}
}
return 0;
}
//暂时只给出了十进制字符串的转化
int CBigInt::OutPutToStr(CString& str, const unsigned int system/*=DEC*/)
{ str="";
char Mask[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
char ch;
CBigInt X;
X.SetValue(*this);
while(X.m_ulValue[X.m_nLength-1]>0)
{ //ch=X.Mod(system)+48;
ch=Mask[X.Mod(system)];
str.Insert(0,ch);
X.SetValue(X.Div(system));
}
if(!m_nSign) str.Insert (0,"-");
return 0;
}
//欧几里德算法求：Y=X.Euc(A)，使满足：YX mod A=1
//相当于对不定方程ax-by=1求最小整数解
//实际上就是初中学过的辗转相除法
/********************************************************************/
/*
例如：11x-49y=1，求x
11 x - 49 y = 1 a)
49%11=5 -> 11 x - 5 y = 1 b)
11%5 =1 -> x - 5 y = 1 c)
令y=1 代入c)式 得x=6
令x=6 代入b)式 得y=13
令y=13 代入a)式 得x=58
/********************************************************************/
CBigInt CBigInt::Euc(CBigInt& A)
{
CBigInt X,Y;
X.SetValue(*this);
Y.SetValue(A);
if((X.m_nLength==1)&&(X.m_ulValue[0]==1))return X;
if((Y.m_nLength==1)&&(Y.m_ulValue[0]==1)){X.SetValue(X.Sub(1));return X;}
if(X.Compare(Y)==1)X.SetValue(X.Mod(Y));
else Y.SetValue(Y.Mod(X));
X.SetValue(X.Euc(Y));
Y.SetValue(*this);
if(Y.Compare(A)==1)
{
X.SetValue(X.Mul(Y));
X.SetValue(X.Sub(1));
X.SetValue(X.Div(A));
}
else
{
X.SetValue(X.Mul(A));
X.SetValue(X.Add(1));
X.SetValue(X.Div(Y));
}
return X;
}
//蒙哥马利算法求：Y=X.Mon(A,B)，使满足：X^A mod B=Y
//俺估计就是高中学过的反复平方法
CBigInt CBigInt::Mon(CBigInt& A, CBigInt& B)
{
CBigInt X,Y,Z;
X.SetValue(1);
Y.SetValue(*this);
Z.SetValue(A);
while((Z.m_nLength!=1)||Z.m_ulValue[0])
{
if(Z.m_ulValue[0]&1)
{
Z.SetValue(Z.Sub(1));
X.SetValue(X.Mul(Y));
X.SetValue(X.Mod(B));
}
else
{
Z.SetValue(Z.Div(2));
Y.SetValue(Y.Mul(Y));
Y.SetValue(Y.Mod(B));
}
}
return X;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -