imported>Unknown at 05:28, 7 February 2021

2021-02-07T05:28:42Z

New page

== About ==
C++ 용 BigInteger 클래스로 거의 모든 연산을 지원한다. UVA 사이트의 구식(?) 컴파일러에도 문제없이 통과할 뿐 아니라, 성능또한 훌륭하다. 고정도 정수 연산을 하는 문제의 경우, 고정도 연산을 하는 라이브러리를 본인이 직접 짜거나, 이 클래스를 이용하면 된다. 몇 일동안 삽질한 결과 후자가 낫다는 판단이 선다. 되게 잘 짜여진 코드다. 시간 내서 분석해봐야 겠다.

== Code ==
/**
* BigInteger Class
* Version 6.7.25
*
* Copyright (c) 2001
* Mahbub Murshed Suman (suman@bttb.net.bd)
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Mahbub Murshed Suman makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*/
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <malloc.h>
#include <cmath>
#include <cstring>
#include <ctime>
#include <strstream>
#include <string>
#include <stdexcept>

using namespace std;

namespace BigMath
{
enum BigMathERROR { BigMathMEM = 1 , BigMathOVERFLOW , BigMathUNDERFLOW, BigMathINVALIDINTEGER, BigMathDIVIDEBYZERO,BigMathDomain};

const char *BigIntErrDes[] = { "Allocation Failed", "Overflow","Underflow", "Invalid Integer", "Divide by Zero" ,"Domain Error"};
const char BigIntPROGRAMNAME[] = { "BigInteger" };
const int BigIntMajorVersion = 6;
const int BigIntMinorVersion = 7;
const int BigIntRevision = 25;

void Dump(const char *,enum BigMathERROR);
string& DumpString (char const*,enum BigMathERROR);

// The Size Type
typedef unsigned int SizeT;
// The Data Type
typedef unsigned int DATATYPE;

// The Base Used
const DATATYPE BASE = 10000;
// An invalid data
const DATATYPE INVALIDDATA = 65535U;
// Number of digits in `BASE'
const SizeT LOG10BASE = 4;
class BigInteger
{
private:
// The integer array to hold the number
DATATYPE *TheNumber;
// Start of the location of the number in the array
SizeT Start;
// End of the location of the number in the array
SizeT End;
// True if the number is negative
bool isNegative;

// Constructor with specified bytes
BigInteger(SizeT,DATATYPE,bool);

// Copies data to 'this' upto size bytes
void datacopy(BigInteger const&,SizeT);

// Determines valid data range
SizeT datalen(DATATYPE const*) const;
// deallocates the array
void deallocateBigInteger();
// Trims zeros in front of a number
void TrimZeros();
// the array with the `fill' value
void Set(DATATYPE);

public:
// Default Constructor
BigInteger();
// Long integer constructor
BigInteger(long);
// Character array constructor
BigInteger(char const*);
// Copy Constructor
BigInteger(BigInteger const&);

// The Destructor
~BigInteger();

// Compares Two BigInteger values irrespective of sign
int UnsignedCompareTo(BigInteger const&)const;
// Compares Two BigInteger values
int CompareTo(BigInteger const&)const;

// Returns Number of digits in the BigInteger
SizeT Digits() const;
// Determines if the number representation is OK or not
bool isValidNumber() const;
// True is the nubmer is zero
bool isZero()const;

// Straight pen-pencil implementation for addition
BigInteger& Add(BigInteger const&) const;
// Straight pen-pencil implementation for subtraction
BigInteger& Subtract(BigInteger const&) const;
// Straight pen-pencil implementation for multiplication
BigInteger& Multiply(BigInteger const&) const;
BigInteger& Multiply(DATATYPE const&) const;
// Straight pen-pencil implementation for division and remainder
BigInteger& DivideAndRemainder(BigInteger const&,BigInteger&,bool) const;
BigInteger& DivideAndRemainder(DATATYPE const&,DATATYPE&,bool) const;

// Overloaded Binary Operators

// Adds Two BigInteger
friend BigInteger& operator+(BigInteger const&, BigInteger const&);
// Subtructs Two BigInteger
friend BigInteger& operator-(BigInteger const&, BigInteger const&);
// Multiplies Two BigInteger
friend BigInteger& operator*(BigInteger const&, BigInteger const&);
friend BigInteger& operator*(BigInteger const&, DATATYPE const&);
friend BigInteger& operator*(DATATYPE const&, BigInteger const&);
// Divides Two BigInteger
friend BigInteger& DivideAndRemainder(BigInteger const&, BigInteger const&,BigInteger&,bool);
friend BigInteger& DivideAndRemainder(BigInteger const&, DATATYPE const&,DATATYPE&,bool);
friend BigInteger& operator/(BigInteger const&, BigInteger const&);
friend BigInteger& operator/(BigInteger const&, DATATYPE const&);
friend BigInteger& operator/(DATATYPE const&, BigInteger const&);
// Modulo Division of Two BigInteger
friend BigInteger& operator%(BigInteger const&, BigInteger const&);
friend BigInteger& operator%(BigInteger const&, DATATYPE const&);
friend BigInteger& operator%(DATATYPE const&, BigInteger const&);

// Assignment Operator
BigInteger& operator=(BigInteger const&);

// Inserter
friend ostream& operator<<(ostream& , BigInteger const&);
// Extractor
friend istream& operator>>(istream& , BigInteger& );

// Overloaded Unary Operators

// Postfix Unary Increment
BigInteger& operator++();
// Prefix Unary Increment
BigInteger& operator++(int);

// Postfix Unary Decrement
BigInteger& operator--();
// Prefix Unary Decrement
BigInteger& operator--(int);

// Negation
BigInteger& operator-();

// Bit Wise Operators

// Left Shift
BigInteger& operator<<(SizeT);
// Right Shift
BigInteger& operator>>(SizeT);
// Returns the BigInteger absolute
void abs();
friend BigInteger& abs(BigInteger&);

// Conversion functions
string& toString() const;
int toInt();
long toLong();

// Others
BigInteger& Power(long )const;
BigInteger& SquareRoot() const;
};

// Private Constructor which provides a new BigInteger Object
// Filled with specified data
// Useful for internal operation
BigInteger::BigInteger(SizeT bytes,DATATYPE fill, bool toInit = true)
{
TheNumber = new DATATYPE[bytes];
isNegative = false;
Start = 0;
End = bytes - 1;

if(toInit) Set(fill);
}

// Default Constructor
BigInteger::BigInteger()
{
TheNumber = new DATATYPE[1];
TheNumber[0] = 0;
Start = 0;
End = 0;
isNegative = false;
}

// Long Constructor
BigInteger::BigInteger(long n)
{
if(n<0)
{
isNegative = true;
n *= -1;
}
else isNegative = false;

SizeT i = (SizeT)(floor(log10((double)n)/LOG10BASE) + 1);

Start = 0;
End = i-1;
TheNumber = new DATATYPE [i];
Set(0);

while(n)
{
TheNumber[--i] = n % BASE;
n /= BASE;
}
TrimZeros();
}

// Character array constructor
BigInteger::BigInteger(char const* n)
{
if(n[0]=='-') { isNegative = true; n++; }
else if(n[0]=='+') { isNegative = false; n++; }
else isNegative = false;

while(*n=='0') n++;

int l = strlen(n);
if(l==0)
{
*this = *new BigInteger();
return;
}
Start = 0;
End = (SizeT)(l/LOG10BASE + l%LOG10BASE - 1);
TheNumber = new DATATYPE [Digits()];
Set(0);

int cur = l - 1;
for(SizeT i = End; i>=Start;i--)
{
if(cur<0) break;
DATATYPE r = 0;
DATATYPE TEN = 1;
for(l=0;l<4;l++)
{
if(cur<0) break;
r = r + TEN*(n[cur]-'0');
TEN *= 10;
cur--;
}
TheNumber[i] = r;
}
TrimZeros();
if(isZero()) isNegative = false;
}

// Copy constructor
BigInteger::BigInteger(BigInteger const& Temp)
{
Start = 0;
End = Temp.Digits() - 1;
TheNumber = new DATATYPE [Temp.Digits()];

datacopy(Temp,Temp.Digits());
isNegative = Temp.isNegative;
}

// Deallocates the array
void BigInteger::deallocateBigInteger()
{
if(TheNumber!=0)
{
delete [] TheNumber;
TheNumber = 0;
}
}

// The Destructor
BigInteger::~BigInteger()
{
deallocateBigInteger();
Start = 0;
End = 0;
}

// Sets the array with the `fill' value
void BigInteger::Set(DATATYPE fill)
{
for(SizeT i=Start;i<=End;i++)
TheNumber[i] = fill;
}

// Copies data from `a' to `this'
void BigInteger::datacopy(BigInteger const& a,SizeT size)
{
for(SizeT i=0;i<size;i++)
TheNumber[Start+i] = a.TheNumber[a.Start+i];
}

// Determines the length upto valid data
SizeT BigInteger::datalen(DATATYPE const* a) const
{
SizeT l = 0;
while(a[l]!=INVALIDDATA) l++;
return l;
}

// Returns number of digits in a BigInteger
SizeT BigInteger::Digits() const
{ return End-Start+1; }

// true if 'this' is zero
bool BigInteger::isZero() const
{ return End==Start && TheNumber[Start]==0; }

// Checks for the validity of the number
bool BigInteger::isValidNumber() const
{
for(SizeT i=Start; i<End ; i++)
if(TheNumber[i]>=BASE) return false;

return true;
}

// Trims Leading Zeros
void BigInteger::TrimZeros()
{
while(TheNumber[Start]==0 && Start<End)
Start++;
}

// Compares this with `with' irrespective of sign
// Returns
// 0 if equal
// 1 if this>with
// -1 if this<with
int BigInteger::UnsignedCompareTo(BigInteger const& with)const
{
if(isZero() && with.isZero()) return 0;
if(!isZero() && with.isZero()) return 1;
if(isZero() && !with.isZero()) return -1;

long temp = Digits() - with.Digits();
// Case 3: First One got more digits
// Case 4: First One got less digits
if(temp!=0) return temp<0?-1:1;

// Now I know Both have same number of digits
// Case 5,6,7:
/*
Compares two array of data considering the
case that both of them have the same number
of digits
*/

temp = 0;
int cmp = 0;
for(SizeT i=0;i<Digits();i++)
{
temp = TheNumber[i+Start] - with.TheNumber[i+with.Start];
if(temp!=0)
{
cmp = temp<0?-1:1;
break;
}
}

return cmp;
}

// Compares this with `with'
// Returns
// 0 if equal
// 1 if this>with
// -1 if this<with
int BigInteger::CompareTo(BigInteger const& with)const
{
int cmp = UnsignedCompareTo(with);

// Case 1: Positive , Negative
if(isNegative==false && with.isNegative==true) return 1;
// Case 2: Negative, Positive
if(isNegative==true && with.isNegative==false) return -1;
// Now, Both are Same Sign
int both_neg = 1;
if(isNegative==true && with.isNegative==true) both_neg = -1;
return cmp*both_neg;
}

// Implentation of addition by paper-pencil method
BigInteger& BigInteger::Add(BigInteger const& Small) const
{
BigInteger const& Big = *this;
BigInteger &Result= *new BigInteger(Big.Digits()+1,0);

long Carry=0,Plus;
long i=Big.Digits() - 1,
j=Small.Digits() -1;

for(; i>=0 ;i--,j--){
Plus = Big.TheNumber[i+Big.Start] + Carry;
if(j>=0) Plus += Small.TheNumber[j+Small.Start] ;

Result.TheNumber[i+1] = Plus%BASE;
Carry = Plus/BASE;
}
i++;

if(Carry) Result.TheNumber[i--] = Carry;

Result.TrimZeros();

return Result;
}

// Implentation of subtraction by paper-pencil method
BigInteger& BigInteger::Subtract(BigInteger const& Small)const
{
BigInteger const& Big = *this;
BigInteger& Result = *new BigInteger(Big.Digits()+1,0);

long Carry=0,Minus;

long i = Big.Digits() - 1,
j= Small.Digits() - 1;

for( ; i>=0 ;i--,j--)
{
Minus = Big.TheNumber[i+Big.Start] - Carry;
if(j>=0) Minus -= Small.TheNumber[j+Small.Start];

if(Minus < 0)
{
Result.TheNumber[i+1] = Minus + BASE;
Carry = 1;
}
else
{
Result.TheNumber[i+1] = Minus;
Carry = 0;
}
}
Result.TrimZeros();
return Result;
}

// Addition operator
BigInteger& operator+(BigInteger const& N1, BigInteger const& N2)
{
if(N1.isNegative && !N2.isNegative)
{
// First is negaive and second is not
BigInteger& Res = *new BigInteger(N1);
Res.isNegative = false;
Res = N2-Res;
return Res;
}
if(!N1.isNegative && N2.isNegative)
{
// Second is negaive and first is not
BigInteger& Res = *new BigInteger(N2);
Res.isNegative = false;
Res = N1-Res;
return Res;
}

BigInteger& ret = *new BigInteger();

if(N1.UnsignedCompareTo(N2)<0)
ret = N2.Add(N1);
else
ret = N1.Add(N2);
if(N1.isNegative==true && N2.isNegative==true)
ret.isNegative = true;
return ret;
}

// Subtruction operator
BigInteger& operator-(BigInteger const& N1, BigInteger const& N2)
{
if(N1.isNegative && !N2.isNegative)
{
BigInteger& res = *new BigInteger(N1);
res.isNegative = false;
res = res+N2;
res.isNegative = true;
return res;
}
if(!N1.isNegative && N2.isNegative)
{
BigInteger& res = *new BigInteger(N2);
res.isNegative = false;
res = res+N1;
return res;
}

BigInteger& ret = *new BigInteger();
int cmp = N1.UnsignedCompareTo(N2);
if(cmp==0)
{
ret = *new BigInteger();
}
if(cmp<0)
{
ret = N2.Subtract(N1);
ret.isNegative = true;
}
else
{
ret = N1.Subtract(N2);
ret.isNegative = false;
}
return ret;
}

// Implentation of multiplication by paper-pencil method
BigInteger& BigInteger::Multiply(BigInteger const& Small) const
{
BigInteger const& Big = *this;
BigInteger& Result = *new BigInteger(Big.Digits()+Small.Digits(),0);

long Carry,Multiply;

SizeT i;
SizeT j;

for(i = 0 ; i< Small.Digits() ; i++)
{
Carry = 0;
for(j = 0 ; j< Big.Digits() ; j++)
{
Multiply = ( (long)Small.TheNumber[Small.End-i] * (long)Big.TheNumber[Big.End-j] )
+ Carry + Result.TheNumber[Result.End-i-j];
Result.TheNumber[Result.End-i-j] = Multiply%BASE;
Carry = Multiply/BASE ;
}
Result.TheNumber[Result.End-i-j] = Carry;
}

Result.TrimZeros();

return Result;
}

// Implentation of multiplication by paper-pencil method
// See: D. E. Knuth 4.3.1
BigInteger& BigInteger::Multiply(DATATYPE const& with) const
{
BigInteger& Result = *new BigInteger(Digits()+1,0);

long Carry,Multiply;

SizeT i;

Carry = 0;
for(i = 0 ; i< Digits() ; i++)
{
Multiply = Carry + (long)TheNumber[End-i] * (long)with;
Carry = Multiply / BASE;
Result.TheNumber[Result.End-i] = Multiply % BASE;
}
Result.TheNumber[Result.End-i] = Carry;
Result.TrimZeros();

return Result;
}

// Multiplication operator
BigInteger& operator*(BigInteger const& N1, BigInteger const& N2)
{
if(N1.isZero() || N2.isZero()) return *new BigInteger();
BigInteger& ret = *new BigInteger();
if(N1.UnsignedCompareTo(N2)<0)
ret = N2.Multiply(N1);
else
ret = N1.Multiply(N2);
if(N1.isNegative!=N2.isNegative)
ret. isNegative = true;
return ret;
}

// Multiplication operator
BigInteger& operator*(BigInteger const& N1, DATATYPE const& N2)
{
if(N1.isZero() || N2==0) return *new BigInteger();
BigInteger& ret = N1.Multiply(N2);
// if(N1.isNegative!=(N2<0)) ret. isNegative = true;
return ret;
}

// Multiplication operator
BigInteger& operator*(DATATYPE const& N1, BigInteger const& N2)
{
if(N2.isZero() || N1==0) return *new BigInteger();
BigInteger& ret = N2.Multiply(N1);
// if(N2.isNegative!=(N1<0)) ret. isNegative = true;
return ret;
}

// Implentation of division by paper-pencil method
// Here `this' is divided by 'V'
BigInteger& BigInteger::DivideAndRemainder(DATATYPE const& V,DATATYPE& _R,bool skipRemainder=false) const
{
BigInteger& W = *new BigInteger(Digits(),0,false);
DATATYPE R = 0;
SizeT j;
for(j=0;j<=End;j++)
{
W.TheNumber[j] = (R*BASE+TheNumber[Start+j])/V;
R = (R*BASE+TheNumber[Start+j])%V;
}

W.TrimZeros();
if(skipRemainder==false)
_R = R;

return W;
}

// Implentation of division by paper-pencil method
// Does not perform the validity and sign check
// It is assumed that this > `_V'
// See: D.E.Knuth 4.3.1
BigInteger& BigInteger::DivideAndRemainder(BigInteger const& _V,BigInteger& R,bool skipRemainder=false) const
{
SizeT m = this->Digits()-_V.Digits();
SizeT n = _V.Digits();
BigInteger& Q = *new BigInteger(m+1,0,false);

DATATYPE d, qhat, rhat;
long temp,x,y;
SizeT i;
int j;

d = (BASE-1)/_V.TheNumber[_V.Start];

BigInteger& U = this->Multiply(d);
BigInteger& V = _V.Multiply(d);

for(j = m; j>=0; j--)
{
temp = (long)U.TheNumber[U.End-j-n]*(long)BASE + (long)U.TheNumber[U.End-j-n+1];
x = temp / (long)V.TheNumber[V.Start];
y = temp % (long)V.TheNumber[V.Start];
if(x>(long)BASE) x /= BASE;
if(y>(long)BASE) y %= BASE;
qhat = (DATATYPE) x;
rhat = (DATATYPE) y;

bool badRhat = false;
do
{
x = (long)qhat * (long)V.TheNumber[V.Start+1];
y = (long)BASE*(long)rhat + (long)U.TheNumber[U.End-j-n+1];

if(qhat==BASE || x > y)
{
qhat --;
rhat += V.TheNumber[V.Start];
if(rhat<BASE) badRhat = true;
else badRhat = false;
}
else break;
}while(badRhat);

// `x' Will act as Carry in the next loop
x = 0;
temp = 0;
for(i=0;i<=n;i++)
{
if(V.End>=i) temp = (long)qhat*(long)V.TheNumber[V.End-i] + temp;
y = (long)U.TheNumber[U.End-j-i] - temp%BASE - x;
temp /= BASE;
if(y < 0)
{
U.TheNumber[U.End-j-i] = (DATATYPE)(y+BASE);
x = 1;
}
else
{
U.TheNumber[U.End-j-i] = (DATATYPE)y;
x = 0;
}
}
// if(x) U.TheNumber[U.Start+j+i] --;

Q.TheNumber[Q.End-j] = qhat;

if(x)
{
Q.TheNumber[Q.End-j] --;
// `x' Will act as Carry in the next loop
x = 0;
for(i=0;i<=n;i++)
{
y = (long)U.TheNumber[U.End-j-i] + x;
if(V.End>=i) y += (long)V.TheNumber[V.End-i];
U.TheNumber[U.End-j-i] = (DATATYPE)(y % BASE);
x = y / BASE;
}
U.TheNumber[U.End-j-i] = (DATATYPE)x;
}
}

U.TrimZeros();
DATATYPE _t;
if(skipRemainder==false)
R = U.DivideAndRemainder(d,_t,true);
Q.TrimZeros();

return Q;
}

// Front end for Divide and Remainder
// Performs the validity and sign check
BigInteger& DivideAndRemainder(BigInteger const& U, BigInteger const& V,BigInteger& R,bool skipRemainder=false)
{
if(V.isZero())
throw logic_error (DumpString ("DivideAndRemainder (BigInteger/BigInteger)",BigMathDIVIDEBYZERO));

if(U.isZero())
{
R = *new BigInteger();
return *new BigInteger();
}

int cmp = U.UnsignedCompareTo(V);
if(cmp==0)
{
R = *new BigInteger();
BigInteger& W = *new BigInteger(1l);
if(U.isNegative!=V.isNegative) W.isNegative = true;
return W;
}
else if(cmp<0)
{
R = *new BigInteger(U);
if(U.isNegative!=V.isNegative) R.isNegative = true;
return *new BigInteger();
}
BigInteger& ret = U.DivideAndRemainder(V,R,skipRemainder);
if(U.isNegative!=V.isNegative) ret.isNegative = true;
return ret;
}

// Front end for Divide and Remainder
// Performs the validity and sign check
BigInteger& DivideAndRemainder(BigInteger const& U, DATATYPE const& V,DATATYPE& R,bool skipRemainder=false)
{
if(V==0)
throw logic_error ( DumpString ("DivideAndRemainder (BigInteger/DATATYPE)",BigMathDIVIDEBYZERO) );

if(U.isZero())
{
R = 0;
return *new BigInteger();
}

int cmp = 1;
if(U.Digits()==1)
{
if(U.TheNumber[U.Start]<V) cmp = -1;
else if(U.TheNumber[U.Start]>V) cmp = 1;
else cmp = 0;
}
if(cmp==0)
{
R = 0;
return *new BigInteger(1l);
}
else if(cmp<0)
{
R = U.TheNumber[U.Start];
return *new BigInteger();
}
BigInteger& ret = U.DivideAndRemainder(V,R,skipRemainder);
// if(U.isNegative!=(V<0)) ret.isNegative = true;
return ret;
}

// Division operator
BigInteger& operator/(BigInteger const& N1, BigInteger const& N2)
{
BigInteger& R = *new BigInteger();
return DivideAndRemainder(N1,N2,R,true);
}

// Division operator
BigInteger& operator/(BigInteger const& U, DATATYPE const& V)
{
DATATYPE R;
return DivideAndRemainder(U,V,R,true);
}

// Division operator
BigInteger& operator/(DATATYPE const& U, BigInteger const& V)
{
if(V.Digits()==1 && U>V.TheNumber[V.Start])
{
return *new BigInteger(U/V.TheNumber[V.Start]);
}
return *new BigInteger();
}

// Modulus operator
BigInteger& operator%(BigInteger const& N1,BigInteger const& N2)
{
BigInteger& R = *new BigInteger();
DivideAndRemainder(N1,N2,R);
return R;
}

// Modulus operator
BigInteger& operator%(BigInteger const& U, DATATYPE const& V)
{
DATATYPE R;
DivideAndRemainder(U,V,R);
return *new BigInteger(R);
}

// Modulus operator
BigInteger& operator%(DATATYPE const& U, BigInteger const& V)
{
if(V.Digits()==1 && U>V.TheNumber[V.Start])
{
return *new BigInteger(U%V.TheNumber[V.Start]);
}
return *new BigInteger();
}

// Assignment Operator
BigInteger& BigInteger::operator=(BigInteger const&arg)
{
Start = 0;
End = arg.Digits() - 1;
delete [] TheNumber;
TheNumber = new DATATYPE [arg.Digits()];

datacopy(arg,arg.Digits());
isNegative = arg.isNegative;
return *this;
}

// Inserter
ostream& operator<<(ostream& stream, BigInteger const& out)
{
if(out.isNegative==true && out.isZero()==false) stream << '-';
stream << out.TheNumber[out.Start];
for(SizeT i=out.Start+1;i<=out.End;i++)
{
stream.width(4);
stream.fill('0');
stream << out.TheNumber[i];
}

return stream;
}

// Extracter
istream& operator>>(istream& stream, BigInteger& in)
{
SizeT SIZE = 500;
char *data = new char[SIZE];
// if(data==0) Dump("Extractor operator",BigMathMEM);
SizeT i = 0;
int input;
bool isNegative = false;
stream >> ws;
input = stream.get();
if(input=='-') isNegative = true;
else if(input=='+') isNegative = false;
else stream.putback(input);

while(true)
{
input = stream.get();
if(isdigit(input))
data[i++] = input;
else
{
stream.putback(input);
break;
}
if(i>=SIZE)
{
SIZE += SIZE;
char *p = new char [SIZE];
// if(p==0) Dump("Extractor operator",BigMathMEM);
strcpy(p,data);
delete [] data;
data = p;
}
}
data[i] = 0;
in = *new BigInteger(data);
if(in.isZero()==false)
in.isNegative = isNegative;
return stream;
}

// Inserts the version information into the output stream
ostream& BigIntegerVersion(ostream& out)
{
out << BigIntPROGRAMNAME << " (Version "<< BigIntMajorVersion
<< "." << BigIntMinorVersion << "." << BigIntRevision << ")";
return out;
}

// Inserts the author information into the output stream
ostream& BigIntegerAuthor(ostream& out)
{
out << "Author: S. M. Mahbub Murshed" <<
endl << "mailto: suman@bttb.net.bd";
return out;
}

// Inserts the about information into the output stream
ostream& BigIntegerAbout(ostream& out)
{
out << BigIntegerVersion << endl << BigIntegerAuthor << endl;
return out;
}

// Returns a string containing version information
string& BigIntegerVersionString()
{
char out[100];
ostrstream str(out,sizeof(out));
str << BigIntegerVersion;
return *new string(out);
}

// Converts `this' to a string representation
string& BigInteger::toString()const
{
const int DIGITS = Digits()*4;
char *R = new char[DIGITS+2];
ostrstream ostr(R,DIGITS);
ostr << *this;
return *new string(R);
}

// Converts `this' to equivalent int value
int BigInteger::toInt()
{
return (int)toLong();
}

// Converts `this' to equivalent 32 bit long value
long BigInteger::toLong()
{
long r = TheNumber[End];
if(Digits()>1) r += BASE * TheNumber[End-1] ;
if(Digits()>2) r += BASE*BASE*(TheNumber[End-2]%100);
return r;
}

// Postfix Increment , that is *this++
BigInteger& BigInteger::operator++()
{
BigInteger& ONE = *new BigInteger(1l);
*this = *this+ONE;
return *this;
}

// Prefix Increment , that is ++*this
BigInteger& BigInteger::operator++(int notused)
{
BigInteger one(1l);
BigInteger& Ret = *new BigInteger(*this);
*this = *this+one;
return Ret;
}

// Postfix Decrement , that is *this--
BigInteger& BigInteger::operator--()
{
BigInteger one(1l);
*this = *this-one;
return *this;
}

// Pretfix Increment , that is --*this
BigInteger& BigInteger::operator--(int notused)
{
BigInteger one(1l);
BigInteger& Ret = *new BigInteger(*this);
*this = *this-one;
return Ret;
}

// Negation, returns -*this
BigInteger& BigInteger::operator-()
{
this->isNegative = this->isNegative==true?false:true;
return *this;
}

// Left Shift
// To be checked
BigInteger& BigInteger::operator<<(SizeT b)
{
SizeT i = (SizeT)(b / LOG10BASE);
b %= LOG10BASE;
while(b--) TheNumber[Digits()-1] *= 10;

if(i>0)
{
DATATYPE *temp = new DATATYPE[Digits()+i];
for(b=0;b<Digits();b++)
temp[b] = TheNumber[b];
for(b=0;b<i; b++)
temp[Digits()+b] = 0;
delete [] TheNumber;
TheNumber = temp;
End += i-1;
}
return *this;
}

// Right Shift
BigInteger& BigInteger::operator>>(SizeT b)
{
SizeT i = (SizeT)(b / LOG10BASE);
b %= LOG10BASE;
End -= i;
while(b--)
{
DATATYPE f = 0,l = 0;
for(i=Start;i<=End;i++)
{
l = TheNumber[i]%10;
TheNumber[i] = f*BASE + TheNumber[i]/10;
f = l;
}
if(TheNumber[Start]==0)
Start--;
}
return *this;
}

// Makes `this' BigInteger value to absolute
void BigInteger::abs()
{ isNegative = false; }

// Returns new BigInteger value which is absolute
// copy of `arg'
BigInteger& abs(BigInteger& arg)
{
BigInteger& ret = *new BigInteger(arg);
ret.isNegative = false;
return ret;
}

// Power BigInteger to the power Long
BigInteger& BigInteger::Power(long y) const
{
long P;
BigInteger& pow = *new BigInteger(1l);
BigInteger& z = *new BigInteger();
BigInteger& ZERO = *new BigInteger();
BigInteger& ONE = *new BigInteger(1l);
P = y;

if(y==0) return pow;
if(isZero()) return ZERO;
if(UnsignedCompareTo(ONE)==0) return ONE;

z = *this;
while(P>0)
{
while(P%2==0)
{
P /= 2;
z = z*z;
}
P--;
pow = pow*z;
}
return pow;
}

void Dump(char const* s,enum BigMathERROR e)
{
cerr << BigIntegerVersion << endl;
cerr << "Exception: " << BigIntErrDes[e-1] << endl;
cerr << "In function: " << s << endl;
cerr << "Error Code: " << e << endl;
exit(e);
}

string& DumpString (char const* s,enum BigMathERROR e)
{
char *R = new char[256];
ostrstream ostr(R,255);
ostr << BigIntegerVersion << endl;
ostr << "Exception: " << BigIntErrDes[e-1] << endl;
ostr << "In function: " << s << endl;
ostr << "Error Code: " << e << endl;
return *new string(R);
}

BigInteger& BigInteger::SquareRoot() const
{
BigInteger const& n = *this;
BigInteger& _2 = *new BigInteger(2l);
BigInteger& zero = *new BigInteger();
if(n.isZero())
return zero;

if(n.isNegative)
throw domain_error ( DumpString ("Square Root",BigMathDomain) );

long Dig;
if(n.Digits()%2==0)
Dig = n.Digits()/2 - 1;
else
Dig = n.Digits()/2 ;

BigInteger& sq = *new BigInteger(1l);
if(Dig==-1)
return sq;

BigInteger sqr,toIncrease,temp;
sq = sq << Dig;
toIncrease = sq;

while(true)
{
sqr = sq*sq;
if(sqr.CompareTo(n) == 0) break;
if(toIncrease.CompareTo(zero)==0) break;
if(sqr.CompareTo(n) > 0)
{
toIncrease = toIncrease/_2;
sq = temp;
}

temp = sq;
sq = sq + toIncrease;
}
return sq;
}

bool operator==(BigInteger const& a, BigInteger const& b)
{ return a.CompareTo(b)==0; }

bool operator!=(BigInteger const& a, BigInteger const& b)
{ return a.CompareTo(b)!=0; }

bool operator>=(BigInteger const& a, BigInteger const& b)
{ return a.CompareTo(b)>=0; }

bool operator<=(BigInteger const& a, BigInteger const& b)
{ return a.CompareTo(b)<=0; }

bool operator>(BigInteger const& a, BigInteger const& b)
{ return a.CompareTo(b)>0; }

bool operator<(BigInteger const& a, BigInteger const& b)
{ return a.CompareTo(b)<0; }
}
----
[[경시대회준비반]]

경시대회준비반/BigInteger - Revision history

Maintenance script: Repair batch-0004 pages from live compare

imported>Unknown at 05:28, 7 February 2021