📄 bigint.cpp
字号:
carry=tmp%A;
}
mod=carry;
for(myi=result.m_nLength-1;myi>=0;myi--)
{
if(result.m_ulvalue[myi]==0)
{
result.m_nLength--;
}
else
{
break;
}
}
return result;
}
CBigInt CBigInt::Div(long A)
{
unsigned long carry=0;
int myi;
My_int64 tmp;
CBigInt result(this->base);
result.m_nLength=this->m_nLength;
for(myi=this->m_nLength-1;myi>=0;myi--)
{
tmp=carry*this->base+this->m_ulvalue[myi];
result.m_ulvalue[myi]=tmp/A;
carry=tmp%A;
}
for(myi=result.m_nLength-1;myi>=0;myi--)
{
if(result.m_ulvalue[myi]==0)
{
result.m_nLength--;
}
else
{
break;
}
}
return result;
}
//file://大数求模
//file://调用形式：N.Mod(A)，返回值：N%A
//file://求模与求商原理相同
CBigInt CBigInt::Mod(CBigInt& A)
{
CBigInt X(base),Y(base);
int len,i;
My_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*base+X.m_ulvalue[X.m_nLength-2];
if(A.m_ulvalue[A.m_nLength-1]==(base-1))
div=num/base;
else
div=num/(A.m_ulvalue[A.m_nLength-1]+1);
}
else
{
//X.Sub(A);
X.Mov(X.Sub(A));
break;
}
Y.Mov(div);
Y.Mov(Y.Mul(A));
//Y.Mul(A);
Y.m_nLength+=len;
for(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));
//X.Sub(Y);
}
if(X.Cmp(A)==0)
X.Mov(0);
return X;
}
long CBigInt::Mod(long A)
{
My_int64 tmp=0;
for(unsigned int i=this->m_nLength-1;i>=0;i--)
{
tmp*=this->base;
tmp+=this->m_ulvalue[i];
tmp=tmp%A;
if(i==0)
break;
}
return (long)tmp;
}
//file://暂时只给出了十进制字符串的转化
int CBigInt::InPutFromStr(string& str, const unsigned int system=DEC)
{
int len=str.length(),i,j;
unsigned long tmp;
Mov(0);
if(system==10)
{
base=100000000;
for(i=len-1,m_nLength=0;i>-1;m_nLength++)//m_nLength代表大数的那个位数
{
tmp=1;
for(j=0;j<8&&i>-1;j++,i--)
{
m_ulvalue[m_nLength]+=(str[i]-'0')*tmp;
tmp*=10;
}
}
}
else
{
base=0x100000000;//这个地方存在问题，处理不好兼容性会出问题
//处理16进制的输入
}
return 0;
}
//file://暂时只给出了十进制字符串的转化
//mcqsmall://在这里的转化效率真的很低，有待改进
int CBigInt::OutPutToStr(string& str, const unsigned int system)
{
str="";
char ch[9];
int len=0,i;
for(i=0;i<m_nLength-1;i++)
{
_ultoa(m_ulvalue[i],ch,system);
len=strlen(ch);
str.insert(0,ch);
for(len=8-len;len>0;len--)
str.insert(0,"0");
}
_ultoa(m_ulvalue[i],ch,system);
str.insert(0,ch);
/*
CBigInt X;
X.Mov(*this);
while(X.m_ulvalue[X.m_nLength-1]>0)
{
ch=X.Mod(system)+48;
str.insert(0,ch);
X.Mov(X.Div(system));//建议不要这样写，这样可能耗费的内存空间会比较大
}
*/
return 0;
}
//file://欧几里德算法求：Y=X.Euc(A)，使满足：YX mod A=1
//file://相当于对不定方程ax-by=1求最小整数解
//file://实际上就是初中学过的辗转相除法
/********************************************************************
例如：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(base),Y(base),tmp(base);
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));
if(X.Cmp(0)==0)
return Y;
}
tmp.Mov(Y.Mod(X));
while(tmp.Cmp(0)!=0)
{
Y.Mov(X);
X.Mov(tmp);
tmp.Mov(Y.Mod(X));
}
return 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::Euc(CBigInt &A, CBigInt &result)
{
CBigInt q,s_1,s_2,r_j,r_j1,tmp;
s_2.Mov(1);
s_1.Mov(0);
r_j.Mov(*this);
r_j1.Mov(A);
q.Mov(r_j.Div(r_j1));
tmp.Mov(r_j.Mod(r_j1));
r_j.Mov(r_j1);
r_j1.Mov(tmp);
result.Mov(0);
while(r_j1.Cmp(0)!=0)
{
q.Mov(q.Mul(s_1));
result.Mov(s_2.Sub(q));
s_2.Mov(s_1);
s_1.Mov(result);
q.Mov(r_j.Div(r_j1));
tmp.Mov(r_j.Mod(r_j1));
r_j.Mov(r_j1);
r_j1.Mov(tmp);
}
result.Mov(result.Add(A));
return r_j;
}
//file://蒙哥马利算法求：Y=X.Mon(A,B)，使满足：X^A mod B=Y
//file://俺估计就是高中学过的反复平方法
CBigInt CBigInt::Mon(CBigInt& A, CBigInt& B)
{
CBigInt X(base),Y(base),Z(base);
int i;
unsigned long tmp,myk;
long k;
X.Mov(1);
Y.Mov(*this);
Z.Mov(A);
while(Z.Cmp(0)!=0)
{
Z.Mov(Z.Div(2,k));
if(k!=0)
{
X.Mov(X.Mul(Y));
X.Mov(X.Mod(B));
}
Y.Mov(Y.Mul(Y));
Y.Mov(Y.Mod(B));
}
return X;
/*
if(this->m_nLength==1)//小底数的模乘方
{
}
else//
{
*/
Y.Mov(this->Mod(B));
X.Mov(Y);
Z.Mov(A);
if(base==100000000)
{
myk=0x4000000;
}
else
{
myk=0x80000000;
}
//处理最高位
tmp=Z.m_ulvalue[Z.m_nLength-1];
k=myk;
while((k&tmp)==0)
{
k>>=1;
}
k>>=1;
while(k!=0)
{
Y.Mov(Y.Mul(Y));
Y.Mov(Y.Mod(B));
if(k&tmp)
{
Y.Mov(Y.Mul(X));
Y.Mov(Y.Mod(B));
}
k>>=1;
}
//处理剩下的各个位
for(i=Z.m_nLength-2;i>=0;i--)
{
tmp=Z.m_ulvalue[i];
k=myk;
while(k!=0)
{
Y.Mov(Y.Mul(Y));
Y.Mov(Y.Mod(B));
if(k&tmp)
{
Y.Mov(Y.Mul(X));
Y.Mov(Y.Mod(B));
}
k>>=1;
}
}
return Y;
/*
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;
//}
}
//小指数的模乘方
CBigInt CBigInt::Mon(unsigned int A,CBigInt& B)
{
CBigInt result(this->base),tmp_base(this->base),tmp_this(this->base);
unsigned long k=0x8000;
if(B.Cmp(0)==0)//除数为0
{
result.Clear0();
return result;
}
if(B.Cmp(1)==0)//模==1 剩余为0
{
result.Clear0();
return result;
}
if(A==0)//指数为0
{
result.Mov(1);
return result;
}
if(this->Cmp(0)==0)
{
result.Clear0();
return result;
}
tmp_base.Mov(this->Mod(B));
tmp_this.Mov(tmp_base);
while((A&k)==0)
{
k>>=1;
}
k>>=1;
while(k!=0)
{
tmp_base.Mov(tmp_base.Mul(tmp_base));
tmp_base.Mov(tmp_base.Mod(B));
if(A&k)
{
tmp_base.Mov(tmp_base.Mul(tmp_this));
tmp_base.Mov(tmp_base.Mod(B));
}
k>>=1;
}
return tmp_base;
}
//file://错误处理
void PrintErr(int Errnum)
//void PrintErr(string& str)
{
//1:表示溢出，超出了最大能承受的范围
if(Errnum==1)
{
cout<<"Digits execd the largest number ,please redefine the BI_MAXLEN"<<endl;
}
//cout<<str<<endl;
}
int CBigInt::Is_Even()
{
if(this->m_ulvalue[0]%2==0)
return 1;
else
return 0;
}
CBigInt CBigInt::Gcd(CBigInt A)
{
CBigInt temp,tmp_this,tmp_A;
tmp_this.Mov(*this);
if(tmp_this.Cmp(tmp_A)<0)
{
temp.Mov(tmp_this);
tmp_this.Mov(tmp_A);
tmp_A.Mov(temp);
}
while(tmp_A.Cmp(0)!=0)
{
temp.Mov(tmp_this.Mod(tmp_A));
tmp_this.Mov(tmp_A);
tmp_A.Mov(temp);
}
return tmp_this;
}
//生成随机数
void CBigInt::Rand(unsigned long bigint_len)
{
unsigned long temp,chengshu;
this->Clear0();
srand((unsigned )time(NULL));
temp=rand()%9973;
temp*=10000;
temp+=rand()%9973;
this->Mov(temp);
while(this->m_nLength<bigint_len)
{
chengshu=rand()%9973;
chengshu*=10000;
chengshu+=rand()%9973;
this->Mul(chengshu);
}
if(this->m_ulvalue[0]%2==0)
this->m_ulvalue[0]++;
}
//64位随机数初始化
CBigInt CBigInt::Seed(CBigInt seed_l)
{
int len=seed_l.m_nLength>4?4:seed_l.m_nLength;
A64.InPutFromStr(a,10);
M.InPutFromStr(b,10);
Buff64.Mov(Seed64);
for(int i=0;i<=len;i++)
{
Seed64.m_ulvalue[i]=seed_l.m_ulvalue[i];
}
return Buff64;
}
//64位随机数生成
CBigInt CBigInt::Rand64(void)
{
Seed64.Mov(Seed64.Mov(A64));
Seed64.Mov(Seed64.Add(1));
Seed64.Mov(Seed64.Mod(M));
return Seed64;
};
/*
最后需要说明的是因为在VC里面存在一个__int64类型可以
用来计算进位与借位值，所以将大数当作0x100000000进制
进行运算是可能的，而在其他编译系统中如果不存在64位
整形，则可以采用0x40000000进制，由于在0x40000000
进制中，对任何两个“数字”进行四则运算，结果都在
0x3fffffff*03fffffff之间，小于0xffffffff，都可以用
一个32位无符号整数来表示。事实上《楚汉棋缘》采用的
freelip大数库正是运用了0x40000000进制来表示大数的，
所以其反汇编后大数的值在内存中表现出来有些“奇怪”。
*/⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -