📄 bint.cpp
字号:
{ N.m_Value[N.m_Length]=carry;
N.m_Length+=carry;
}
if(N.m_Length<m_Length)
N.m_Length=m_Length;
if(cmp>0)
N.m_Sign=B.m_Sign;
}
else
N.SetValue(0);
return N;
/*
N.SetValue(B);
N.m_Sign=1-N.m_Sign;
return Add(N);
*/
}
}
CBint CBint::Sub(long B) const
{ CBint N(*this);
if(B==0)
return N;
if((m_Sign*B)>=0)
{
if(N.m_Value[0]>=(unsigned long)B)
{ N.m_Value[0]-=B;
return N;
}
if(N.m_Length==1)
{ N.m_Value[0]=B-N.m_Value[0];
N.m_Sign=1-N.m_Sign;
return N;
}
unsigned __int64 num=0x100000000+N.m_Value[0];
N.m_Value[0]=(unsigned long)(num-B);
int i=1;
while(N.m_Value[i]==0)
{
N.m_Value[i]=0xffffffff;
i++;
}
if(N.m_Value[i]==1)
N.m_Length--;
N.m_Value[i]--;
return N;
}
else
return N.Add(-B);
}
//大数相乘
//调用形式：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
/*****************************************************************/
CBint CBint::Mul(const CBint& A) const
{ CBint X,Y;
unsigned __int64 mul;
unsigned long carry;
for(int i=0;i<A.m_Length;i++)
{
Y.m_Length=m_Length;
carry=0;
for(int j=0;j<m_Length;j++)
{
//mul=m_Value[j];
//mul=mul*A.m_Value[i]+carry;
mul=(unsigned __int64)m_Value[j]*A.m_Value[i]+carry;
Y.m_Value[j]=(unsigned long)mul;
carry=(unsigned long)(mul>>32);
}
if(carry&&(Y.m_Length<BI_MAXLEN))
{
Y.m_Length++;
Y.m_Value[Y.m_Length-1]=carry;
}
if(Y.m_Length<BI_MAXLEN-i)
{
Y.m_Length+=i;
for(int k=Y.m_Length-1;k>=i;k--)
Y.m_Value[k]=Y.m_Value[k-i];
/*for(k=0;k<i;k++)
Y.m_Value[k]=0;
*/
ZeroMemory(Y.m_Value,i*sizeof(unsigned long));
}
X.SetValue(X.Add(Y));
}
if(m_Sign+A.m_Sign==1)
X.m_Sign=0;
else
X.m_Sign=1;
return X;
}
CBint CBint::Mul(long A) const
{
CBint X;
unsigned __int64 mul;
unsigned long carry=0;
X.SetValue(*this);
for(int i=0;i<m_Length;i++)
{
mul=(unsigned __int64)m_Value[i]*A+carry;
X.m_Value[i]=(unsigned long)mul;
carry=(unsigned long)((mul-X.m_Value[i])>>32);
}
if(carry&&(X.m_Length<BI_MAXLEN))
{ X.m_Length++;
X.m_Value[X.m_Length-1]=carry;
}
if(A<0)
X.m_Sign=1-X.m_Sign;
return X;
}
//大数相除
//调用形式：N.Div(A)，返回值：N/A
//除法的关键在于“试商”，然后就变成了乘法和减法
//这里将被除数与除数的试商转化成了被除数最高位与除数最高位的试商
CBint CBint::Div(const CBint& A) const
{ CBint X,Y,Z;
int len;
unsigned __int64 num,div;
unsigned long carry=0;
Y.SetValue(*this);
if(A.Compare(0)==0)
{
return X;
}
while(Y.Compare(A)>0)
{
if(Y.m_Value[Y.m_Length-1]>A.m_Value[A.m_Length-1])
{
len=Y.m_Length-A.m_Length;
div=Y.m_Value[Y.m_Length-1]/(A.m_Value[A.m_Length-1]+1);
}
else if(Y.m_Length>A.m_Length)
{
len=Y.m_Length-A.m_Length-1;
num=Y.m_Value[Y.m_Length-1];
num=(num<<32)+Y.m_Value[Y.m_Length-2];
if(A.m_Value[A.m_Length-1]==0xffffffff)
div=(num>>32);
else
div=num/(A.m_Value[A.m_Length-1]+1);
}
else
{
X.SetValue(X.Add(1));
break;
}
Z.SetValue(div);
Z.m_Length+=len;
for(int i=Z.m_Length-1;i>=len;i--)
Z.m_Value[i]=Z.m_Value[i-len];
for(i=0;i<len;i++)
Z.m_Value[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_Sign+A.m_Sign==1)
X.m_Sign=0;
else
X.m_Sign=1;
return X;
}
CBint CBint::Div(long A) const
{
CBint X;
X.SetValue(*this);
if(X.m_Length==1){X.m_Value[0]=X.m_Value[0]/A;return X;}
unsigned __int64 div,mul;
unsigned long carry=0;
for(int i=X.m_Length-1;i>=0;i--)
{
div=carry;
div=(div<<32)+X.m_Value[i];
X.m_Value[i]=(unsigned long)(div/A);
mul=(div/A)*A;
carry=(unsigned long)(div-mul);
}
if(X.m_Value[X.m_Length-1]==0)X.m_Length--;
if(A<0)X.m_Sign=1-X.m_Sign;
return X;
}
//大数求模
//调用形式：N.Mod(A)，返回值：N%A
//求模与求商原理相同
CBint CBint::Mod(const CBint& A) const
{ CBint X(*this);
X=X.Sub(X.Div(A).Mul(A));
/*
CBint X,Y;
int len;
unsigned __int64 num,div;
unsigned long carry=0;
X.SetValue(*this);
while(X.Compare(A)>0)
{
if(X.m_Value[X.m_Length-1]>A.m_Value[A.m_Length-1])
{
len=X.m_Length-A.m_Length;
div=X.m_Value[X.m_Length-1]/(A.m_Value[A.m_Length-1]+1);
}
else if(X.m_Length>A.m_Length)
{
len=X.m_Length-A.m_Length-1;
num=X.m_Value[X.m_Length-1];
num=(num<<32)+X.m_Value[X.m_Length-2];
if(A.m_Value[A.m_Length-1]==0xffffffff)div=(num>>32);
else div=num/(A.m_Value[A.m_Length-1]+1);
}
else
{
X.SetValue(X.Sub(A));
break;
}
Y.SetValue(div);
Y.SetValue(Y.Mul(A));
Y.m_Length+=len;
for(int i=Y.m_Length-1;i>=len;i--)
Y.m_Value[i]=Y.m_Value[i-len];
//for(i=0;i<len;i++)
// Y.m_Value[i]=0;
ZeroMemory(Y.m_Value,len*sizeof(unsigned long));
X.SetValue(X.Sub(Y));
}
if(X.Compare(A)==0)
X.SetValue(0);
*/
return X;
}
long CBint::Mod(long A) const
{ if(m_Length==1)
{ register long X=m_Value[0];
if(m_Sign==0) X=-X;
return X-(X/A)*A;
}
unsigned __int64 div;
unsigned long carry=0;
for(int i=m_Length-1;i>=0;i--)
{
div=carry*0x100000000+m_Value[i];
carry=(unsigned long)(div-((div/A)*A));
}
return carry;
}
long CBint::ModAbs(long A) const
{ unsigned __int64 div;
unsigned long carry=0;
for(int i=m_Length-1;i>=0;i--)
{
div=carry*0x100000000+m_Value[i];
carry=(unsigned long)(div-((div/A)*A));
}
return carry;
}
//暂时只给出了十进制字符串的转化
int CBint::InPutFromStr(CString& str, const unsigned int system /*=AUTO */)
{ int autoSystem,len=str.GetLength();
register int i=0,k=0;
autoSystem=system;
if(autoSystem==AUTO_SYSTEM)
{ autoSystem=DEC_SYSTEM;
CString x(str.Left(2));
x.MakeLower();
if(x =="0x")
{
autoSystem=HEX_SYSTEM;
i=2;
}
}
SetValue(0);
for(;i<len;i++)
{ if(i==0 && str[i]=='-')
m_Sign=0;
else
{
SetValue(Mul(autoSystem));
k=str[i]-48;
SetValue(Add(k));
}
}
return 0;
}
//暂时只给出了十进制字符串的转化
int CBint::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;
CBint X(*this);
while(X.m_Value[X.m_Length-1]>0)
{ //ch=X.Mod(system)+48;
ch=Mask[X.Mod(system)];
str.Insert(0,ch);
X.SetValue(X.Div(system));
}
if(!m_Sign) 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
/********************************************************************/
CBint CBint::Euc(CBint& A)
{
CBint X,Y;
X.SetValue(*this);
Y.SetValue(A);
if((X.m_Length==1)&&(X.m_Value[0]==1))
return X;
if((Y.m_Length==1)&&(Y.m_Value[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
//俺估计就是高中学过的反复平方法
CBint CBint::Mon(CBint& A, CBint& B)
{
CBint X,Y,Z;
X.SetValue(1);
Y.SetValue(*this);
Z.SetValue(A);
while((Z.m_Length!=1)||Z.m_Value[0])
{
if(Z.m_Value[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;
}
//求X^Y次方 Mod N
CBint CBint::Powmod(CBint Y,CBint N)
{ CBint Result(1),X(*this),Zero((unsigned __int64)0);
while(Y.Compare(Zero)>0)
{
while(Y.Mod(2)==0)
{ X =X.Mul(X);
X=X.Mod(N); // X^2 % N
Y =Y.Div(2);
}
Result = Result.Mul(X).Mod(N);// Mod((m.X * m.ReturnValue), m._N)
Y = Y.Sub(1);
}
return Result;
}
CBint CBint::Powmod(unsigned long Y,CBint N)
{
return Powmod(CBint(Y),N);
}
bool CBint::IsPrimeNumber()
{
if(Compare(1)<0)
return false;
else if (Compare(2)==0)
return true;
for(CBint i(2);i.Compare(1000)>0 ;i++)
{ if(i.Mod(2)==0)
return false;
}
return true;
}
CBint CBint::Sqrt()
{ CBint a(*this),x0,x1;
CString a1,a2;
if(a.Compare(0)<0)
a.SetValue(0);
if(a.Compare(1)<=0)
return a;
x0=a.Div(2);
x1=x0.Add(a.Div(x0)).Div(2); //x1=(x0+a/x0)/2;
do
{ x0=x1;
x1=x0.Add(a.Div(x0)).Div(2); //x1=(x0+a/x0)/2;
//if(x1.Compare(0)==0 || x1.Compare(1)==0) break;
}while(x0.Sub(x1).Compare(0)>0); // fabs(x0-x1)>=0);
if(x1.Compare(1)>0 && x1.Mul(x1).Abs().Compare(a)>0)
x1=x1.Sub(1);
//if(a.Compare(1)==0)
// x1.SetValue(1);
return x1;
}⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -