?? bigint.cpp
字號:
InitMulCache(B);
for(int i=A.len-1,f,h,t,m; i>=0; )
{
if( !GetDivNext(Mod,A,B,i) )
break;
//用二分法找商
h=1; t=BI_BASE-1;
while( h<=t )
{
m = (h+t) >> 1;
f = Cmp(MulCache[m],Mod);
if( !f )
break;
if( f>0 )
t = m-1;
else
h = m+1;
}
Out.bit[i+1] = f ? --h : m;
if(f)
Sub(Mod,Mod,MulCache[h]);
else
Mod = Zero;
}
SetLen( Out,A.len-B.len);
Spls = Mod;
M = Out;
return true;
}
/******************************************************************************/
// 名稱：Add
// 功能：大數加法 ( C = A + B )
// 參數：
// 返回：成功返回true，否則返回false
// 備注：
// 更新：2003/1/25
// 作者：0200935王俊川
/***************************************************************************/
bool CBigInt::Add(BigInt &C,BigInt &A,BigInt &B)
{
static BigInt Out,*pa,*pb;
if( A.len > B.len )
pa=&A,pb=&B;
else
pa=&B,pb=&A;
Out = *pa;
for(UINT i=0,carry=0,j=pb->len,tmp; i<j; ++i)
{
tmp = pa->bit[i] + pb->bit[i] + carry;
if( tmp > BI_BASE-1 )
{
tmp -= BI_BASE;
carry = 1;
}
else
{
carry = 0;
}
Out.bit[i] = tmp;
}
if(carry)
{
while( Out.bit[i] == BI_BASE-1 )
{
Out.bit[i] = 0;
CHECK( ++i < BI_MAXLEN );
}
CHECK( i < BI_MAXLEN );
++Out.bit[i];
if( i == pa->len )
++Out.len;
}
C = Out;
return true;
}
/******************************************************************************/
// 名稱：Sub
// 功能：大數減法 ( C = A - B )
// 參數：
// 返回：成功返回true，否則返回false
// 備注：調用前保證A >= B，否則結果不對
// 更新：2003/1/25
// 作者：0200935王俊川
/******************************************************************************/
bool CBigInt::Sub(BigInt &C,BigInt &A,const BigInt &B)
{
if( &C != &A )
C = A;
for(int i=0,carry=0,j=B.len,tmp; i<j; ++i)
{
tmp = A.bit[i] - B.bit[i] - carry;
if( tmp<0 )
{
tmp += BI_BASE;
carry = 1;
}
else
{
carry = 0;
}
C.bit[i] = tmp;
}
if(carry)
{
while( !C.bit[i] )
{
C.bit[i] = BI_BASE-1;
CHECK( ++i < BI_MAXLEN );
}
CHECK( i < BI_MAXLEN );
--C.bit[i];
}
SetLen(C,C.len-1);
return true;
}
/******************************************************************************/
// 名稱：InitMulCache
// 功能：初始化乘法緩存 ( MulCache[i] = In*i )
// 參數：
// 返回：成功返回true，否則返回false
// 備注：
// 更新：2003/1/20
// 作者：0200906高志剛
/******************************************************************************/
bool CBigInt::InitMulCache(BigInt &In)
{
MulCache[1] = In;
for(int i=2; i<BI_BASE; ++i)
{
CHECK( Add(MulCache[i],MulCache[i-1],In) )
}
return true;
}
/******************************************************************************/
// 名稱：SetLen
// 功能：設置大數的長度
// 參數：
// 返回：
// 備注：
// 更新：2003/1/20
// 作者：0200906高志剛
/***************************************************************************/
void CBigInt::SetLen(BigInt &BI,UINT start)
{
for( int i=start; i>=0 && !BI.bit[i]; --i );
BI.len = i+1;
}
/******************************************************************************/
// 名稱：ShR
// 功能：大數邏輯右移
// 參數：
// 返回：成功返回true，否則返回false
// 備注：
// 更新：2003/1/20
// 作者：0200906高志剛
/******************************************************************************/
bool CBigInt::ShR(BigInt &Out,BigInt &In,UINT len)
{
CHECK( (In.len+len) <= BI_MAXLEN )
if( !len )
{
if( &Out != &In )
Out = In;
}
else if( In.len )
{
static BigInt Tmp;
Tmp = Zero;
memcpy(Tmp.bit+len,In.bit,In.len);
Tmp.len = In.len + len;
Out = Tmp;
}
return true;
}
/******************************************************************************/
// 名稱：Cmp
// 功能：大數比較
// 參數：
// 返回：A>B 返回 1; A=B 返回 0; A<B 返回 -1
// 備注：
// 更新：2003/1/20
// 作者：0200906高志剛
/******************************************************************************/
int CBigInt::Cmp(const BigInt &A,const BigInt &B)
{
int i=A.len;
if( (UINT)i > B.len )
return 1;
if( (UINT)i < B.len )
return -1;
for(--i; i>=0; --i)
{
if( A.bit[i] > B.bit[i] )
return 1;
if( A.bit[i] < B.bit[i] )
return -1;
}
return 0;
}
/******************************************************************************/
// 名稱：New
// 功能：產生一個大數
// 參數：
// 返回：
// 備注：
// 更新：2003/1/20
// 作者：0200906高志剛
/******************************************************************************/
BigInt CBigInt::New(long n)
{
int i=0;
BigInt Out;
memset(Out.bit,0,BI_MAXLEN);
while(n)
{
Out.bit[i++] = n%BI_BASE;
n /= BI_BASE;
}
Out.len = i;
return Out;
}
/******************************************************************************/
// 名稱：GetVal
// 功能：獲取大數的值
// 參數：
// 返回：
// 備注：
// 更新：2003/1/20
// 作者：0200906高志剛
/******************************************************************************/
long CBigInt::GetVal(const BigInt &In)
{
CHECK( In.len )
long n=0;
for(int i=In.len-1; i>=0; --i)
{
n *= BI_BASE;
n += In.bit[i];
}
return n;
}
/******************************************************************************/
// 名稱：SetVal
// 功能：設置大數的值
// 參數：
// 返回：
// 備注：
// 更新：2003/1/20
// 作者：0200906高志剛
/******************************************************************************/
void CBigInt::SetVal(BigInt &BI,long n)
{
int i=0;
BI = Zero;
while(n)
{
BI.bit[i++] = n%BI_BASE;
n /= BI_BASE;
}
BI.len = i;
}
/******************************************************************************/
// 名稱：BuildBIFromByte
// 功能：由輸入字節組構造一個大數
// 參數：
// 返回：構造成功返回true，否則返回false
// 備注：
// 更新：2003/1/20
// 作者：0200906高志剛
/******************************************************************************/
bool CBigInt::BuildBIFromByte(BigInt &Out,const char *In,UINT len)
{
CHECK( In && len<=BI_MAXLEN/4 )
Out = Zero;
CGfL::ByteToHalfByte(Out.bit,In,len);
SetLen(Out,len<<1);
return true;
}
/******************************************************************************/
// 名稱：BuildBIFromHalfByte
// 功能：由輸入半字節組構造一個大數
// 參數：
// 返回：構造成功返回true，否則返回false
// 備注：
// 更新：2003/1/20
// 作者：0200906高志剛
/******************************************************************************/
bool CBigInt::BuildBIFromHalfByte(BigInt &Out,const char *In,UINT len)
{
CHECK( In && len<=BI_MAXLEN/2 )
Out = Zero;
memcpy(Out.bit,In,len);
SetLen(Out,len);
return true;
}
/******************************************************************************/
// 名稱：BuildBIFromStr
// 功能：由輸入字符串構造一個大數
// 參數：len—字符串長度
// 返回：構造成功返回true，否則返回false
// 備注：
// 更新：2003/1/20
// 作者：0200906高志剛
/******************************************************************************/
bool CBigInt::BuildBIFromStr(BigInt &Out,char *In,UINT len)
{
CHECK( In && len<=BI_MAXLEN/2 )
Out = Zero;
CGfL::StrToHalfByte( Out.bit,In,len);
SetLen(Out,len);
return true;
}
/******************************************************************************/
// 名稱：Rand
// 功能：產生隨機大數
// 參數：len—隨機大數的長度
// 返回：產生成功返回true，否則返回false
// 備注：
// 更新：2003/1/20
// 作者：0200906高志剛
/******************************************************************************/
bool CBigInt::RandVal(BigInt &Out,UINT len)
{
CHECK( len>0 && len<=BI_MAXLEN )
Out = Zero;
srand(GetTickCount());
for(UINT i=0; i<len; ++i)
{
Out.bit[i] = rand()%BI_BASE;
}
Out.bit[0] |= 1;
Out.bit[len-1] |= 1;
Out.len = len;
return true;
}
///////////////////////////////////////////////////////////////////////////////
// End of Files
///////////////////////////////////////////////////////////////////////////////
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -