Next ... class expanded to permit division of Big Integers ...
// classBigInt.cpp // version 2 on 2014-07-26 //
// class for large int's as strings with overloaded +, -, *, /
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cassert>
using namespace std;
// trim leading and trailing whitespaces from 's' ... and return by 'ref.'
void trim( string& s, const string t = " \t" ) // default whitespace: "\t "
{
size_t p1 = s.find_first_not_of( t ); // get index of 'first char' ...
if( string::npos != p1 ) // ok ... not all ws ... nor empty ... so can safely
{
s.erase( 0, p1 );
size_t p2 = s.find_last_not_of( t ); // get index of 'last char' ...
s.erase( p2+1 );
}
else // ... all whitespaces or empty
s.clear();
}
string itostring( int i )
{
ostringstream oss;
oss << i;
return oss.str();
}
// prototype declared here ... so can use QuoRem in class BigInt
struct QuoRem;
class BigInt
{
public:
// constructors ...
BigInt() : snum("0"), sign('+') {}
BigInt( const string& s ) : snum(s) { normalize(); delLeadZeros(); }
BigInt( int s ) : snum( itostring(s) ) { extractNegSign(); }
char get_sign() const { return sign; }
void showData() const
{
int count = 0, i = snum.size();
while( i && snum[--i] == '0' ) ++count;
cout << "size = " << snum.size()
<< ", end zeros = " << count;
}
private:
string snum;
char sign;
void normalize()
{
trim( snum ); // trim off all leading and trailing whitespaces ...
if( snum[0] == '-' || snum[0] == '+' ) { sign = snum[0]; snum.erase(0, 1); }
else sign = '+';
int len = snum.size();
for( int i = 0; i < len; ++i ) // if not a valid integer ... set to "0"
if( snum[i] < '0' || '9' < snum[i] )
{ snum = "0"; break; }
}
void delLeadZeros() // erase leading zeros ... but NOT last zero
{
int i = 0, len_1 = snum.size() -1;
while( i < len_1 && snum[i] == '0' )
++i;
snum.erase( 0, i );
if( snum == "0" ) sign = '+';
}
void extractNegSign()
{
if( snum[0] == '-' ) { sign = '-'; snum.erase( 0, 1 ); }
else sign = '+';
}
friend ostream& operator << ( ostream& os, const BigInt& s )
{ return os << "("<< (s.sign == '-' ? "-" : "") << s.snum << ")"; }
// find if abs(a) >= abs(b) ...
friend bool operator >= ( const BigInt& a, const BigInt& b )
{
int len1 = a.snum.size(), len2 = b.snum.size();
if( len1 > len2 ) return true;
if( len1 == len2 ) return a.snum >= b.snum;
return false;
}
friend bool operator > ( const BigInt& a, const BigInt& b )
{
int len1 = a.snum.size(), len2 = b.snum.size();
if( len1 > len2 ) return true;
if( len1 == len2 ) return a.snum > b.snum;
return false;
}
friend bool operator == ( const BigInt& a, const BigInt& b )
{
if( a.snum == b.snum ) return true;
return false;
}
friend bool operator != ( const BigInt& a, const BigInt& b )
{
if( a.snum != b.snum ) return true;
return false;
}
friend bool operator <= ( const BigInt& a, const BigInt& b )
{
int len1 = a.snum.size(), len2 = b.snum.size();
if( len1 < len2 ) return true;
if( len1 == len2 ) return a.snum <= b.snum;
return false;
}
friend bool operator < ( const BigInt& a, const BigInt& b )
{
int len1 = a.snum.size(), len2 = b.snum.size();
if( len1 < len2 ) return true;
if( len1 == len2 ) return a.snum < b.snum;
return false;
}
// i.e. ... flip sign of 'a' ...
friend BigInt operator - ( const BigInt& a )
{
BigInt b = a;
if( b.snum == "0" ) { b.sign = '+'; return b; }
// else ...
b.sign = ( a.sign == '+' ? '-' : '+' );
return b;
}
friend char sumof( char a, char b, int& carry )
{
int sum = a-'0' + b-'0' + carry;
if( sum > 9 ) { sum -= 10; carry = 1; }
else carry = 0;
return char( '0' + sum );
}
friend char sumof( char s, int& carry )
{
int sum = s-'0' + carry;
if( sum > 9 ) { sum -= 10; carry = 1; }
else carry = 0;
return char( '0' + sum );
}
// uses both friend functions above ...
friend BigInt operator + ( const BigInt& a, const BigInt& b )
{
if( a.sign == b.sign )
{
int len1 = a.snum.size(), len2 = b.snum.size();
int ml = (len1 > len2 ? len1 : len2);
BigInt s;
s.snum.resize( ml );
int carry = 0;
while( len1 && len2 )
s.snum[--ml] = sumof( a.snum[--len1], b.snum[--len2], carry );
// at most ... will do only one of the following 2 'while loops' ...
while( len1 )
s.snum[--ml] = sumof( a.snum[--len1], carry );
while( len2 )
s.snum[--ml] = sumof( b.snum[--len2], carry );
if( carry )
s.snum = "1" + s.snum;
s.sign = a.sign;
return s;
}
// else if ... if didn't 'return' above ... signs are different!
if( a.sign == '+' ) return a - (-b);
// else ...
return -((-a) - b);
}
friend char difof( char a, char b, int& carry )
{
int sum = a-'0' - (b-'0') + carry;
if( sum < 0 ) { sum += 10; carry = -1; }
else carry = 0;
return char( '0' + sum );
}
friend char difof( char s, int& carry )
{
int sum = s-'0' + carry;
if( sum < 0 ) { sum += 10; carry = -1; }
else carry = 0;
return char( '0' + sum );
}
// uses both friend functions above ...
friend BigInt operator - ( const BigInt& a, const BigInt& b )
{
if( a.sign == b.sign )
{
if( a >= b )
{
int len1 = a.snum.size(), len2 = b.snum.size(), carry = 0;
BigInt s;
s.snum.resize( len1 );
while( len1 && len2 )
{ --len1; --len2; s.snum[len1] = difof( a.snum[len1], b.snum[len2], carry ); }
while( len1-- )
{ s.snum[len1] = difof( a.snum[len1], carry ); }
s.sign = a.sign;
s.delLeadZeros();
return s;
}
else // return -( b - a );
{
int len1 = a.snum.size(), len2 = b.snum.size(), carry = 0;
BigInt s;
s.snum.resize( len2 );
while( len2 && len1 )
{ --len2; --len1; s.snum[len2] = difof( b.snum[len2], a.snum[len1], carry ); }
while( len2-- )
{ s.snum[len2] = difof( b.snum[len2], carry ); }
s.sign = b.sign;
s.delLeadZeros();
return -s;
}
}
// if reach here ... signs are different ...
//else if( a.sign == '+' ) return a + (-b);
else return a + (-b);
}
// a >= 0 ...
//friend char productof( int a, const BigInt& b, int len2, int& carry )
friend char productof( int a, char b, int& carry )
{
int sum = a * (b - '0') + carry;
if( sum > 9 ) { carry = sum/10; sum = sum%10; }
else carry = 0;
return char( '0' + sum );
}
friend BigInt operator * ( int a, const BigInt& b )
{
int len2 = b.snum.size();
BigInt s;
s.snum.resize( len2 );
char signA = '+';
if( a < 0 ) { a = -a; signA = '-'; }
int carry = 0;
while( len2-- )
s.snum[len2] = productof( a, b.snum[len2], carry );
//productof( a, b, len2, carry );
if( carry )
s.snum = char( '0'+carry ) + s.snum;
if( signA == b.sign ) s.sign = '+';
else s.sign = '-';
s.delLeadZeros();
return s;
}
// uses both friend functions above ...
friend BigInt operator * ( const BigInt& a, const BigInt& b )
{
BigInt s; // initial value is zero ...
// multiply 'longer' by 'shorter' ...
if( a.snum.size() >= b.snum.size() )
{
int len1 = b.snum.size();
while( len1-- )
{
BigInt n = (b.snum[len1]-'0') * ( a.sign == '+' ? a : -a ) ;
n.delLeadZeros();
// shift left ... before adding ..
n.snum += string( b.snum.size()-1-len1, '0' );
s = s + n;
}
}
else
{
int len1 = a.snum.size();
while( len1-- )
{
BigInt n = (a.snum[len1]-'0') * ( b.sign == '+' ? b : -b );
n.delLeadZeros();
// shift left ... before adding ...
n.snum += string( a.snum.size()-1-len1, '0' );
s = s + n;
}
}
s.sign = ( a.sign == b.sign ? '+' : '-' );
if( s.snum == "0" ) s.sign = '+';
return s;
}
// prototypes ... Note: QuoRem isn't defined until after class BigInt ...
// since QuoRem uses BigInt ... and needs BigInt defined
friend BigInt division( const BigInt& dividend, const BigInt& divisor, BigInt& remain );
friend QuoRem operator / ( const BigInt& dividend, const BigInt& divisor );
} ;
struct QuoRem
{
BigInt quo;
BigInt rem;
};
/*
get_quotient function computes the quotient and ...
remainder of two numbers ... using "a type of 'bit' shifting"
*/
BigInt division( const BigInt& dividend, const BigInt& divisor, BigInt& remain )
{
BigInt quotient(1);
if( divisor > dividend ) // if( abs(divisor) > abs(dividend) ) ...
{
quotient = BigInt();
remain = dividend;
}
else if( divisor == dividend )
{
// quotient already initialed to 1 above ...
/* quotient = BigInt(1); */
remain = BigInt();
}
else
{
BigInt tmp_divisor = divisor;
while( tmp_divisor <= dividend )
{
/*
Here divisor <= dividend, therefore ...
left shift (i.e. multiply by 2) ... divisor and quotient
*/
tmp_divisor = 2*tmp_divisor; // times 2 ...
quotient = 2*quotient;
}
/*
We have reached the point where divisor > dividend,
therefore divide divisor and quotient by two ... or times 5/10
*/
tmp_divisor = 5*tmp_divisor; // times 5 ...
quotient = 5*quotient; // times 5 ...
tmp_divisor.snum.erase(tmp_divisor.snum.size()-1); // and divide by 10
quotient.snum.erase(quotient.snum.size()-1); // and divide by 10
/*
Now call get_quotient RECURSIVEly for the difference ...
... to get the exact quotient
*/
quotient = quotient + division( (dividend-tmp_divisor), divisor, remain );
}
return quotient;
}
// returns quotient and remaider via the struc QuoRem ...
QuoRem operator / ( const BigInt& dividend, const BigInt& divisor )
{
QuoRem qr;
if( divisor.snum == "0" )
{
qr.quo.snum = "Error! Division by ZERO is NOT defined!";;
return qr;
}
BigInt s, remain;
if( dividend.sign == divisor.sign )
{
if( dividend.sign == '+' )
s = division( dividend, divisor, remain );
else
s = division( -dividend, -divisor, remain );
s.sign = '+';
}
else // signs are different ...
{
if( dividend.sign == '-' )
s = division( -dividend, divisor, remain );
else
s = division( dividend, -divisor, remain );
s.sign = '-';
remain.sign = '-';
}
if( s.snum == "0" ) s.sign = '+';
if( remain.snum == "0" ) remain.sign = '+';
qr.quo = s;
qr.rem = remain;
return qr;
}
int main()
{
BigInt s1( "+0009876543210987654" );
BigInt s2( "-0001234567890123456" );
BigInt s3;
BigInt t = s2 + BigInt(1);
// testing adding 2 BigInt's ...
cout << s1 << "+" << s2 << "=" << s1+s2 << endl;
cout << s2 << "+" << s1 << "=" << s2+s1 << endl << endl;
assert( s1+s2 == s2+s1 );
// testing subtracting 2 BigInt's ...
s3 = s1 - s2;
cout << s1 << "-" << s2 << "=" << s1-s2 << endl;
cout << s3 << "+" << s2 << "=" << s3+s2 << endl << endl;
assert( s1 == s3 + s2 );
s3 = s2 - s1;
cout << s2 << "-" << s1 << "=" << s2-s1 << endl;
cout << s3 << "+" << s1 << "=" << s3+s1 << endl << endl;
assert( s2 == s3 + s1 );
cout << s2 << "-" << t << "=" << s2-t << endl;
cout << t << "-" << s2 << "=" << t-s2 << endl;
assert( s2-t == -(t-s2) );
cout << t+BigInt(-1) << "-" << s2 << "=" << (t+BigInt(-1))-s2 << endl << endl;
assert( (t+BigInt(-1)) - s2 + ( s2 -BigInt(-1) ) == t );
QuoRem qr; // to hold quotient and remainder for division returned values
do
{
qr = s1/s2;
cout << s1 << "/" << s2 << "=" << qr.quo << ", remainder="
<< qr.rem << endl;
// now verify division .. ( i.e. multiply back ... )
if( s2.get_sign() == '-')
cout << qr.quo << "*" << s2 << "-" << qr.rem << "="
<< qr.quo*s2 - qr.rem << endl << endl;
else
cout << qr.quo << "*" << s2 << "+" << qr.rem << "="
<< qr.quo*s2 + qr.rem << endl << endl;
if( s2.get_sign() == '-')
assert( s2*qr.quo - qr.rem == s1 );
else
assert( s2*qr.quo + qr.rem == s1 );
QuoRem qr2 = s2 / BigInt(123);
s2 = qr2.quo;
}
while( s2 != BigInt(0) );
s2 = BigInt( "+0001234567890123456" ); // reset ...
cout << "Press 'Enter' to continue ... " << flush;
cin.get();
cout << endl;
s3 = s1 + s2;
// testing adding 2 BigInt's ...
cout << s1 << "+" << s2 << "=" << s3 << endl
<< s3-s2 << "=" << s3 << "-" << s2 << endl;
cout << s2 << "+" << s1 << "=" << s2+s1 << endl << endl;
assert( s2 == s3-s1 );
s1 = -s1; s3 = s1 + s2;
// testing adding 2 BigInt's ...
cout << s1 << "+" << s2 << "=" << s3 << endl
<< s3-s2 << "=" << s3 << "-" << s2 << endl;
cout << s2 << "+" << s1 << "=" << s2+s1 << endl << endl;
assert( s2 == s3-s1 );
s2 = -s2; s1 = -s1; s3 = s1 + s2;
// testing adding 2 BigInt's ...
cout << s1 << "+" << s2 << "=" << s3 << endl
<< s3-s2 << "=" << s3 << "-" << s2 << endl;
cout << s2 << "+" << s1 << "=" << s2+s1 << endl << endl;
assert( s2 == s3-s1 );
s2 = 10*s2; s3 = s1 + s2;
// testing adding 2 BigInt's ...
cout << s1 << "+" << s2 << "=" << s3 << endl
<< s3-s2 << "=" << s3 << "-" << s2 << endl;
cout << s2 << "+" << s1 << "=" << s2+s1 << endl << endl;
assert( s2 == s3-s1 );
cout << "Press 'Enter' to continue ... " << flush;
cin.get();
cout << endl;
// testing multiplying by a constant multiplier <= 10 in front ...
for( int a = 0; a < 11; ++a )
{
cout << a << "*" << s2 << "=" << a*s2 << endl;
if( a )
assert( ((a*s2) / BigInt(a)).quo == s2 );
}
cout << endl;
// testing multiplying 2 BigInt's ...
cout << s1 << "*" << s2 << "=" << s1*s2 << endl;
cout << s2 << "*" << s1 << "=" << s2*s1 << endl << endl;
assert( s1*s2 == s2*s1 );
s1 = -s1;
// testing multiplying 2 BigInt's ...
for( int i = 0; i < 3; ++i )
{
BigInt s3(i*1000000000); // i * 10^10
cout << s1 << "*" << s3 << "=" << s1*s3 << endl;
cout << s3 << "*" << s1 << "=" << s3*s1 << endl;
assert( s1*s3 == s3*s1 );
}
cout << endl;
cout << "Press 'Enter' to continue ... " << flush;
cin.get();
s1 = BigInt(1);
// testing multiplying 2 BigInt's ... (and find factorial) ...
for( int i = 1; i <= 200; ++i )
{
BigInt s3(i);
s1 = s1*s3;
if( i <=5 || i == 200 )
{
cout << "Factorial("<< i << ") <with ";
s1.showData();
cout << "> is " << endl;
cout << s1 << endl << endl;
}
if( i == 5 ) cout << "...\n\n";
}
cout << "Press 'Enter' to EXIT PROGRAM ... " << flush;
cin.get();
}
