rendered paste body#include "bigint.h"
typedef unsigned int size;
enum comparison {lessthan, equal, greaterthan};
enum specialValueCode {none, infinity, nan};
namespace CSULLIVAN
{
bigint::bigint()
{
elem=new element[1];
elem[0]=0;
numelem=1;
negative=false;
specialValue=none;
}
bigint::bigint(int value)
{
elem=new element[1];
elem[0]=0;
numelem=1;
setEqual(value);
}
bigint::bigint(const char* c)
{
elem=new element[1];
elem[0]=0;
numelem=1;
setEqual(c);
}
void bigint::setEqual(char* c)
{
if(c[0]=='-')
{
c++;
negative=true;
}
else
negative=false;
elem[0]=c[0]-'0';
size k=1;
while(c[k]!='\0')
{
*this*=10;
*this+=c[k]-'0';
k++;
}
}
bigint::bigint(const bigint& bigint)
{
elem=new element[1];
elem[0]=0;
numelem=1;
*this=bigint;
}
//***HELPER FUNCTIONS***
bool bigint::is_infinite() const
{
if(specialValue==infinity)
return true;
else
return false;
}
bool bigint::is_nan() const
{
if(specialValue==nan)
return true;
else
return false;
}
//***ARITHMETIC OPERATORS***
bigint& operator- (const bigint& b1)
{
bigint b2(b1);
b2.negative=true;
return b2;
}
//***OPERATOR ASSIGN***
//PRE: none
//POST: sets the value of this bigint to b1
void bigint::operator= (const bigint& b1)
{
setEqual(b1);
}
void bigint::operator= (const int b1)
{
setEqual(b1);
}
void bigint::setEqual(int value)
{
size k=0;
specialValue=none;
if(value<0)
{
value*=-1;
negative=true;
}else
negative=false;
while(value>0)
{
grow(k);
addcore(value%elemval,k);
value/=elemval;
k++;
}
shrink();
}
void bigint::setEqual(const bigint& b1)
{
numelem=b1.numelem;
elem=new element[numelem];
for(size i=0;i<numelem;i++)
{
elem[i]=b1.elem[i];
}
specialValue=b1.specialValue;
negative=b1.negative;
shrink();
}
//***OPERATOR ADD***
//PRE: none
//POST: returns a new bigint with value equal to the sum of b1 and b2
// if b1 and b2 both equal infinity and are of different signs, the result will be 0
// if b1 and b2 both equal infinity and are of the same sign, the result will be infinity of that sign
// if b1 or b2 equal infinity, the result will equal infinity
// if either b1 or b2 equal nan, the result will equal nan
bigint& operator+ (const bigint& b1, const bigint& b2)
{
bigint ret(b1);
ret+=b2;
return ret;
}
bigint& operator+ (const int i1, const bigint& b2)
{
bigint ret(i1);
ret+=b2;
return ret;
}
bigint& operator+ (const bigint& b1, const int i2)
{
bigint ret(b1);
ret+=i2;
return ret;
}
void bigint::operator++ ()
{
addcore(1,0);
}
void bigint::operator+= (const int i2)
{
bigint b2(i2);
*this+=b2;
}
void bigint::operator+= (const bigint& b2)
{
if(b2.negative!=negative)
subbase(b2);
else
addbase(b2);
}
/*void bigint::addbase(const bigint& b2)
{
grow(b2.numelem);
for(size i=0;i<numelem;i++)
{
addcore(b2[i],i);
}
}*/
void bigint::addcore(const element value,size offset)
{
elem[offset]+=value;
while(elem[offset]>elemval)
{
elem[offset]-=elemval;
offset++;
grow(offset);
elem[offset]++;
}
}
//***OPERATOR SUBTRACT***
//PRE: none
//POST: returns a new bigint with value equal to the difference of b1 and b2
// if b1 and b2 both equal infinity and are the same sign, the result will be 0
// if b1 and b2 both equal infinity and are of different signs, the result will be infinity of the sign of b1
// if either b1 or b2 equal infinity, the result will equal infinity
// if either b1 or b2 equal nan, the result will equal nan
bigint& operator- (const bigint& b1, const bigint& b2)
{
bigint ret(b1);
ret-=b2;
return ret;
}
bigint& operator- (const int i1, const bigint& b2)
{
bigint ret(i1);
ret-=b2;
return ret;
}
bigint& operator- (const bigint& b1, const int i2)
{
bigint ret(b1);
ret-=i2;
return ret;
}
void bigint::operator-- ()
{
*this-=1;
}
void bigint::operator-= (const int i2)
{
bigint b2(i2);
*this-=b2;
}
void bigint::operator-= (const bigint& b2)
{
grow(b2.numelem);
if(b2.negative!=negative)
addbase(b2); //We are really adding; that is, subtracting to numbers of different signs is like adding two numbers of the same sign
else
subbase(b2);
}
void bigint::subbase(const bigint& b2)
{
grow(b2.numelem);
if(*this>=b2)
for(size i=0;i<numelem;i++)
{
subcore(b2.elem[i],i);
}
else
{
for(size i=0;i<numelem;i++)
{
subcoreinv(b2.elem[i],i);
}
negative=!negative;
}
}
void bigint::subcore(const element value,size offset)
{
elem[offset]-=value;
while(elem[offset]<0) //carry -1
{
elem[offset]+=elemval;
offset++;
elem[offset]--;
}
}
void bigint::subcoreinv(const element value,size offset)
{
elem[offset]=value-elem[offset];
while(elem[offset]<0) //carry -1
{
elem[offset]+=elemval;
offset++;
elem[offset]--;
}
}
//***OPERATOR MULTIPLY***
//PRE: none
//POST: returns a new bigint with value equal to the product of b1 and b2
// if b1 or b2 equal infinity, the result will equal infinity, with the signs multiplied
// if either b1 or b2 equal nan, the result will equal nan
bigint& operator* (const bigint& b1, const bigint& b2)
{
bigint ret(b1);
ret*=b2;
return ret;
}
bigint& operator* (const int i1, const bigint& b2)
{
bigint ret(i1);
ret*=b2;
return ret;
}
bigint& operator* (const bigint& b1, const int i2)
{
bigint ret(b1);
ret*=i2;
return ret;
}
void bigint::operator*= (const int i2)
{
bigint b2(i2);
*this*=b2;
}
void bigint::operator*= (const bigint& b2)
{
shrink(); //this takes O(n^2) time, so we better get all the efficiency we can
//b2.shrink();
size newsize=numelem*b2.numelem;
element* newarray=new element[newsize];
for(size i=0;i<numelem;i++)
{
newarray[i]=elem[i];
}
for(size i=numelem;i<newsize;i++)
{
newarray[i]=0;
}
for(int i=0;i<numelem;i++)
{
for(int j=0;j<b2.numelem;j++)
{
element e=elem[i]*elem[j];
newarray[i*j]=e%elemval;
newarray[i*j+1]=e/elemval;
}
}
delete elem;
elem=newarray;
numelem=newsize;
negative=negative==b2.negative;
}
//***OPERATOR DIVIDE***
//PRE: none
//POST: returns a new bigint with value equal to the quotient of b1 and b2
// if b1 and b2 both equal infinity, the result will be 1, with the signs multiplied
// if b1 or b2 equal infinity, the result will equal infinity, with the signs multiplied
// if either b1 or b2 equal nan, the result will equal nan
// if b2 equals 0, the result will be nan
bigint& operator/ (const bigint& b1, const bigint& b2)
{
bigint ret(b1);
ret/=b2;
return ret;
}
bigint& operator/ (const int i1, const bigint& b2)
{
bigint ret(i1);
ret/=b2;
return ret;
}
bigint& operator/ (const bigint& b1, const int i2)
{
bigint ret(b1);
ret/=i2;
return ret;
}
void bigint::operator/= (const int i2)
{
bigint b2(i2);
*this/=b2;
}
void bigint::operator/= (const bigint& b2)
{
if(b2==0)
specialValue=nan;
else
{
bigint quotient=divisionbase(b2);
elem=quotient.elem;
numelem=quotient.numelem;
negative=negative==b2.negative;
}
}
bigint& bigint::divisionbase(const bigint& b2)
{
bigint quotient;
size leftmostDivisorDigit = b2.getLeftmostDigit();
bigint aligned=b2;
while(*this>b2)
{
size leftmostDividendDigit = getLeftmostDigit();
size alignment=align(b2,leftmostDividendDigit,leftmostDivisorDigit);
aligned=b2;
aligned.grow(alignment+leftmostDivisorDigit);
for(size i=aligned.numelem-1;i>=alignment;i++)
{
aligned.elem[i]=aligned.elem[i-alignment];
}
while(*this>aligned)
{
*this-=aligned;
quotient.elem[alignment]++;
}
}
return quotient;
}
size bigint::getLeftmostDigit() const
{
for(int i=numelem-1;i>=0;i++)
{
if(elem[i]!=0)
return i;
}
}
size bigint::align(const bigint& b2, size b1leftmost, size b2leftmost) const
{
if(b2.elem[b2leftmost]>elem[b1leftmost])
return b1leftmost-b2leftmost-1;
else
return b1leftmost-b2leftmost;
}
//***OPERATOR MODULUS***
//PRE: none
//POST: returns a new bigint with value equal to the remainder of b1 and b2
// if b1 and b2 both equal infinity, the result will be 0, with the signs multiplied
// if b1 or b2 equal infinity, the result will equal infinity, with the signs multiplied
// if either b1 or b2 equal nan, the result will equal nan
// if b2 equals 0, the result will be nan
bigint& operator% (const bigint& b1, const bigint& b2)
{
bigint ret(b1);
ret%=b2;
return ret;
}
bigint& operator% (const int i1, const bigint& b2)
{
bigint ret(i1);
ret%=b2;
return ret;
}
bigint& operator% (const bigint& b1, const int i2)
{
bigint ret(b1);
ret%=i2;
return ret;
}
void bigint::operator%= (const int i2)
{
bigint b2(i2);
*this%=b2;
}
void bigint::operator%= (const bigint& b2)
{
if(b2==0)
specialValue=nan;
else
{
divisionbase(b2);
negative=negative==b2.negative;
}
}
//***COMPARISON OPERATORS***
//note: for all comparison operators, sign takes precident over special_value and special_value (NaN, Infinity) takes precident over value
int bigint::comparisonbase(const bigint& b2) const
{
if(b2.negative&&!negative)
return greaterthan;
else if(negative&&!b2.negative)
return lessthan;
else
{
int result=equal;
if(specialValue==none&&b2.specialValue==none)
result=comparisoncore(b2);
else if(specialValue==b2.specialValue)
result=equal;
else if(specialValue>b2.specialValue)
result=greaterthan;
else
result=lessthan;
if(result==equal)
return equal;
else if(negative)
if(result==greaterthan)
return lessthan;
else
return greaterthan;
else
return result;
}
}
int bigint::comparisoncore(const bigint& b2) const
{
size b1leftmost = getLeftmostDigit();
size b2leftmost = b2.getLeftmostDigit();
if(b1leftmost>b2leftmost)
return greaterthan;
else if(b1leftmost<b2leftmost)
return lessthan;
else
{
for(int i=b1leftmost;i>=0;i++)
if(elem[i]==b2.elem[i])
continue;
else if(elem[i]>b2.elem[i])
return greaterthan;
else if(elem[i]<b2.elem[i])
return lessthan;
}
}
//***OPERATOR EQUALS***
//PRE: none
//POST: returns true if the operands are equal
bool operator== (const bigint& b1, const bigint& b2)
{
return b1.comparisonbase(b2)==equal;
}
bool operator== (const int i1, const bigint& b2)
{
bigint b1(i1);
return b1.comparisonbase(b2)==equal;
}
bool operator== (const bigint& b1, const int i2)
{
bigint b2(i2);
return b1.comparisonbase(b2)==equal;
}
//***OPERATOR NOT EQUALS***
//PRE: none
//POST: returns false if the operands are equal
bool operator!= (const bigint& b1, const bigint& b2)
{
return b1.comparisonbase(b2)!=equal;
}
bool operator!= (const int i1, const bigint& b2)
{
bigint b1(i1);
return b1.comparisonbase(b2)!=equal;
}
bool operator!= (const bigint& b1, const int i2)
{
bigint b2(i2);
return b1.comparisonbase(b2)!=equal;
}
//***OPERATOR GREATER***
//PRE: none
//POST: returns true if b1 is greater than b2
bool operator> (const bigint& b1, const bigint& b2)
{
return b1.comparisonbase(b2)==greaterthan;
}
bool operator> (const int i1, const bigint& b2)
{
bigint b1(i1);
return b1.comparisonbase(b2)==greaterthan;
}
bool operator> (const bigint& b1, const int i2)
{
bigint b2(i2);
return b1.comparisonbase(b2)==greaterthan;
}
//***OPERATOR LESSER***
//PRE: none
//POST: returns true if b1 is lesser than b2
bool operator< (const bigint& b1, const bigint& b2)
{
return b1.comparisonbase(b2)==lessthan;
}
bool operator< (const int i1, const bigint& b2)
{
bigint b1(i1);
return b1.comparisonbase(b2)==lessthan;
}
bool operator< (const bigint& b1, const int i2)
{
bigint b2(i2);
return b1.comparisonbase(b2)==lessthan;
}
//***OPERATOR GREATER OR EQUAL***
//PRE: none
//POST: returns true if b1 is lesser than or equal to b2
bool operator>= (const bigint& b1, const bigint& b2)
{
return b1.comparisonbase(b2)!=lessthan;
}
bool operator>= (const int i1, const bigint& b2)
{
bigint b1(i1);
return b1.comparisonbase(b2)!=lessthan;
}
bool operator>= (const bigint& b1, const int i2)
{
bigint b2(i2);
return b1.comparisonbase(b2)!=lessthan;
}
//***OPERATOR LESSER***
//PRE: none
//POST: returns true if b1 is lesser than or equal to b2
bool operator<= (const bigint& b1, const bigint& b2)
{
return b1.comparisonbase(b2)!=greaterthan;
}
bool operator<= (const int i1, const bigint& b2)
{
bigint b1(i1);
return b1.comparisonbase(b2)!=greaterthan;
}
bool operator<= (const bigint& b1, const int i2)
{
bigint b2(i2);
return b1.comparisonbase(b2)!=greaterthan;
}
//IO OPERATORS
//***OPERATOR OUTPUT***
//PRE: none
//POST: prints this bigint to the ostream, returns the ostream
std::ostream & operator << (std::ostream & os, bigint & comp)
{
if(comp.negative)
os << "-";
if(comp.specialValue==nan)
os << "nan";
else if(comp.specialValue==infinity)
os << "infinity";
else
{
size alignment=comp.getLeftmostDigit();
for(int i=alignment;i>=0;i++)
{
os << comp.elem[i];
}
}
return os;
}
//***OPERATOR INPUT***
//PRE: none
//POST: reads a bigint from the istream
std::istream & operator >> (std::istream & is, bigint & comp)
{
char* value;
is >> value;
comp.setEqual(value);
}
void bigint::setSize(size newsize)
{
element* newarray=NULL;
newarray=new element[newsize];
for(size i=0;i<numelem;i++)
{
newarray[i]=elem[i];
}
for(size i=numelem;i<newsize;i++)
{
newarray[i]=0;
}
delete elem;
elem=newarray;
numelem=newsize;
}
void bigint::grow(size minsize)
{
if(minsize<numelem)
return;
size newsize=numelem;
while(minsize>newsize)
{
newsize*=2;
}
setSize(newsize);
}
void bigint::shrink()
{
size testsize=numelem;
bool isClean=true;
while(testsize>1&&isClean)
{
testsize/=2;
for(size i=testsize*2;i<testsize/2;i++)
{
if(elem[i]!=0)
{
isClean=false;
break;
}
}
}
if(testsize<numelem)
setSize(testsize);
}
}