大数取余运算的C++实现

// Big_Int.cpp : Defines the entry point for the console application.
//
#include
#include
#include
#include
const long L = 900;
class Big_Int
{
public:
Big_Int();
~Big_Int();
Big_Int(const int ©);
Big_Int(const long ©);
Big_Int(const char *copy);
Big_Int &operator = (const Big_Int &right);
// "+":
Big_Int operator + (const Big_Int &second);
friend Big_Int operator + (const long &first, Big_Int &second);
friend Big_Int operator + (const char *first, Big_Int &second);
// "-":
Big_Int operator - (const Big_Int &second);
friend Big_Int operator - (const long &first, Big_Int &second);
friend Big_Int operator - (const char *first, Big_Int &second);
friend Big_Int operator - (const Big_Int &one);
// "*":
Big_Int operator * (const Big_Int &second);
friend Big_Int operator * (const long &first, Big_Int &second);
friend Big_Int operator * (const char *first, Big_Int &second);
// "/":
Big_Int operator / (const Big_Int &second);
friend Big_Int operator / (const long &first, Big_Int &second);
friend Big_Int operator / (const char *first, Big_Int &second);
// "%":
Big_Int operator % (const Big_Int &second);
friend Big_Int operator % (const long &first, Big_Int &second);
friend Big_Int operator % (const char *first, Big_Int &second);
//"=="
bool operator == (const Big_Int &second);
friend bool operator == (const long &first, Big_Int &second);
friend bool operator == (const char *first, Big_Int &second);
//"!="
bool operator != (const Big_Int &second);
friend bool operator != (const long &first, Big_Int &second);
friend bool operator != (const char *first, Big_Int &second);
//">="
bool operator >= (const Big_Int &second);
friend bool operator >= (const long &first, Big_Int &second);
friend bool operator >= (const char *first, Big_Int &second);
//"<="
bool operator <= (const Big_Int &second);
friend bool operator <= (const long &first, Big_Int &second);
friend bool operator <= (const char *first, Big_Int &second);
//">"
bool operator > (const Big_Int &second);
friend bool operator > (const long &first, Big_Int &second);
friend bool operator > (const char *first, Big_Int &second);
//"<"
bool operator < (const Big_Int &second);
friend bool operator < (const long &first, Big_Int &second);
friend bool operator < (const char *first, Big_Int &second);
// auxiliary functions
friend ostream &operator << (ostream &cout, const Big_Int &one);
friend istream &operator >> (istream &cin, Big_Int &one);
friend Big_Int Abs(const Big_Int &one);
friend Big_Int Pow(const Big_Int &x, long y);
long Digit();
double HighestNDigits(long &length);
void ProduceBigInt(const char *bigint, long begin, long end);
void Swap(Big_Int &a, Big_Int &b);
protected:
private:
long Int[L/4+1];
long digit;
};
//////////////////////////////////////////////////////////////////////////
Big_Int::Big_Int()
{
for(long i = 0; i <= L/4; i ++)
Int[i] = 0;
digit = 1;
}
Big_Int::~Big_Int()
{
}
Big_Int::Big_Int(const int ©)
{
int item;
item = abs(copy);
for(long i = L/4; i >= 0; i --)
{
Int[i] = abs(item%10000);
item = item/10000;
}
digit = Digit();
}
Big_Int::Big_Int(const long ©)
{
long item;
item = abs(copy);
for(long i = L/4; i >= 0; i --)
{
Int[i] = abs(item%10000);
item = item/10000;
}
digit = Digit();
}
Big_Int::Big_Int(const char *copy)
{
long n = strlen(copy);
if(copy[0] == '-')
{
ProduceBigInt(copy, 1, n);
for(long i = 0; i <= L/4; i ++)
Int[i] = -Int[i];
}
else
ProduceBigInt(copy, 0, n);
digit = Digit();
}
Big_Int &Big_Int::operator = (const Big_Int &right)
{
for(long i = 0; i <= L/4; i ++)
Int[i] = right.Int[i];
digit = right.digit;
return *this;
}
//////////////////////////////////////////////////////////////////////////
Big_Int Big_Int::operator + (const Big_Int &second)
{
Big_Int second_ = second;
if(*this > 0 && second_ < 0)
return (*this - (-second_));
else if(*this < 0 && second_ > 0)
return (second_ - (-(*this)));
else
{
Big_Int current;
long carry, i;
for(carry = 0, i = L/4; i >=0; i --)
{
current.Int[i] = Int[i] + second.Int[i] + carry;
carry = current.Int[i] / 10000;
current.Int[i] = current.Int[i] % 10000;
}
current.digit = current.Digit();
return current;
}
}
Big_Int operator + (const long &first, Big_Int &second)
{
return (second + first);
}
Big_Int operator + (const char *first, Big_Int &second)
{
return (second + first);
}
Big_Int Big_Int::operator - (const Big_Int &second)
{
Big_Int second_ = second;
if((*this > 0 && second_ <= 0) || (*this < 0 && second_ >= 0))
return (*this + (-second));
else
{
Big_Int current;
Big_Int a, b;
bool sign = true;
a = Abs(*this);
b = Abs(second_);
if(a < b) Swap(a, b);
for(long i = L/4, carry = 0; i >= L/4 - (a.digit-1)/4; i--)
{
current.Int[i] = a.Int[i] - b.Int[i] + carry;
if(current.Int[i] < 0)
{
current.Int[i] = 10000 + current.Int[i];
carry = -1;
}
else
carry = 0;
}
current.digit = current.Digit();
if(*this < second_)
current = -current;
return current;
}
}
Big_Int operator - (const long &first, Big_Int &second)
{
return ((-second) + first);
}
Big_Int operator - (const char *first, Big_Int &second)
{
return ((-second) + first);
}
Big_Int operator - (const Big_Int &one)
{
Big_Int current;
for(long i = L/4; i >= 0; i --)
current.Int[i] = -one.Int[i];
current.digit = current.Digit();
return current;
}
Big_Int Big_Int::operator * (const Big_Int &second)
{
Big_Int current;
long i, j, position;
bool sign= true;
for(i = L/4; i >= L/4-second.digit/4 && sign == true; i --)
{
for(j = L/4; j >= L/4-digit/4 && sign == true; j --)
{
position = i + j - L/4;
if(position < 0)
{
//cout << "Range-error is found when do the multiplication!" << endl;
sign = false;
break;
}
current.Int[position] = current.Int[position] + second.Int[i] * Int[j];
current.Int[position-1] = current.Int[position-1] + current.Int[position] / 10000;
current.Int[position] = current.Int[position] % 10000;
}
}
current.digit = current.Digit();
return current;
}
Big_Int operator * (const long &first, Big_Int &second)
{
return (second * first);
}
Big_Int operator * (const char *first, Big_Int &second)
{
return (second * first);
}
Big_Int Big_Int::operator / (const Big_Int &second_)
{
Big_Int first = Abs(*this), second = Abs(second_);
if(second == 0)
{
//cout << "Error found!/" << endl;
return *this;
}
Big_Int quotien = 0, remainder = first, power, bigTmp;
double dividend, divisor;
long tryQuotien, quotienPosition, remainderD, secondD, lenRem, lenSec;
long digitOfTry, change, longTmp;
secondD = (second.digit-1)/4 + 1;
lenSec = 2;
dividend = second.HighestNDigits(lenSec);
while(remainder >= second)
{
power = 0;
lenRem = lenSec + 1;
remainderD = (remainder.digit-1)/4 + 1;
quotienPosition = L/4 - (remainderD-secondD) + 1;
divisor = remainder.HighestNDigits(lenRem);
tryQuotien = long(divisor/dividend);
for(longTmp = tryQuotien, digitOfTry = 0; longTmp != 0; digitOfTry ++)
longTmp = longTmp/10;
if(digitOfTry > 4)
change = long(pow(10,digitOfTry-4));
else change = 1;
tryQuotien = (tryQuotien/change) * change;
quotien.Int[quotienPosition] = quotien.Int[quotienPosition] + tryQuotien%10000;
quotien.Int[quotienPosition-1] = quotien.Int[quotienPosition-1] + tryQuotien/10000;
//worked as quotien+tryQuotien
power.Int[quotienPosition] = tryQuotien%10000;
power.Int[quotienPosition-1] = tryQuotien/10000;
power.digit = power.Digit(); //worked as power*tryQuotien
bigTmp = remainder - power*second;
if(bigTmp >= 0)
remainder = bigTmp;
else
{
quotien.Int[quotienPosition] = quotien.Int[quotienPosition] - change;
power.Int[quotienPosition] = power.Int[quotienPosition] - change;
power.digit = power.Digit();
remainder = remainder - power*second;
}
}
quotien.digit = quotien.Digit();
if((*this)*second < 0) quotien = -quotien;
return quotien;
}
Big_Int operator / (const long &first, Big_Int &second)
{
if(second == 0)
{
//cout << "Error found!/" << endl;
return first;
}
Big_Int current = first;
return (current/second);
}
Big_Int operator / (const char *first, Big_Int &second)
{
if(second == 0)
{
//cout << "Error found!/" << endl;
return first;
}
Big_Int current = first;
return (current/second);
}
Big_Int Big_Int::operator % (const Big_Int &second)
{
Big_Int second_ = second;
if(second_ == 0)
{
//cout << "Error found!%" << endl;
return *this;
}
return *this - (*this/second)*second;
}
Big_Int operator % (const long &first, Big_Int &second)
{
if(second == 0)
{
//cout << "Error found!%" << endl;
return first;
}
Big_Int current = first;
return current - second*(current/second);
}
Big_Int operator % (const char *first, Big_Int &second)
{
if(second == 0)
{
//cout << "Error found!%" << endl;
return first;
}
Big_Int current = first;
return current - second*(current/second);
}
Big_Int Abs(const Big_Int &one)
{
Big_Int current;
for(long i = 0; i <= L/4; i ++)
current.Int[i] = abs(one.Int[i]);
current.digit = one.digit;
return current;
}
Big_Int Pow(const Big_Int &x, long y)
{
Big_Int current = 1;
if(y != 0)
{
for(long i = 1; i <= y; i ++)
{
current = current*x;
}
}
return current;
}
//////////////////////////////////////////////////////////////////////////
bool Big_Int::operator > (const Big_Int &second)
{
bool positive1 = true, positive2 = true, sign = true;
long i;
Big_Int second_ = second;
if(this->Int[L/4] < 0) positive1 = false;
if(second_.Int[L/4] < 0) positive2 = false;
if(positive1 == false && positive2 == true)
sign = false;
else if(digit < second.digit && positive1 == true && positive2 == true)
sign = false;
else if(digit > second.digit && positive1 == false && positive2 == false)
sign = false;
else if(digit == second.digit && !(positive1 == true && positive2 == false))
{
for(i = 0; i <= L/4 && sign == true; i ++)
{
if(Int[i] > second.Int[i])
break;
else if(Int[i] < second.Int[i] || (Int[i] == second.Int[i] && i == L/4))
sign = false;
}
}
return sign;
}
bool operator > (const long &first, Big_Int &second)
{
return (second < first);
}
bool operator > (const char *first, Big_Int &second)
{
return (second < first);
}
bool Big_Int::operator < (const Big_Int &second)
{
return !(*this > second || *this == second);
}
bool operator < (const long &first, Big_Int &second)
{
return (second > first);
}
bool operator < (const char *first, Big_Int &second)
{
return (second > first);
}

bool Big_Int::operator <= (const Big_Int &second)
{
return !(*this > second);
}
bool operator <= (const long &first, Big_Int &second)
{
return (second >= first);
}
bool operator <= (const char *first, Big_Int &second)
{
return (second >= first);
}

bool Big_Int::operator >= (const Big_Int &second)
{
return !(*this < second);
}
bool operator >= (const long &first, Big_Int &second)
{
return (second <= first);
}
bool operator >= (const char *first, Big_Int &second)
{
return (second <= first);
}
bool Big_Int::operator == (const Big_Int &second)
{
bool sign = true;
for(long i = 0; i <= L/4 && sign == true; i ++)
{
if(Int[i] != second.Int[i])
sign = false;
}
return sign;
}
bool operator == (const long &first, Big_Int &second)
{
return (second == first);
}
bool operator == (const char *first, Big_Int &second)
{
return (second == first);
}

bool Big_Int::operator != (const Big_Int &second)
{
return !(*this == second);
}
bool operator != (const long &first, Big_Int &second)
{
return (second != first);
}
bool operator != (const char *first, Big_Int &second)
{
return (second != first);
}
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
ostream &operator << (ostream &cout, const Big_Int &one)
{
long i, begin, current;
for(begin = 0; begin <= L/4; begin ++)
{
if(one.Int[begin] != 0)
break;
}
if(begin == L/4 + 1)
cout << 0;
else
{
cout << one.Int[begin];
for(i = begin + 1; i <= L/4; i ++)
{
current = abs(one.Int[i]);
//cout << " ";
cout.fill('0');
cout.width(4);
cout << current;
}
}
return cout;
}
istream & operator >> (istream &cin, Big_Int &one)
{
char copy[L];
scanf("%s",copy);
Big_Int current(copy);
one = current;
return cin;
}
long Big_Int::Digit()
{
long i, d, abs_;
for(i = 0; i <= L/4 && Int[i] == 0; i ++)
;
d = 4*(L/4 - i);
abs_ = abs(Int[i]);
if(abs_ < 10)
d = d + 1;
else if(abs_ < 100)
d = d + 2;
else if(abs_ < 1000)
d = d + 3;
else
d = d + 4;
return d;
}
void Big_Int::ProduceBigInt(const char *bigint, long begin, long end)
{
long n, i, j, current, position;
n = end - begin;
position = L/4 - (n-1)/4;
for(i = 0; i < position; i ++)
Int[i] = 0;
if(n%4 != 0)
{
for(i = begin, current = 0; i < begin + n%4; i ++)
current = 10*current + (bigint[i] - '0');
Int[position ++] = current;
}
for(i = begin + n%4; i < end; )
{
for(j = 0, current = 0; j < 4; j ++)
current = 10*current + (bigint[i ++] - '0');
Int[position ++] = current;
}
}
double Big_Int::HighestNDigits(long &length)
{
long beginPosition, occupiedDigit, position;
double highestNDigit = 0;
occupiedDigit = (digit-1)/4 + 1;
beginPosition = L/4 - occupiedDigit + 1;
if(length > occupiedDigit)
length = occupiedDigit;
for(position = beginPosition; position < beginPosition + length; position ++)
highestNDigit = highestNDigit*10000 + Int[position];
return highestNDigit;
}
void Big_Int::Swap(Big_Int &a, Big_Int &b)
{
Big_Int temp;
temp = a;
a = b;
b = temp;
}
//////////////////////////////////////////////////////////////////////////
int main()
{
Big_Int a, b;
//Big_Int c;
char p[L], q[L];
while(scanf("%s%s",p,q) == 2)
{
a = p;
b = q;
//c = a*b;
//cout << a << " " << b << " ";
cout << a/b << endl;
//cout << c/b << " c/b" << endl
// << c/a << " c/a" << endl;
}
return 0;
}

大数类。

可以用 辗转相除法求解.我也想知道,呵呵