// classStrInt.cpp // // 2014-07-26 //
// start of class for ... large int's as strings //
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
using namespace std;
string itostring( int a )
{
ostringstream oss;
oss << a;
return oss.str();
}
class StrInt
{
public:
// ctor... from string ...
StrInt( const string& s = "0" ) : snum(s)
{ trim(snum); validate(snum); normalize(); }
// ctor from int ...
StrInt( int s ) : snum( itostring(s) ) {}
void showData()
{
int count = 0;
int i = snum.size();
while( i && snum[--i] == '0' ) ++count;
cout << "size = " << snum.size()
<< ", end zeros = " << count;
}
private:
string snum;
void normalize()
{
//now called in ctor ...
//trim( snum ); // trim off all leading and trailing whitespaces ...
/* // now ... validate is done in ctor ...
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"; len = 1; break; }
*/
// erase leading zeros ... but NOT last zero
int i = 0, j = snum.size() -1;
while( i < j && snum[i] == '0' ) ++i;
snum.erase( 0, i );
}
// if not a valid integer ... set to "0"
static bool validate( string& s )
{
int len = s.size();
for( int i = 0; i < len; ++i )
if( s[i] < '0' || '9' < s[i] )
{ s = "0"; return false; }
return true;
}
// trim leading and trailing whitespaces from 's' ... and return by 'ref.'
static 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 was whitespace ... or was empty
s.clear();
}
friend ostream& operator << ( ostream& os, const StrInt& s )
{ return os << s.snum; }
friend char sumof( const StrInt& a, int len1, const StrInt& b, int len2, int& carry )
{
int sum = a.snum[len1]-'0' + b.snum[len2]-'0' + carry;
if( sum > 9 ) { sum -= 10; carry = 1; }
else carry = 0;
return char( '0' + sum );
}
friend char sumof( const StrInt& s, int len, int& carry )
{
int sum = s.snum[len]-'0' + carry;
if( sum > 9 ) { sum -= 10; carry = 1; }
else carry = 0;
return char( '0' + sum );
}
// uses both friend functions above ...
friend StrInt operator + ( const StrInt& a, const StrInt& b )
{
int len1 = a.snum.size();
int len2 = b.snum.size();
int ml = (len1 > len2 ? len1 : len2);
StrInt s;
s.snum.resize( ml );
int carry = 0;
while( len1 && len2 )
s.snum[--ml] = sumof( a, --len1, b, --len2, carry );
if( len1 )
while( len1 )
s.snum[--ml] = sumof( a, --len1, carry );
else if( len2 )
while( len2 )
s.snum[--ml] = sumof( b, --len2, carry );
if( carry )
s.snum = "1" + s.snum;
return s;
}
friend char productof( int a, const StrInt& b, int len2, int& carry )
{
int sum = a * (b.snum[len2]-'0') + carry;
if( sum > 9 ) { carry = sum/10; sum = sum%10; }
else carry = 0;
return char( '0' + sum );
}
friend StrInt operator * ( int a, const StrInt& b )
{
int len2 = b.snum.size();
StrInt s;
s.snum.resize( len2 );
int carry = 0;
while( len2-- )
s.snum[len2] = productof( a, b, len2, carry );
if( carry )
s.snum = char( '0'+carry ) + s.snum;
s.normalize();
return s;
}
// uses both friend functions above ...
friend StrInt operator * ( const StrInt& a, const StrInt& b )
{
int len1 = a.snum.size();
StrInt s;
while( len1-- )
{
StrInt n = (a.snum[len1]-'0') * b;
n.normalize();
if( n.snum != "0" )
{
/*
for( int i = a.snum.size()-1-len1; i > 0; --i )
n = 10*n;
*/
int shiftLeft = a.snum.size()-1-len1;
if( shiftLeft > 0 )
n.snum += string( shiftLeft, '0' );
}
s = s + n;
}
return s;
}
};
int main()
{
StrInt s1( "0001234567890123456789" );
StrInt s2( "0009876543210987654321" );
// testing adding 2 StrInt's ...
cout << s1 << "+" << s2 << "=" << s1+s2 << endl;
cout << s2 << "+" << s1 << "=" << s2+s1 << endl << endl;
// testing multiplying by a constant multiplier <= 10 in front ...
for( int a = 0; a < 11; ++a )
cout << a << "*" << s2 << "=" << a*s2 << endl;
cout << endl;
// testing multiplying 2 StrInt's ...
cout << s1 << "*" << s2 << "=" << s1*s2 << endl;
cout << s2 << "*" << s1 << "=" << s2*s1 << endl;
cout << endl;
// testing multiplying 2 StrInt's ...
for( int i = 0; i <= 2; ++i )
{
StrInt s3(i*1000000000); // i * 10^10
cout << s1 << "*" << s3 << "=" << s1*s3 << endl;
cout << s3 << "*" << s1 << "=" << s3*s1 << endl;
}
cout << "Press 'Enter' to exit ... " << flush;
cin.get();
s1 = StrInt(1);
// testing multiplying 2 StrInt's ...
for( int i = 1; i < 25; ++i )
{
StrInt s3(i);
s1 = s3*s1;
cout << "Factorial("<< i << ") = " << s1 << " ";
s1.showData();
cout << endl;
//cin.get();
}
cout << "Press 'Enter' to exit ... " << flush;
cin.get();
}
// classStrIntNeg.cpp // // 2014-07-26 //
// class for large int's as strings (handles neg int's) //
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
using namespace std;
string itostring( int i )
{
ostringstream oss;
oss << i;
return oss.str();
}
class StrInt
{
public:
StrInt( const string& s = "0" ) : snum(s)
{ normalize(); delLeadZeros(); }
StrInt( int s ) : snum( itostring(s) ) { normalize(); }
void showData() const
{
int count = 0;
int i = snum.size();
while( i && snum[--i] == '0' ) ++count;
cout << "size = " << snum.size()
<< ", end zeros = " << count;
}
private:
string snum;
char sign;
void normalize()
{
// trim off all leading and trailing whitespaces ...
trim( snum );
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( snum[i] < '0' || '9' < snum[i] )
/* if not a valid integer ... set to "0" */
{ snum = "0"; break; }
}
// erase leading zeros ... but NOT last zero
void delLeadZeros()
{
int i = 0, j = snum.size() -1;
while( i < j && snum[i] == '0' ) ++i;
snum.erase( 0, i );
if( snum == "0" ) sign = '+';
}
// trim leading and trailing whitespaces from 's' ... and return by 'ref.'
static 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();
}
friend ostream& operator << ( ostream& os, const StrInt& s )
{ return os << "("<< (s.sign == '-' ? "-" : "") << s.snum << ")"; }
// comapres the absolute values ...
friend bool operator >= ( const StrInt& a, const StrInt& 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 StrInt operator - ( const StrInt& a )
{
StrInt b = a;
if( b.snum == "0" ) { b.sign = '+'; return b; }
// else ...
b.sign = ( a.sign == '+' ? '-' : '+' );
return b;
}
friend char sumof( const StrInt& a, int len1, const StrInt& b, int len2, int& carry )
{
int sum = a.snum[len1]-'0' + b.snum[len2]-'0' + carry;
if( sum > 9 ) { sum -= 10; carry = 1; }
else carry = 0;
return char( '0' + sum );
}
friend char sumof( const StrInt& s, int len, int& carry )
{
int sum = s.snum[len]-'0' + carry;
if( sum > 9 ) { sum -= 10; carry = 1; }
else carry = 0;
return char( '0' + sum );
}
// uses both friend functions above ...
friend StrInt operator + ( const StrInt& a, const StrInt& b )
{
int len1 = a.snum.size();
int len2 = b.snum.size();
int ml = (len1 > len2 ? len1 : len2);
StrInt s;
s.snum.resize( ml );
if( a.sign == b.sign )
{
int carry = 0;
while( len1 && len2 )
s.snum[--ml] = sumof( a, --len1, b, --len2, carry );
if( len1 )
{
while( len1 )
s.snum[--ml] = sumof( a, --len1, carry );
}
else if( len2 )
{
while( len2 )
s.snum[--ml] = sumof( b, --len2, carry );
}
if( carry )
s.snum = "1" + s.snum;
s.sign = a.sign;
return s;
}
// if reach here ... signs are different ... //
else if( a >= b ) // i.e. abs(a) >= abs(b) ...
{
if( a.sign == '+' ) return a - (-b);
else return -((-a) - b);
}
else
{
if( b.sign == '+' ) return b - (-a);
else return -((-b) - a);
}
}
// abs(a) >= abs(b) ...
friend char difof( const StrInt& a, int len1, const StrInt& b, int len2, int& carry )
{
int sum = a.snum[len1]-'0' - (b.snum[len2]-'0') + carry;
if( sum < 0 ) { sum += 10; carry = -1; }
else carry = 0;
return char( '0' + sum );
}
friend char difof( const StrInt& s, int len, int& carry )
{
int sum = s.snum[len]-'0' + carry;
if( sum < 0 ) { sum += 10; carry = -1; }
else carry = 0;
return char( '0' + sum );
}
// uses both friend functions above ...
friend StrInt operator - ( const StrInt& a, const StrInt& b )
{
int len1 = a.snum.size();
int len2 = b.snum.size();
int ml = (len1 > len2 ? len1 : len2);
StrInt s;
s.snum.resize( ml );
int carry = 0;
if( a.sign == b.sign )
{
if( a >= b )
{
while( len1 && len2 )
s.snum[--ml] = difof( a, --len1, b, --len2, carry );
while( len1 )
s.snum[--ml] = difof( a, --len1, carry );
s.sign = a.sign;
s.delLeadZeros();
return s;
}
else
{
while( len2 && len1 )
s.snum[--ml] = difof( b, --len2, a, --len1, carry );
while( len2 )
s.snum[--ml] = difof( b, --len2, carry );
s.sign = b.sign;
s.delLeadZeros();
return -s;
}
}
//else if( a.sign == '+' ) return a + (-b);
else return a + (-b);
}
// a >= 0 ...
friend char productof( int a, const StrInt& b, int len2, int& carry )
{
int sum = a * (b.snum[len2]-'0') + carry;
if( sum > 9 ) { carry = sum/10; sum = sum%10; }
else carry = 0;
return char( '0' + sum );
}
friend StrInt operator * ( int a, const StrInt& b )
{
int len2 = b.snum.size();
StrInt s;
s.snum.resize( len2 );
char signA = '+';
if( a < 0 ) { a = -a; signA = '-'; }
int carry = 0;
while( len2-- )
s.snum[len2] = 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 StrInt operator * ( const StrInt& a, const StrInt& b )
{
StrInt s; // initial value is zero ...
if( a >= b )
{
int len1 = b.snum.size();
while( len1-- )
{
StrInt 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-- )
{
StrInt 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;
}
} ;
int main()
{
StrInt s1( "+0009876543210987654" );
StrInt s2( "+0001234567890123456" );
StrInt s3 = s1 + s2;
// testing adding 2 StrInt's ...
cout << s1 << "+" << s2 << "=" << s3 << endl
<< s3-s2 << "=" << s3 << "-" << s2 << endl;
cout << s2 << "+" << s1 << "=" << s2+s1 << endl << endl;
s1 = -s1; s3 = s1 + s2;
// testing adding 2 StrInt's ...
cout << s1 << "+" << s2 << "=" << s3 << endl
<< s3-s2 << "=" << s3 << "-" << s2 << endl;
cout << s2 << "+" << s1 << "=" << s2+s1 << endl << endl;
s2 = -s2; s1 = -s1; s3 = s1 + s2;
// testing adding 2 StrInt's ...
cout << s1 << "+" << s2 << "=" << s3 << endl
<< s3-s2 << "=" << s3 << "-" << s2 << endl;
cout << s2 << "+" << s1 << "=" << s2+s1 << endl << endl;
s2 = 10*s2; s3 = s1 + s2;
// testing adding 2 StrInt's ...
cout << s1 << "+" << s2 << "=" << s3 << endl
<< s3-s2 << "=" << s3 << "-" << s2 << endl;
cout << s2 << "+" << s1 << "=" << s2+s1 << endl << endl;
// testing multiplying by a constant multiplier <= 10 in front ...
for( int a = 0; a < 11; ++a )
cout << a << "*" << s2 << "=" << a*s2 << endl;
cout << endl;
// testing multiplying 2 StrInt's ...
cout << s1 << "*" << s2 << "=" << s1*s2 << endl;
cout << s2 << "*" << s1 << "=" << s2*s1 << endl;
cout << endl;
// testing multiplying 2 StrInt's ...
for( int i = 0; i < 3; ++i )
{
StrInt s3(i*1000000000); // i * 10^10
cout << s1 << "*" << s3 << "=" << s1*s3 << endl;
cout << s3 << "*" << s1 << "=" << s3*s1 << endl;
}
cout << "Press 'Enter' to exit ... " << flush;
cin.get();
s1 = StrInt(1);
// testing multiplying 2 StrInt's ... (and find factorial) ...
for( int i = 1; i <= 24; ++i )
{
StrInt s3(i);
s1 = s1*s3;
cout << "Factorial("<< i << ") <with ";
s1.showData();
cout << "> is " ; //<< endl;
cout << s1 << endl;
//cin.get();
}
cout << "Press 'Enter' to exit ... " << flush;
cin.get();
}
// 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();
}
// structBigIntNeg2.cpp // version 2 revised 2014-07-26 //
// a start of a struct to handle large int's as strings ...
// this version does subtraction by adding using the 9's complement ...
// and then ... see ...
// http://en.wikipedia.org/wiki/Method_of_complements // re. subtracting ...
// subtraction method suggested by Circuit_Girl at DIC ...
// http://www.dreamincode.net/forums/topic/189506-9s-compliment-to-subtract-strings/
#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 or 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 a )
{
ostringstream oss;
oss << a;
return oss.str();
}
struct BigInt
{
string snum;
char sign;
// constructors ...
BigInt() : snum("0"), sign('+') {} // default constructor ...
BigInt( string s ) : snum(s) { trim(snum); setSign(); validate(); delLeadZeros(); }
BigInt( int s ) : snum( itostring(s) ) { setSign(); }
void setSign()
{
if( snum[0] == '-' || snum[0] == '+' ) // get sign and erase from string
{ sign = snum[0]; snum.erase(0, 1); }
else sign = '+';
}
void validate()
{
for( int i = snum.size()-1; i >= 0; --i ) // if not valid integer set to "0"
if( snum[i] < '0' || '9' < snum[i] )
{ snum = "0"; break; }
}
void delLeadZeros() // but leave last zero un-erased (if all zeros) ...
{
size_t i = 0;
while( i < snum.size()-1 && snum[i] == '0' )
++i;
snum.erase( 0, i );
if( snum == "0" ) sign = '+';
}
void showData() const
{
int count = 0, i = snum.size();
while( i && snum[--i] == '0' ) ++count;
cout << "size = " << snum.size()
<< ", end zeros = " << count;
}
};
// overloaded operators ... and functions ...
ostream& operator << ( ostream& os, const BigInt& bi )
{
return os << "(" << (bi.sign=='+' ? "" : "-") << bi.snum << ")";
}
// compares absolute values only ... (i.e. ignores sign)
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;
}
char sumof( char a, char b, int& carry )
{
int sum = a-'0' + b-'0' + carry; // char's get 'cast' to int values ...
if( sum > 9 ) { sum -= 10; carry = 1; }
else carry = 0;
return char( '0' + sum );
}
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 );
}
// prototypes / forward declarations ... as these are both needed below ...
// for the overloaded operator + that comes next ...
BigInt operator - ( const BigInt& a );
BigInt operator - ( const BigInt& a, const BigInt& b );
// uses both 'sumof' functions above ... (and the overloaded 'operator -')
BigInt operator + ( const BigInt& a, const BigInt& b )
{
if( a.sign == b.sign )
{
int len1 = a.snum.size(), len2 = b.snum.size(), carry = 0;
int ml = (len1 > len2 ? len1 : len2);
BigInt s;
s.snum.resize( ml );
s.sign = a.sign;
while( len1 && len2 ) // i.e. while both are greater than zero ...
s.snum[--ml] = sumof( a.snum[--len1], b.snum[--len2], carry );
// at most ... only one of the following 2 while loops will execute ...
// since NOW ... len1 or len2 is zero ... or both are zero.
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;
return s;
}
// else signs are different ...
if( a.sign == '+' ) return ( a - (-b) );
// else a.sign is '-' ... so ...
return -( (-a) - b );
}
// get 'neg value' ... i.e. switch sign ... (a 'quick' function call)
BigInt operator - ( const BigInt& a )
{
BigInt n = a; // construct a new copy of 'a' ...
if( n.snum == "0" ) n.sign = '+';
else n.sign = ( a.sign=='+' ? '-' : '+' ); // n has the opposite sign as a
return n; // return the new copy with the updated opposite sign (if not zero)
}
// uses adding with the 9's complement ...
BigInt operator - ( const BigInt& a, const BigInt& b )
{
// handle special case ...
if( a.sign == b.sign && a.snum == b.snum )
return BigInt(0);
if( a.sign != b.sign ) // then add together ...
{
if( a.sign == '+' ) return a + (-b);
// else a.sign is '-' ...
return -( (-a) + b );
}
// else same signs ... so ... if |a| > |b|
if( a > b ) // then can do ... a - b
{
int len1 = a.snum.size(), len2 = b.snum.size();
BigInt c; // construct a new BigInt vith value 0
string sval( len1, '9' ); // construct all 9's STL string ...
c.snum = sval; // update BigInt value ... now all 9's
c.sign = a.sign; // update sign ...
while( len2 ) // get 9's complement ... (of 'b')
{
--len1; --len2; // update 'next_in_far_right_index' (each term)
c.snum[len1] = char( c.snum[len1] - b.snum[len2] + '0' );
}
c = c + a; // now add a + 9's complement ...
c.snum.erase( 0, 1 ); // remove leading unwanted '1' of overflow
c.delLeadZeros();
if( c.sign == '+' ) return c + BigInt(1);
// else ...
return -( (-c) + BigInt(1) );
}
//else ...
return -(b - a); // a recursive call here...
}
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 );
}
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 );
if( carry )
s.snum = char( '0'+carry ) + s.snum;
if( signA == b.sign ) s.sign = '+';
else s.sign = '-';
s.delLeadZeros(); // also handles 'zero' sign fix ...
return s;
}
// uses both friend functions above ...
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;
}
bool operator == ( const BigInt& a, const BigInt& b )
{
if( a.sign == b.sign && a.snum == b.snum )
return true;
return false;
}
int main()
{
BigInt s1( "001234567890123456789 " );
BigInt s2( "-9876543210987654321" );
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 ...
BigInt 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;
cout << t+BigInt(-1) << "-" << s2 << "="
<< (t+BigInt(-1))-s2 << endl << endl;
assert( (t+BigInt(-1))-s2 + (s2-BigInt(-1)) == t );
// testing multiplying by a constant multiplier <= 10 in front ...
for( int a = 0; a < 11; ++a )
cout << a << "*" << s2 << "=" << a*s2 << endl;
cout << endl;
// testing multiplying 2 BigInt's ...
cout << s1 << "*" << s2 << "=" << s1*s2 << endl;
cout << s2 << "*" << s1 << "=" << s2*s1 << endl;
assert( s1*s2 == s2*s1 );
cout << endl;
// 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 << "Press 'Enter' to test BigInt factorials ... " << flush;
cin.get();
s1 = BigInt(1);
// testing multiplying 2 BigInt's ...
for( int i = 1; i <= 500; ++i )
{
BigInt s3(i);
s1 = s3*s1;
}
cout << "Factorial("<< 500 << ")=\n" << s1 << " ";
s1.showData();
cout << "\nPress 'Enter' to exit ... " << flush;
cin.get();
}
// output ...
/*
(1234567890123456789)+(-9876543210987654321)=(-8641975320864197532)
(-9876543210987654321)+(1234567890123456789)=(-8641975320864197532)
(1234567890123456789)-(-9876543210987654321)=(11111111101111111110)
(11111111101111111110)+(-9876543210987654321)=(1234567890123456789)
(-9876543210987654321)-(1234567890123456789)=(-11111111101111111110)
(-11111111101111111110)+(1234567890123456789)=(-9876543210987654321)
(-9876543210987654321)-(-9876543210987654320)=(1)
(-9876543210987654320)-(-9876543210987654321)=(-1)
(-9876543210987654321)-(-9876543210987654321)=(0)
0*(-9876543210987654321)=(0)
1*(-9876543210987654321)=(-9876543210987654321)
2*(-9876543210987654321)=(-19753086421975308642)
3*(-9876543210987654321)=(-29629629632962962963)
4*(-9876543210987654321)=(-39506172843950617284)
5*(-9876543210987654321)=(-49382716054938271605)
6*(-9876543210987654321)=(-59259259265925925926)
7*(-9876543210987654321)=(-69135802476913580247)
8*(-9876543210987654321)=(-79012345687901234568)
9*(-9876543210987654321)=(-88888888898888888889)
10*(-9876543210987654321)=(-98765432109876543210)
(1234567890123456789)*(-9876543210987654321)=(-121932631137021795223746380111126
35269)
(-9876543210987654321)*(1234567890123456789)=(-121932631137021795223746380111126
35269)
(1234567890123456789)*(0)=(0)
(0)*(1234567890123456789)=(0)
(1234567890123456789)*(1000000000)=(1234567890123456789000000000)
(1000000000)*(1234567890123456789)=(1234567890123456789000000000)
(1234567890123456789)*(2000000000)=(2469135780246913578000000000)
(2000000000)*(1234567890123456789)=(2469135780246913578000000000)
Press 'Enter' to test BigInt factorials ...
Factorial(500)=
(1220136825991110068701238785423046926253574342803192842192413588385845373153881
99760549644750220328186301361647714820358416337872207817720048078520515932928547
79075719393306037729608590862704291745478824249127263443056701732707694610628023
10452644218878789465754777149863494367781037644274033827365397471386477878495438
48959553753799042324106127132698432774571554630997720278101456108118837370953101
63563244329870295638966289116589747695720879269288712817800702651745077684107196
24390394322536422605234945850129918571501248706961568141625359056693423813008856
24924689156412677565448188650659384795177536089400574523894033579847636394490531
30623237490664450488246650759467358620746379251842004593696929810222639719525971
90945217823331756934581508552332820762820023402626907898342451712006207714640979
45611612762914595123722991334016955236385094288559201872743379517301458635757082
83557801587354327688886801203998823847021514676054454076635359841744304801289383
13896881639487469658817504506926365338175055478128640000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000) size = 1135, end zeros = 124
Press 'Enter' to exit ...
*/
// BigInt2.h // // this revision 2014-07-26 //
#ifndef BIG_INT2_H_
#define BIG_INT2_H_
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
// trim leading and trailing whitespaces from 's' ... and return by 'ref.'
void trim( std::string& s, const std::string t = " \t" ) // default whitespace: "\t "
{
size_t p1 = s.find_first_not_of( t ); // get index of 'first char' ...
if( std::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.resize( p2+1 );
}
else // ... all whitespaces or empty
s.clear();
}
std::string itostring( int i )
{
std::ostringstream oss;
oss << i;
return oss.str();
}
class BigInt
{
public:
// constructors ...
BigInt() : snum("0"), sign('+') {}
BigInt( const std::string& s ) : snum(s) { normalize(); delLeadZeros(); }
BigInt( std::string s, bool ) : snum(s) {}
BigInt( int s ) : snum( itostring(s) ) { extractNegSign(); }
BigInt operator - () const // i.e. ... flip sign of *this
{
BigInt b = *this;
if( b.snum == "0" ) { b.sign = '+'; return b; }
// else ...
b.sign = ( sign == '+' ? '-' : '+' );
return b;
}
// returns quotient and remainder ... calls div... friend function
BigInt operator / ( const BigInt& divisor ) const
{
BigInt s, remain;
if( divisor.snum == "0" )
{
s.snum = "Error! Division by ZERO is NOT defined!";;
return s;
}
if( sign == divisor.sign )
{
if( sign == '+' )
s = div_school( *this, divisor, remain );
else
s = div_school( -*this, -divisor, remain );
s.sign = '+';
}
else
{
if( sign == '-' )
s = div_school( -*this, divisor, remain );
else
s = div_school( *this, -divisor, remain );
s.sign = '-';
remain.sign = '-';
}
if( s.snum == "0" ) s.sign = '+';
if( remain.snum == "0" ) remain.sign = '+';
rnum = remain.snum;
rsign = remain.sign;
return s;
}
char getSign() const { return sign; }
void showData() const
{
int count = 0, i = snum.size();
while( i && snum[--i] == '0' ) ++count;
std::cout << "size = " << snum.size()
<< ", end zeros = " << count;
}
BigInt shift( int places )
{
if( snum != "0" )
{
if( places >= 0 )
{
if( places )
snum.resize( snum.size()+places, '0' ) ;
}
else
{
size_t p = - places;
if( snum.size() > p ) snum.resize( snum.size()-p );
else { snum = "0"; sign = '+'; }
}
}
return *this;
}
std::string get_str() const
{ if( sign == '+' ) return snum; else return '-'+snum; }
std::string get_rstr() const
{ if( rsign == '+' ) return rnum; else return '-'+rnum; }
BigInt get_remainder() const
{
BigInt tmp( rnum );
tmp.sign = rsign;
return tmp;
}
private:
std::string snum;
char sign;
static std::string rnum;
static char rsign;
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 std::ostream& operator << ( std::ostream& os, const BigInt& s )
{ return os << "("<< (s.sign == '-' ? "-" : "") << s.snum << ")"; }
// the following 'compare functions' compare ONLY 'absolute values' ...
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 false;
return a.snum >= b.snum;
}
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 false;
return a.snum > b.snum;
}
friend bool operator == ( const BigInt& a, const BigInt& b )
{
return a.snum == b.snum;
}
friend bool operator != ( const BigInt& a, const BigInt& b )
{
return a.snum != b.snum;
}
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 false;
return a.snum <= b.snum;
}
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 false;
return a.snum < b.snum;
}
friend BigInt operator + ( const BigInt& a, const BigInt& b )
{
if( a.sign == b.sign )
{
int len1 = a.snum.size(), len2 = b.snum.size(), carry = 0;
BigInt s;
if( a >= b )
{
s.snum = a.snum;
while( len2 )
{
--len1; --len2;
s.snum[len1] += b.snum[len2] - '0' + carry;
if( s.snum[len1] > 9 + '0' )
{ s.snum[len1] -= 10; carry = 1; }
else carry = 0;
}
while( len1-- && carry )
{
s.snum[len1] += carry;
if( s.snum[len1] > 9 + '0' )
{ s.snum[len1] -= 10; carry = 1; }
else carry = 0;
}
}
else
{
s.snum = b.snum;
while( len1 )
{
--len2; --len1;
s.snum[len2] += a.snum[len1] - '0' + carry;
if( s.snum[len2] > 9 + '0' )
{ s.snum[len2] -= 10; carry = 1; }
else carry = 0;
}
while( len2-- && carry )
{
s.snum[len2] += carry;
if( s.snum[len2] > 9 + '0' )
{ s.snum[len2] -= 10; carry = 1; }
else carry = 0;
}
}
if( carry )
s.snum.insert( s.snum.begin(), 1, '1' ) ;
s.sign = a.sign;
return s;
} // end if signs equal ...
// else if ... if didn't 'return' above ...
//if( a.sign == '+' ) return a - (-b);
// else ...
//return -((-a) - b);
return a - (-b);
}
friend BigInt operator - ( const BigInt& a, const BigInt& b )
{
if( a.sign == b.sign )
{
int len1 = a.snum.size(), len2 = b.snum.size(), carry = 0;
BigInt s;
if( a >= b )
{
s.snum = a.snum;
while( len2 )
{
--len1; --len2;
s.snum[len1] -= ( b.snum[len2] + carry );
if( s.snum[len1] < 0 )
{ s.snum[len1] += 10; carry = 1; }
else carry = 0;
s.snum[len1] += '0';
}
while( len1-- && carry )
{
s.snum[len1] -= carry ;
if( s.snum[len1] < '0' )
{ s.snum[len1] += 10; carry = 1; }
else carry = 0;
}
s.sign = a.sign;
s.delLeadZeros();
return s;
}
else // return -( b - a );
{
s.snum = b.snum;
while( len1 )
{
--len2; --len1;
s.snum[len2] -= ( a.snum[len1] + carry );
if( s.snum[len2] < 0 )
{ s.snum[len2] += 10; carry = 1; }
else carry = 0;
s.snum[len2] += '0';
}
while( len2-- && carry )
{
s.snum[len2] -= carry;
if( s.snum[len2] < '0' )
{ s.snum[len2] += 10; carry = 1; }
else carry = 0;
}
s.sign = b.sign;
s.delLeadZeros();
return -s;
}
}
//else if( a.sign == '+' ) return a + (-b);
//else ...
return a + (-b);
}
// NOTE! ... Here 'a' is limited to values in range -9..9
friend BigInt operator * ( int a, const BigInt& b )
{
if( a == 0 || b == BigInt() ) return BigInt(); // BigInt() is 0
BigInt s = b;
int len2 = b.snum.size();
char signA = '+';
if( a < 0 ) { a = -a; signA = '-'; }
if( a > 9 ) // NOTE! ... Here 'a' is limited to values in range -9..9
{
std::cerr << signA << a
<< " * BigInt is INVALID here ... returning 0 ... \n";
return BigInt(); // return 0 ...
}
int carry = 0;
while( len2-- )
{
s.snum[len2] -= '0';
s.snum[len2] *= a;
s.snum[len2] += carry;
if( s.snum[len2] > 9 )
{
carry = s.snum[len2]/10;
s.snum[len2] %= 10;
}
else carry = 0;
s.snum[len2] += '0';
}
if( carry )
s.snum.insert( s.snum.begin(), 1, char('0'+carry) ) ;
if( signA == b.sign ) s.sign = '+';
else s.sign = '-';
if( s.snum[0] == '0' ) s.delLeadZeros();
return s;
}
friend BigInt operator * ( const BigInt& a, const BigInt& b )
{
BigInt s; // s = 0
if( a == s || b == s ) return s;
if( a < b )
{
int len = a.snum.size();
while( len-- )
{
int m = a.snum[len]-'0';
if( m ) // skip term to add in ... if zero
{
BigInt n = m * b;
//std::string zeros( a.snum.size()-1-len, '0' );
//n.snum = n.snum + zeros;
n.snum.resize( n.snum.size() + a.snum.size()-1-len, '0' ) ;
s = s + n;
}
}
}
else // a >= b ...
{
int len = b.snum.size();
while( len-- )
{
int m = b.snum[len]-'0';
if( m ) // skip term to add in ... if zero
{
BigInt n = m * a;
//std::string zeros( b.snum.size()-1-len, '0' );
//n.snum = n.snum + zeros;
n.snum.resize( n.snum.size() + b.snum.size()-1-len, '0' ) ;
s = s + n;
}
}
}
if( a.sign == b.sign ) s.sign = '+';
else s.sign = '-';
if( s.snum[0] == '0' ) s.delLeadZeros();
return s;
}
friend BigInt div_school( const BigInt&, const BigInt& , BigInt& );
} ;
// initial static BigInt variables for remainder std::string and sign ...
std::string BigInt::rnum = "0";
char BigInt::rsign = '+';
/*
this friend function computes the quotient and remainder of two numbers ...
using the ordinary 'school taught' long-division method ...
*/
BigInt div_school( const BigInt& dividend,
const BigInt& divisor, BigInt& remain )
{
BigInt quotient;
if( divisor > dividend )
{
quotient = BigInt(); // i.e. ... 0
remain = dividend;
}
else if( divisor == dividend )
{
quotient = BigInt(1);
remain = BigInt(); // i.e. ... 0
}
else
{
int len1 = dividend.snum.size(), len2 = divisor.snum.size();
int len = len1 - len2 + 1;
quotient.snum.resize( len );
remain = BigInt( dividend.snum.substr(0, len2) );
for( int j = 0 ; j < len ; )
{
int q = 0;
while( remain >= divisor )
{
++q;
remain = remain - divisor;
}
quotient.snum[j] = '0' + q;
if( remain == BigInt() ) // if remain == 0
{
remain.snum.clear();
while( j < len && dividend.snum[len2+j] == '0' )
{
quotient.snum[++j] = '0';
}
}
remain.snum.reserve( len2 + 1 );
while
(
j < len && // 'remain < divisor' //
(
remain.snum.size() < divisor.snum.size() ||
( remain.snum.size() == divisor.snum.size() &&
remain.snum < divisor.snum )
)
)
{
remain.snum.resize( remain.snum.size()+1 ) ;
remain.snum[remain.snum.size()-1] = dividend.snum[len2+j];
quotient.snum[++j] = '0' ;
}
} // end of ... for j = 0; ...
} // end else ...
quotient.delLeadZeros();
return quotient;
}
#endif // BIG_INT2_H_
// pi_BigInt2.cpp // // this revision 2014-07-26 //
// class for large int's as std::strings with overloaded +, -, *, /
#define FNAME "myPi.txt"
#include "BigInt2.h"
#include <cstdlib> // re. system ?
#include <ctime>
#include <climits>
#include <iomanip>
// acotx = 1/x - 1/3x**3 + 1/5x**5 - 1/7x**7 + ...
BigInt acot( BigInt x, BigInt unity )
{
BigInt zero;
BigInt ssum, xpower;
ssum = xpower = unity / x;
BigInt n = 3;
int sign = -1;
int count = 0;
static int loop = 0;
std::cout << "Loop " << (++loop) << " arccot terms needed ... \n";
while( 1 )
{
xpower = xpower / (x*x);
BigInt term = xpower / n;
if( term == zero ) break;
ssum = ssum + sign * term;
sign = -sign;
n = n + 2;
count += 1;
if( count % 100 == 0 ) std::cout << std::setw(5) << count;
}
std::cout << "\nTotal arccot terms needed = " << count << std::endl;
return ssum;
}
BigInt mypi( int digits )
{
BigInt unity = 1;
unity.shift( digits + 10 );
// PI/4 <= 4*ACOT5 - ACOT239
BigInt pi = 4 * ( 4 * acot( 5, unity ) - acot(239, unity) );
return pi.shift(-10); // 10^10
}
int main()
{
int dig;
bool good = false;
while( !good )
{
std::cout << "Num of xxx decimal digits for 3.xxx pi ? " << std::flush;
if( std::cin >> dig && dig > 0 ) good = true;
else
{
std::cout << "Valid integer input only in range (1.." << INT_MAX
<< ") ...\n";
std::cin.clear();
}
std::cin.sync();
}
double t1 = clock();
BigInt pi = mypi( dig );
double t2 = clock();
std::cout << "Time was " << (t2-t1)/CLOCKS_PER_SEC << std::endl;
std::string piStr = pi.get_str();
std::cout << "piStr.length() = " << piStr.length() << std::endl;
for( int ring = 0; ring < 3; ++ring ) std::cout << "\07" << std::endl;
std::ofstream fout( FNAME /*, std::ios::app */ );
if( fout )
{
fout << "Time was " << (t2-t1)/CLOCKS_PER_SEC << ' ';
fout << "piStr.length() = " << piStr.length() << std::endl;
fout << piStr[0] << '.' << std::endl;
for( size_t i = 1; i < piStr.size(); ++i )
{
fout << piStr[i];
if( i % 100 == 0 ) fout << std::endl;
}
fout << std::endl;
fout.close();
system( FNAME );
}
else
{
std::cout << "\nThere was a problem opening file "
<< FNAME << " for output ...\n";
std::cout << "\nPress 'Enter' to "
<< "continue/EXIT PROGRAM ... "
<< std::flush;
std::cin.get();
}
}
#ifndef BIGINTVECTOR_H_ // 2012-03-06 //
#define BIGINTVECTOR_H_
#include <iostream>
#include <iomanip> // re. setfill, setw
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
const int DIG_LEN = 9;
const int TENS = 1000000000; // 9 zeros
const int NINES = TENS - 1;
bool isValidNum( const std::string& s )
{
if( !s.size() ) return false;
int stop = 0;
if( s[0] == '+' || s[0] == '-' ) stop = 1;
for( int i = s.size()-1; i >= stop; --i )
if( s[i] < '0' || s[i] > '9' )
return false;
// else ...
return true;
}
std::string getValidNum( const std::string& msg )
{
for( ; ; )
{
std::cout << msg << std::flush;
std::string line;
getline( std::cin, line );
if( isValidNum( line ) ) return line;
// else ...
std::cout << "Invalid input ...\n";
}
}
bool more()
{
std::cout << "More (y/n) ? " << std::flush;
std::string reply;
getline( std::cin, reply );
if( reply == "n" || reply =="N" ) return false;
// else ...
return true;
}
int to_int( const std::string& s )
{
std::istringstream iss( s );
int tmp;
iss >> tmp;
return tmp;
}
std::string to_string( int i )
{
std::ostringstream oss;
oss << i;
return oss.str();
}
// a - b where a and b hold an 'int' ... and a >= b pre-tested as per above ...
std::string myStrSubtract( const std::string& a, const std::string& b )
{
int len1 = a.size(), len2 = b.size(), carry = 0;
std::string s = a;
while( len2 )
{
--len1; --len2;
s[len1] -= ( b[len2] + carry );
if( s[len1] < 0 )
{ s[len1] += 10; carry = 1; }
else carry = 0;
s[len1] += '0';
}
while( len1-- && carry )
{
s[len1] -= carry ;
if( s[len1] < '0' )
{ s[len1] += 10; carry = 1; }
else carry = 0;
}
len1 = s.size()-1;
int i = 0;
while( i < len1 && s[i] == '0' ) ++i;
if( i ) s.erase( 0, i );
return s;
}
class BigInt ///////////////////// BEGIN class BigInt //////////////////////////
{
friend std::ostream& operator << ( std::ostream& os, const BigInt& b )
{
return os << to_string(b);
}
friend std::string to_plain_string( const BigInt& b )
{
std::ostringstream oss;
int blen = b.bnum.size();
std::vector< int >::const_reverse_iterator i = b.bnum.rbegin();
if( blen >= 1 ) { oss << *i; --blen; ++i; }
if( blen )
{
for( ; i != b.bnum.rend(); ++i )
oss << std::setfill( '0' ) << std::setw(DIG_LEN) << *i;
std::setfill( ' ' );
}
return oss.str();
}
friend std::string to_string( const BigInt& b )
{
if( b.sign == '+' ) return "(" + to_plain_string(b) + ")" ;
// else ...
return "(-" + to_plain_string(b) + ")" ;
}
// compares absolute values only ...
friend bool operator < ( const BigInt& a, const BigInt& b )
{
if( a.bnum.size() < b.bnum.size() ) return true;
if( a.bnum.size() > b.bnum.size() ) return false;
for( int i = a.bnum.size()-1; i >= 0; --i )
{
if( a.bnum[i] < b.bnum[i] ) return true;
if( a.bnum[i] > b.bnum[i] ) return false;
}
return false; // since equal
}
// compares absolute values only ...
friend bool operator <= ( const BigInt& a, const BigInt& b )
{
if( a.bnum.size() < b.bnum.size() ) return true;
if( a.bnum.size() > b.bnum.size() ) return false;
for( int i = a.bnum.size()-1; i >= 0; --i )
{
if( a.bnum[i] < b.bnum[i] ) return true;
if( a.bnum[i] > b.bnum[i] ) return false;
}
return true; // since equal
}
// compares absolute values only ...
friend bool operator == ( const BigInt& a, const BigInt& b )
{
if( a.bnum.size() != b.bnum.size() ) return false;
for( int i = a.bnum.size()-1; i >= 0; --i )
if( a.bnum[i] != b.bnum[i] ) return false;
return true; // since equal
}
friend BigInt operator + ( const BigInt& a, const BigInt& b )
{
int len1 = a.bnum.size(), len2 = b.bnum.size();
if( a.sign == b.sign )
{
int i, carry = 0;
if( len1 >= len2 )
{
BigInt s = a; // sum ...
for( i = 0; i < len2; ++i )
{
s.bnum[i] += b.bnum[i] + carry;
if( s.bnum[i] > NINES )
{
carry = 1;
s.bnum[i] -= TENS;
}
else carry = 0;
}
for( ; i < len1; ++i )
{
s.bnum[i] += carry;
if( s.bnum[i] > NINES )
{
carry = 1;
s.bnum[i] -= TENS;
}
else carry = 0;
if( !carry ) break;
}
if( carry ) s.bnum.push_back( carry );
return s;
}
else // len2 > len1
{
BigInt s = b; // sum ...
for( i = 0; i < len1; ++i )
{
s.bnum[i] += a.bnum[i] + carry;
if( s.bnum[i] > NINES )
{
carry = 1;
s.bnum[i] -= TENS;
}
else carry = 0;
}
for( ; i < len2; ++i )
{
s.bnum[i] += carry;
if( s.bnum[i] > NINES )
{
carry = 1;
s.bnum[i] -= TENS;
}
else carry = 0;
if( !carry ) break;
}
if( carry ) s.bnum.push_back( carry );
return s;
}
} // end if signs equal ...
// else if ... (if didn't return above) ...
//if( a.sign == '+' ) return a - (-b);
// else ...
//return -((-a) - b);
return a - (-b);
}
friend BigInt operator - ( const BigInt& a, const BigInt& b )
{
int len1 = a.bnum.size(), len2 = b.bnum.size();
if( a.sign == b.sign )
{
int i, carry = 0;
if( b < a ) // i.e. abs(b) < abs(a) ...
{
BigInt s = a; // sum ...
for( i = 0; i < len2; ++i )
{
s.bnum[i] = s.bnum[i] - b.bnum[i] + carry;
if( s.bnum[i] < 0 )
{
carry = -1;
s.bnum[i] += TENS;
}
else carry = 0;
}
for( ; i < len1; ++i )
{
s.bnum[i] += carry;
if( s.bnum[i] < 0 )
{
carry = -1;
s.bnum[i] += TENS;
}
else carry = 0;
if( !carry ) break;
}
return s.trimLeadZeros();
}
else // b >= a ...
{
BigInt s = b; // sum ...
for( i = 0; i < len1; ++i )
{
s.bnum[i] = s.bnum[i] - a.bnum[i] + carry;
if( s.bnum[i] < 0 )
{
carry = -1;
s.bnum[i] += TENS;
}
else carry = 0;
}
for( ; i < len2; ++i )
{
s.bnum[i] += carry;
if( s.bnum[i] < 0 )
{
carry = -1;
s.bnum[i] += TENS;
}
else carry = 0;
if( !carry ) break;
}
// flip sign since -(b-a) == (a-b) ...
s.sign = (s.sign == '+' ? '-' : '+' );
return s.trimLeadZeros();
}
} // end if signs equal ...
// else if ... (if didn't return above) ...
//if( a.sign == '+' ) return a + (-b);
// else ...
//return -((-a) + b);
return a + (-b);
}
friend BigInt operator * ( int a, const BigInt& b )
{
if( a == 0 || b == 0 ) return BigInt();
// abs(a) checked below if >= TENS
BigInt s;
s.bnum.clear(); // since constructed above with size 1 ...
int len2 = b.bnum.size();
s.bnum.reserve( len2+1 );
char signA = '+';
if( a < 0 ) { a = -a; signA = '-'; }
if( a >= TENS ) // now checking that 'a' is within size 'TENS' bounds
{
std::cerr << "abs(" << a << ") >= " << TENS
<< " ERROR! ... returning 0 ...\n";
return BigInt();
}
int carry = 0;
for( int i = 0; i < len2; ++i )
{
long long prod = a * (long long)b.bnum[i] + carry ;
if( prod > NINES )
{
carry = prod/TENS;
prod = prod%TENS;
}
else carry = 0;
s.bnum.push_back( prod );
}
if( carry )
s.bnum.push_back( carry );
if( signA == b.sign ) s.sign = '+';
else s.sign = '-';
return s;
}
// uses helper functions above ...
friend BigInt operator * ( const BigInt& a, const BigInt& b )
{
if( a == 0 || b == 0 ) return BigInt();
BigInt s; // initial value is zero ...
if( a < b )
{
int len1 = a.bnum.size();
for( int i = 0; i < len1; ++i )
{
int m = a.bnum[i];
if( m ) // skip term to add in ... if zero
{
BigInt n = m * b;
n.bnum.insert( n.bnum.begin(), i, 0 );
s = n + s;
}
}
}
else
{
int len1 = b.bnum.size();
for( int i = 0; i < len1; ++i )
{
int m = b.bnum[i];
if( m ) // skip term to add in ... if zero
{
BigInt n = m * a;
n.bnum.insert( n.bnum.begin(), i, 0 );
s = n + s;
}
}
}
if( a.sign == b.sign ) s.sign = '+';
else s.sign = '-';
return s;
}
friend BigInt div_school( const BigInt&, const BigInt&, BigInt& );
// returns quotient ... and finds/stores remainder ...
// (remainder NOT stored YET here)
friend BigInt operator / ( const BigInt& a, const BigInt& divisor )
{
BigInt q, remain;
if( divisor == 0 )
{
std::cout << "\nError! Division by ZERO is NOT defined!\n";
return q;
}
if( a.sign == divisor.sign )
{
if( a.sign == '+' )
q = div_school( a, divisor, remain );
else
q = div_school( -a, -divisor, remain );
q.sign = '+';
}
else
{
if( a.sign == '-' )
q = div_school( -a, divisor, remain );
else
q = div_school( a, -divisor, remain );
q.sign = '-';
//remain.sign = '-';
}
if( q == 0 ) q.sign = '+';
//if( remain.snum == "0" ) remain.sign = '+';
//q.rnum = remain.snum;
//q.rsign = remain.sign;
return q;
}
public:
BigInt() { bnum.push_back(0); sign = '+'; }
BigInt( std::string );
BigInt::BigInt( std::string s, bool fast );
BigInt( int );
BigInt operator - () const
{
BigInt tmp = *this;
tmp.sign = ( sign == '+' ? '-' : '+' );
return tmp;
}
char get_sign() const { return sign; }
size_t get_size() const { return bnum.size(); }
BigInt& trimLeadZeros();
void shift( int places )
{
if( ! places ) return;
std::string n = to_plain_string( *this );
char sav_sign = sign;
if( places > 0 )
{
//std::string add( places, '0' );
//n = n + add;
n.resize( n.size()+places, '0' );
*this = BigInt( n );
sign = sav_sign;
}
else
{
places = -places;
if( places < (int)n.size()-1 ) n.erase( n.size() - places );
else n = "0";
*this = BigInt( n );
sign = sav_sign;
}
}
private:
std::vector < int > bnum;
char sign;
} ;
BigInt& BigInt::trimLeadZeros()
{
int end = bnum.size()-1;
while( end != 0 && bnum[end] == 0 ) --end;
// now can ...
bnum.resize( ++end );
if( end == 1 && bnum[0] == 0 ) sign = '+';
return *this;
}
BigInt::BigInt( int i )
{
std::string tmp = to_string( i );
*this = BigInt( tmp );
}
BigInt::BigInt( std::string s )
{
sign = '+';
if( s[0] == '-' || s[0] == '+' )
{
sign = s[0];
s.erase(0, 1);
}
if( !isValidNum(s) )
bnum.push_back(0);
else
{
bnum.reserve( 2 + s.size()/DIG_LEN );
int count = 0 ;
for( int i = s.size()-1; i >= 0 ; --i )
{
++count;
if( count == DIG_LEN )
{
count = 0; // reset ...
bnum.push_back( to_int(s.substr(i, DIG_LEN)) );
}
}
// get last one ... if missed above ... i.e. less than 'DIG_LEN' digits
if( (int)s.size() < DIG_LEN )
bnum.push_back( to_int(s) ); // i.e. less than 1 'block'
else if( count )
bnum.push_back( to_int(s.substr(0, count)) );
trimLeadZeros();
}
}
BigInt::BigInt( std::string s, bool fast )
{
sign = '+';
bnum.reserve( 2 + s.size()/DIG_LEN );
int count = 0 ;
for( int i = s.size()-1; i >= 0 ; --i )
{
++count;
if( count == DIG_LEN )
{
count = 0; // reset ...
bnum.push_back( to_int(s.substr(i, DIG_LEN)) );
}
}
// get last one ... if missed above ... i.e. less than 'DIG_LEN' digits
if( (int)s.size() < DIG_LEN )
bnum.push_back( to_int(s) ); // i.e. less than 1 'block'
else if( count )
bnum.push_back( to_int(s.substr(0, count)) );
}
//////////////////////////////// END class BigInt //////////////////////////////
/*
this friend function computes the quotient and remainder of two numbers ...
using the ordinary 'school taught' long-division method ...
*/
BigInt div_school( const BigInt& dividend,
const BigInt& divisor, BigInt& remain )
{
std::string quotientStr, remainStr;
if( divisor < dividend )
{
std::string divisorStr = to_plain_string(divisor),
dividendStr = to_plain_string(dividend);
int j, len1 = dividendStr.size(), len2 = divisorStr.size();
int len = len1 - len2 + 1;
quotientStr.resize( len, '0' );
remainStr = dividendStr.substr(0, len2);
for( j = 0 ; j < len ; )
{
int q = 0;
while // while( remain >= divisor )
(
remainStr.size() > divisorStr.size() ||
(
remainStr.size() == divisorStr.size() &&
remainStr >= divisorStr
)
)
{
++q;
// remain = remain - divisor;
remainStr = myStrSubtract( remainStr, divisorStr );
}
quotientStr[j] = '0' + q;
if( remainStr == "0" ) // if remain == 0
{
remainStr.clear();
while( j < len && dividendStr[len2+j] == '0' )
quotientStr[++j] = '0';
}
remainStr.reserve( len2 + 1 );
while
(
j < len && // 'remain < divisor' //
(
remainStr.size() < divisorStr.size() ||
( remainStr.size() == divisorStr.size() &&
remainStr < divisorStr )
)
)
{
remainStr.resize( remainStr.size()+1 ) ;
remainStr[remainStr.size()-1] = dividendStr[len2+j];
quotientStr[++j] = '0' ;
}
} // end of ... for j = 0; ...
//quotient.delLeadZeros();
j = 0, len = quotientStr.size() - 1;
while( j < len && quotientStr[j] == '0' ) ++j;
if( j ) quotientStr.erase( 0, j );
remain = BigInt( remainStr, true );
return BigInt( quotientStr, true );
} // end else ...
if( dividend < divisor )
{
remain = dividend;
return BigInt(); // i.e. ... quotient = 0
}
//else ... divisor == dividend ... so ...
remain = BigInt(); // i.e. ... remain = 0
return BigInt(1); // i.e. quotient = 1
}
BigInt factorial( int n )
{
BigInt f(1);
for( int i = 1; i <= n; ++i )
f = f * i; // if (i * f) then 'i' is limited to int values 0..(TENS-1)
return f;
}
#endif
// pi_BigIntVector.cpp // 2012-03-06 //
// class for large int's as strings with overloaded +, -, *, /
#define FNAME "myPiVector.txt" // includes ... also <iomanip>
#include "BigIntVector.h"
#include <cstdlib> // re. system ...
#include <ctime>
#include <limits> // re. INT_MAX
// acot(x) = 1/x - 1/(3 * x^3) + 1/(5 * x^5) - 1/(7 * x^7) + ...
BigInt acot( BigInt x, BigInt unity )
{
BigInt ssum, xpower;
ssum = xpower = unity / x;
BigInt n = 3;
int sign = -1;
int count = 0;
static int loop = 0;
std::cout << "Loop " << ++loop << " arccot terms needed = \n";
while( 1 )
{
xpower = xpower / (x*x);
BigInt term = xpower / n;
if( term == BigInt() ) break;
ssum = ssum + sign * term;
sign = -sign;
n = n + 2;
count += 1;
if( count % 100 == 0 ) std::cout << std::setw(5) << count;
}
std::cout << "\nTotal arccot terms needed so far = " << count << std::endl;
return ssum;
}
BigInt mypi( int digits )
{
BigInt unity = 1;
unity.shift( digits + 10 ); // multiply by 10^(digits+10)
// PI/4 <= 4*ACOT(5) - ACOT(239)
BigInt pi = 4 * ( 4 * acot( 5, unity ) - acot(239, unity) );
pi.shift( -10 ); // divide by 10^10
return pi;
}
int main()
{
using std::cin; using std::cout; using std::flush; using std::endl;
using std::string; using std::ofstream; using std::ios;
int dig;
bool good = false;
while( !good )
{
cout << "Num of decimal digits for 3.xxx pi ? "
<< flush;
if( cin >> dig && dig > 0 & dig <= 100000 ) good = true;
else
{
cout << "Valid integer input only in range (1.." << 100000 //INT_MAX
<< ") ...\n";
cin.clear();
}
cin.sync();
}
double t1 = clock();
BigInt pi = mypi( dig );
double t2 = clock();
cout << "Time was " << (t2-t1)/CLOCKS_PER_SEC << endl;
string piStr = to_plain_string(pi);
cout << "piStr.length() = " << piStr.length() << endl;
for( int ring = 0; ring < 3; ++ring ) cout << "\07" << endl;
ofstream fout( FNAME , ios::app );
if( fout )
{
fout << "Time was " << (t2-t1)/CLOCKS_PER_SEC << ' ';
fout << "piStr.length() = " << piStr.length() << endl;
fout << piStr[0] << '.' << endl;
for( size_t i = 1; i < piStr.size(); ++i )
{
fout << piStr[i];
if( i % 100 == 0 ) fout << endl;
}
fout << endl;
fout.close();
system( "notepad " FNAME ); // compiler concatenates at compile time
}
else
{
cout << "\nPress 'Enter' to continue/EXIT PROGRAM ... " << flush;
cin.get();
}
}
// Vector2.h // // this version 2012-03-06 //
// with merge sort and insertion sort ... and added ...
// resize, pack ... and ...
// size constructor,
// copy constuctor, array constructor and overloaded operator=
#ifndef dwVECTOR_H
#define dwVECTOR_H
/* can re-set this to minimize copying and getting new memory using push_back */
#ifndef VEC_CHUNK_SIZE
#define VEC_CHUNK_SIZE 8
#endif
template < typename T >
class Vector
{
public:
Vector();
Vector( int n );
Vector( const Vector<T>& ); // copy constructor ...
Vector( const T*, const T* ); // array constructor ...
Vector<T>& operator= ( const Vector<T>& v ); // overloaded operator=
~Vector() { clear(); }
void push_back( const T& );
void reserve( int );
void resize( int );
void shrink( int );
void pack();
void clear();
T& operator [] (int i) { return ary[i]; }
const T& operator [] (int i) const { return ary[i]; }
int size() const { return _size; }
int capacity() const { return cap; }
bool get_isSorted() const { return isSorted; }
bool isSortedUp() const;
int find( T ) const; // returns index if T value present ... else -1
void erase( int ); // if int index valid, erases element there
void erase( int, int ); // if int index valid, erases n elements there
void insert( int, int, const T& );
void msort();
void isort();
void unique();
bool isUnique() const ;
private:
int cap; // capacity
int _size;
bool isSorted;
T* ary;
void enlarge(); // used by push_back
void merge( int, int, int, Vector< T >& ); // used by msort ...
void my_msort( int, int, Vector< T >& );
};
// definitions ...
template < typename T >
Vector<T>::Vector() : cap(0), _size(0), isSorted(true), ary(0) {}
template < typename T >
Vector<T>::Vector( int n ) : cap(0), _size(0), isSorted(true), ary(0)
{
if( n > 0 )
{
cap = _size = n;
if( _size > 1 ) isSorted = false;
ary = new T[size];
for( int i = 0; i < _size; ++i ) ary[i] = T(0);
}
}
template < typename T >
Vector<T>::Vector( const Vector<T> & v ) // copy constructor ...
{
cap = v.cap;
_size = v._size;
isSorted = v.isSorted;
ary = new T[cap];
for( int i = 0; i < _size; ++i ) ary[i] = v.ary[i];
}
template < typename T >
Vector<T>::Vector( const T* a, const T* b ) // array constructor ... NOTE! b is one past last element
{
_size = cap = b-a;
isSorted = false;
ary = new T[cap];
for( int i = 0; i < _size; ++i ) ary[i] = a[i];
}
template < typename T >
Vector<T>& Vector<T>::operator= ( const Vector<T>& v ) // overloaded operator=
{
if( this != &v )
{
delete [] ary;
cap = v.cap;
_size = v._size;
isSorted = v.isSorted;
ary = new T[cap];
for( int i = 0; i < _size; ++i ) ary[i] = v.ary[i];
}
return *this;
}
template < typename T >
void Vector<T>::push_back( const T& e )
{
if( _size == cap ) enlarge();
/* now add in new Rec ... */
ary[_size] = e;
++ _size;
isSorted = false;
}
// new array to hold 2x's records ... copies old to new
template < typename T >
void Vector<T>::enlarge()
{
if( cap ) cap += cap; // double capacity ...
else cap = VEC_CHUNK_SIZE; // set initial capacity
T* tmp = new T[ cap ];
for( int i = _size-1; i >= 0; --i ) tmp[i] = ary[i];
//for( int i = cap-1; i >= _size; --i ) tmp[i] = 0;
delete [] ary;
ary = tmp; // update the base address of ary
}
template < typename T >
void Vector<T>::reserve( int newCap )
{
if( newCap > cap )
{
cap = newCap;
T* tmp = new T[ cap ];
for( int i = _size-1; i >= 0; --i ) tmp[i] = ary[i];
delete [] ary;
ary = tmp; // update the base address of ary
}
}
template < typename T >
void Vector<T>::resize( int newSize )
{
if( newSize > _size )
{
reserve( newSize );
for( int i = cap-1; i >= _size; --i ) ary[i] = T(0);
_size = newSize;
isSorted = false;
}
else if( newSize < _size )
{
shrink( newSize );
//pack(); // ? //
}
}
template < typename T >
void Vector<T>::shrink( int newSize )
{
if( newSize < _size && newSize >= 0 ) _size = newSize; // leave cap unchanged
if( _size < 2 ) isSorted = true;
}
template < typename T >
void Vector<T>::pack()
{
if( _size < cap )
{
cap = _size;
T* tmp = new T[cap];
for( int i = _size-1; i >= 0; --i ) tmp[i] = ary[i];
delete [] ary;
ary = tmp; // update address ...
}
}
template < typename T >
void Vector<T>::clear()
{
if( ary != 0 )
{
delete [] ary;
cap = _size = 0;
ary = 0;
isSorted = true;
}
}
template < typename T >
int Vector<T>::find( T value ) const // returns index if present ... else -1
{
for( int i = 0; i < _size; ++i )
if( ary[i] == value ) return i;
// else if reach here ...
return -1;
}
template < typename T >
void Vector<T>::erase( int index ) // if index valid, erases element there
{
if( !size )
{
std::cout << "\nERROR! Vector empty." << std::endl;
return;
}
//else ...
if( index < 0 || index >= _size )
{
std::cout << "\nERROR! Index " << index
<< " out of range 0.." << _size-1 << std::endl;
return;
}
// else ...
for( int i = index; i < _size-1; ++i )
ary[i] = ary[i+1]; // copy each element above, down one index, so erased
// now update _size for 'this' vector object ...
-- _size;
}
template < typename T > // assumes num >= 0 and num <= _size
void Vector<T>::erase( int index, int num ) // if index valid, erases n elements there
{
if( !size )
{
std::cout << "\nERROR! Vector empty." << std::endl;
return;
}
//else ...
if( index < 0 || index >= _size )
{
std::cout << "\nERROR! Index " << index
<< " out of range 0.." << _size-1 << std::endl;
return;
}
//else ...
if( num > _size - index )
{
num = _size - index;
std::cout << "\nERROR! num to erase " << num
<< " out of range 0.." << _size-index << std::endl;
return;
}
// else ...
for( int i = index; i < _size-num; ++i )
ary[i] = ary[i+num]; // copy nth element above, down n places, so erased
// now update _size for 'this' vector object ...
_size -= num;
}
template < typename T > // assumes pos >= 0, num > 0
void Vector<T>::insert( int pos, int num, const T& val )
{
if( cap < _size + num ) reserve( _size + num ); // updates cap
if( pos > cap-num ) pos = _size;
if( pos < _size ) // shift last '_size-pos' elements up num places ....
{
int top = _size + num - 1;
for( int i = 0; i < num; ++i ) { ary[top] = ary[top-num]; --top; }
//for( int i = 0; i < num; ++ i ) ary[pos+i] = val; // insert val's
}
for( int i = 0; i < num; ++ i ) ary[pos+i] = val; // insert val's
_size += num; // update _size
}
template < typename T >
bool Vector<T>::isSortedUp() const
{
int sizeTmp = _size;
while( --sizeTmp )
if( ary[sizeTmp] < ary[sizeTmp-1] ) return false;
return true;
}
/* * * * * * * * * * * * * * merge sort / isort * * * * * * * * * * * * * * * */
template < typename T >
void Vector<T>::merge( int bot, int mid, int top, Vector<T>& tmp )
{
int sz = top - bot + 1; // _size of the range to be merged
int j = 0; // next open index in tmp
int h1 = bot; // next index to consider in the 1st half
int h2 = mid + 1; // next index to consider in the 2nd half
// while indexes h1 and h2 are not past their ends ...
while( h1 <= mid && h2 <= top )
{ // move the smaller element into the tmp vec...
if( ary[h1] < ary[h2] ) tmp[j++] = ary[h1++];
else tmp[j++] = ary[h2++];
}
// Note: only one of the two while loops below is executed ...
while( h1 <= mid ) tmp[j++] = ary[h1++]; // copy any remaining entries (1st half)
while( h2 <= top ) tmp[j++] = ary[h2++]; // copy any remaining entries (2nd half)
for( j = 0; j < sz; ++j ) ary[bot+j] = tmp[j]; // copy back sorted tmp vec...
}
template < typename T >
void Vector<T>::my_msort( int bot, int top, Vector& tmp )
{
if( bot == top ) return;
else
{
int mid = ( bot + top ) / 2;
my_msort( bot, mid, tmp ); // sort the first ...
my_msort( mid + 1, top, tmp ); // and the second half ...
merge( bot, mid, top, tmp ); // now merge these 2 sorted chunks
}
}
template < typename T >
void Vector<T>::msort()
{
if( isSorted ) return;
if( _size > 1 )
{
Vector<T> tmp;
tmp.reserve( _size );
my_msort( 0, _size-1, tmp );
isSorted = true;
}
}
template < typename T >
void Vector<T>::isort()
{
if( isSorted ) return;
// start with an array of just the first 2 elements (if exists)
for( int i = 1; i < _size; ++i )
{
T cmp = ary[i]; // get copy of this new cmp element on each outer loop
int j = i-1; // get index of element just to the left of the above 'cmp'
// to start comparisons
while( j >= 0 && cmp < ary[j] )
{
ary[j+1] = ary[j]; // copy element 'up' ...
--j; // decrement j in preparation for next inner loop
}
ary[j+1] = cmp; // insert element at index j+1 (since j was decremented above)
}
isSorted = true;
}
/* * * * * * * * * * * * * * merge sort / isort * * * * * * * * * * * * * * * */
template < typename T >
void Vector<T>::unique()
{
if( !isSorted ) msort();
int i = 0;
for( int j = 1; j < _size ; ++j )
{
if( ary[i] != ary[j] )
{
++i;
if( i != j ) ary[i] = ary[j];
}
}
_size = ++i;
}
template < typename T >
bool Vector<T>::isUnique() const
{
if( !isSorted ) msort();
for( int i = _size-1; i > 0; --i )
if( ary[i] == ary[i-1] ) return false;
// else ...
return true;
}
#endif
#ifndef BIGINTVECTOR_H_ // 2012-03-06 //
#define BIGINTVECTOR_H_
#include <iostream>
#include <iomanip> // re. setfill, setw
#include <sstream>
#include <fstream>
#include <string>
#include "vector2.h"
const int DIG_LEN = 9;
const int TENS = 1000000000; // 9 zeros
const int NINES = TENS - 1;
bool isValidNum( const std::string& s )
{
if( !s.size() ) return false;
int stop = 0;
if( s[0] == '+' || s[0] == '-' ) stop = 1;
for( int i = s.size()-1; i >= stop; --i )
if( s[i] < '0' || s[i] > '9' )
return false;
// else ...
return true;
}
std::string getValidNum( const std::string& msg )
{
for( ; ; )
{
std::cout << msg << std::flush;
std::string line;
getline( std::cin, line );
if( isValidNum( line ) ) return line;
// else ...
std::cout << "Invalid input ...\n";
}
}
bool more()
{
std::cout << "More (y/n) ? " << std::flush;
std::string reply;
getline( std::cin, reply );
if( reply == "n" || reply =="N" ) return false;
// else ...
return true;
}
int to_int( const std::string& s )
{
std::istringstream iss( s );
int tmp;
iss >> tmp;
return tmp;
}
std::string to_string( int i )
{
std::ostringstream oss;
oss << i;
return oss.str();
}
// a - b where a and b hold an 'int' ... and a >= b pre-tested as per above ...
std::string myStrSubtract( const std::string& a, const std::string& b )
{
int len1 = a.size(), len2 = b.size(), carry = 0;
std::string s = a;
while( len2 )
{
--len1; --len2;
s[len1] -= ( b[len2] + carry );
if( s[len1] < 0 )
{ s[len1] += 10; carry = 1; }
else carry = 0;
s[len1] += '0';
}
while( len1-- && carry )
{
s[len1] -= carry ;
if( s[len1] < '0' )
{ s[len1] += 10; carry = 1; }
else carry = 0;
}
len1 = s.size()-1;
int i = 0;
while( i < len1 && s[i] == '0' ) ++i;
if( i ) s.erase( 0, i );
return s;
}
class BigInt ///////////////////// BEGIN class BigInt //////////////////////////
{
friend std::ostream& operator << ( std::ostream& os, const BigInt& b )
{
return os << to_string(b);
}
friend std::string to_plain_string( const BigInt& b )
{
std::ostringstream oss;
int i = b.bnum.size() - 1;
if( i >= 0 ) { oss << b.bnum[i]; --i; }
if( i >= 0 )
{
for( ; i >= 0 ; --i )
oss << std::setfill( '0' ) << std::setw(DIG_LEN) << b.bnum[i];
std::setfill( ' ' );
}
return oss.str();
}
friend std::string to_string( const BigInt& b )
{
if( b.sign == '+' ) return "(" + to_plain_string(b) + ")" ;
// else ...
return "(-" + to_plain_string(b) + ")" ;
}
// compares absolute values only ...
friend bool operator < ( const BigInt& a, const BigInt& b )
{
if( a.bnum.size() < b.bnum.size() ) return true;
if( a.bnum.size() > b.bnum.size() ) return false;
for( int i = a.bnum.size()-1; i >= 0; --i )
{
if( a.bnum[i] < b.bnum[i] ) return true;
if( a.bnum[i] > b.bnum[i] ) return false;
}
return false; // since equal
}
// compares absolute values only ...
friend bool operator <= ( const BigInt& a, const BigInt& b )
{
if( a.bnum.size() < b.bnum.size() ) return true;
if( a.bnum.size() > b.bnum.size() ) return false;
for( int i = a.bnum.size()-1; i >= 0; --i )
{
if( a.bnum[i] < b.bnum[i] ) return true;
if( a.bnum[i] > b.bnum[i] ) return false;
}
return true; // since equal
}
// compares absolute values only ...
friend bool operator == ( const BigInt& a, const BigInt& b )
{
if( a.bnum.size() != b.bnum.size() ) return false;
for( int i = a.bnum.size()-1; i >= 0; --i )
if( a.bnum[i] != b.bnum[i] ) return false;
return true; // since equal
}
friend BigInt operator + ( const BigInt& a, const BigInt& b )
{
int len1 = a.bnum.size(), len2 = b.bnum.size();
if( a.sign == b.sign )
{
int i, carry = 0;
if( len1 >= len2 )
{
BigInt s = a; // sum ...
for( i = 0; i < len2; ++i )
{
s.bnum[i] += b.bnum[i] + carry;
if( s.bnum[i] > NINES )
{
carry = 1;
s.bnum[i] -= TENS;
}
else carry = 0;
}
for( ; i < len1; ++i )
{
s.bnum[i] += carry;
if( s.bnum[i] > NINES )
{
carry = 1;
s.bnum[i] -= TENS;
}
else carry = 0;
if( !carry ) break;
}
if( carry ) s.bnum.push_back( carry );
return s;
}
else // len2 > len1
{
BigInt s = b; // sum ...
for( i = 0; i < len1; ++i )
{
s.bnum[i] += a.bnum[i] + carry;
if( s.bnum[i] > NINES )
{
carry = 1;
s.bnum[i] -= TENS;
}
else carry = 0;
}
for( ; i < len2; ++i )
{
s.bnum[i] += carry;
if( s.bnum[i] > NINES )
{
carry = 1;
s.bnum[i] -= TENS;
}
else carry = 0;
if( !carry ) break;
}
if( carry ) s.bnum.push_back( carry );
return s;
}
} // end if signs equal ...
// else if ... (if didn't return above) ...
//if( a.sign == '+' ) return a - (-b);
// else ...
//return -((-a) - b);
return a - (-b);
}
friend BigInt operator - ( const BigInt& a, const BigInt& b )
{
int len1 = a.bnum.size(), len2 = b.bnum.size();
if( a.sign == b.sign )
{
int i, carry = 0;
if( b < a ) // i.e. abs(b) < abs(a) ...
{
BigInt s = a; // sum ...
for( i = 0; i < len2; ++i )
{
s.bnum[i] = s.bnum[i] - b.bnum[i] + carry;
if( s.bnum[i] < 0 )
{
carry = -1;
s.bnum[i] += TENS;
}
else carry = 0;
}
for( ; i < len1; ++i )
{
s.bnum[i] += carry;
if( s.bnum[i] < 0 )
{
carry = -1;
s.bnum[i] += TENS;
}
else carry = 0;
if( !carry ) break;
}
return s.trimLeadZeros();
}
else // b >= a ...
{
BigInt s = b; // sum ...
for( i = 0; i < len1; ++i )
{
s.bnum[i] = s.bnum[i] - a.bnum[i] + carry;
if( s.bnum[i] < 0 )
{
carry = -1;
s.bnum[i] += TENS;
}
else carry = 0;
}
for( ; i < len2; ++i )
{
s.bnum[i] += carry;
if( s.bnum[i] < 0 )
{
carry = -1;
s.bnum[i] += TENS;
}
else carry = 0;
if( !carry ) break;
}
// flip sign since -(b-a) == (a-b) ...
s.sign = (s.sign == '+' ? '-' : '+' );
return s.trimLeadZeros();
}
} // end if signs equal ...
// else if ... (if didn't return above) ...
//if( a.sign == '+' ) return a + (-b);
// else ...
//return -((-a) + b);
return a + (-b);
}
friend BigInt operator * ( int a, const BigInt& b )
{
if( a == 0 || b == 0 ) return BigInt();
// abs(a) checked below if >= TENS
BigInt s;
s.bnum.clear(); // since constructed above with size 1 ...
int len2 = b.bnum.size();
s.bnum.reserve( len2+1 );
char signA = '+';
if( a < 0 ) { a = -a; signA = '-'; }
if( a >= TENS ) // now checking that 'a' is within size 'TENS' bounds
{
std::cerr << "abs(" << a << ") >= " << TENS
<< " ERROR! ... returning 0 ...\n";
return BigInt();
}
int carry = 0;
for( int i = 0; i < len2; ++i )
{
long long prod = a * (long long)b.bnum[i] + carry ;
if( prod > NINES )
{
carry = prod/TENS;
prod = prod%TENS;
}
else carry = 0;
s.bnum.push_back( prod );
}
if( carry )
s.bnum.push_back( carry );
if( signA == b.sign ) s.sign = '+';
else s.sign = '-';
return s;
}
// uses helper functions above ...
friend BigInt operator * ( const BigInt& a, const BigInt& b )
{
if( a == 0 || b == 0 ) return BigInt();
BigInt s; // initial value is zero ...
if( a < b )
{
int len1 = a.bnum.size();
for( int i = 0; i < len1; ++i )
{
int m = a.bnum[i];
if( m ) // skip term to add in ... if zero
{
BigInt n = m * b;
n.bnum.insert( 0, i, 0 );
s = n + s;
}
}
}
else
{
int len1 = b.bnum.size();
for( int i = 0; i < len1; ++i )
{
int m = b.bnum[i];
if( m ) // skip term to add in ... if zero
{
BigInt n = m * a;
n.bnum.insert( 0, i, 0 );
s = n + s;
}
}
}
if( a.sign == b.sign ) s.sign = '+';
else s.sign = '-';
return s;
}
friend BigInt div_school( const BigInt&, const BigInt&, BigInt& );
// returns quotient ... and finds/stores remainder ...
// (remainder NOT stored YET here)
friend BigInt operator / ( const BigInt& a, const BigInt& divisor )
{
BigInt q, remain;
if( divisor == 0 )
{
std::cout << "\nError! Division by ZERO is NOT defined!\n";
return q;
}
if( a.sign == divisor.sign )
{
if( a.sign == '+' )
q = div_school( a, divisor, remain );
else
q = div_school( -a, -divisor, remain );
q.sign = '+';
}
else
{
if( a.sign == '-' )
q = div_school( -a, divisor, remain );
else
q = div_school( a, -divisor, remain );
q.sign = '-';
//remain.sign = '-';
}
if( q == 0 ) q.sign = '+';
//if( remain.snum == "0" ) remain.sign = '+';
//q.rnum = remain.snum;
//q.rsign = remain.sign;
return q;
}
public:
BigInt() { bnum.push_back(0); sign = '+'; }
BigInt( std::string );
BigInt::BigInt( std::string s, bool fast );
BigInt( int );
BigInt operator - () const
{
BigInt tmp = *this;
tmp.sign = ( sign == '+' ? '-' : '+' );
return tmp;
}
char get_sign() const { return sign; }
size_t get_size() const { return bnum.size(); }
BigInt& trimLeadZeros();
void shift( int places )
{
if( ! places ) return;
std::string n = to_plain_string( *this );
char sav_sign = sign;
if( places > 0 )
{
//std::string add( places, '0' );
//n = n + add;
n.resize( n.size()+places, '0' );
*this = BigInt( n );
sign = sav_sign;
}
else
{
places = -places;
if( places < (int)n.size()-1 ) n.erase( n.size() - places );
else n = "0";
*this = BigInt( n );
sign = sav_sign;
}
}
private:
Vector < int > bnum;
char sign;
} ;
BigInt& BigInt::trimLeadZeros()
{
int end = bnum.size()-1;
while( end != 0 && bnum[end] == 0 ) --end;
// now can ...
bnum.resize( ++end );
if( end == 1 && bnum[0] == 0 ) sign = '+';
return *this;
}
BigInt::BigInt( int i )
{
std::string tmp = to_string( i );
*this = BigInt( tmp );
}
BigInt::BigInt( std::string s )
{
sign = '+';
if( s[0] == '-' || s[0] == '+' )
{
sign = s[0];
s.erase(0, 1);
}
if( !isValidNum(s) )
bnum.push_back(0);
else
{
bnum.reserve( 2 + s.size()/DIG_LEN );
int count = 0 ;
for( int i = s.size()-1; i >= 0 ; --i )
{
++count;
if( count == DIG_LEN )
{
count = 0; // reset ...
bnum.push_back( to_int(s.substr(i, DIG_LEN)) );
}
}
// get last one ... if missed above ... i.e. less than 'DIG_LEN' digits
if( (int)s.size() < DIG_LEN )
bnum.push_back( to_int(s) ); // i.e. less than 1 'block'
else if( count )
bnum.push_back( to_int(s.substr(0, count)) );
trimLeadZeros();
}
}
BigInt::BigInt( std::string s, bool fast )
{
sign = '+';
bnum.reserve( 2 + s.size()/DIG_LEN );
int count = 0 ;
for( int i = s.size()-1; i >= 0 ; --i )
{
++count;
if( count == DIG_LEN )
{
count = 0; // reset ...
bnum.push_back( to_int(s.substr(i, DIG_LEN)) );
}
}
// get last one ... if missed above ... i.e. less than 'DIG_LEN' digits
if( (int)s.size() < DIG_LEN )
bnum.push_back( to_int(s) ); // i.e. less than 1 'block'
else if( count )
bnum.push_back( to_int(s.substr(0, count)) );
}
//////////////////////////////// END class BigInt //////////////////////////////
/*
this friend function computes the quotient and remainder of two numbers ...
using the ordinary 'school taught' long-division method ...
*/
BigInt div_school( const BigInt& dividend,
const BigInt& divisor, BigInt& remain )
{
std::string quotientStr, remainStr;
if( divisor < dividend )
{
std::string divisorStr = to_plain_string(divisor),
dividendStr = to_plain_string(dividend);
int j, len1 = dividendStr.size(), len2 = divisorStr.size();
int len = len1 - len2 + 1;
quotientStr.resize( len, '0' );
remainStr = dividendStr.substr(0, len2);
for( j = 0 ; j < len ; )
{
int q = 0;
while // while( remain >= divisor )
(
remainStr.size() > divisorStr.size() ||
(
remainStr.size() == divisorStr.size() &&
remainStr >= divisorStr
)
)
{
++q;
// remain = remain - divisor;
remainStr = myStrSubtract( remainStr, divisorStr );
}
quotientStr[j] = '0' + q;
if( remainStr == "0" ) // if remain == 0
{
remainStr.clear();
while( j < len && dividendStr[len2+j] == '0' )
quotientStr[++j] = '0';
}
remainStr.reserve( len2 + 1 );
while
(
j < len && // 'remain < divisor' //
(
remainStr.size() < divisorStr.size() ||
( remainStr.size() == divisorStr.size() &&
remainStr < divisorStr )
)
)
{
remainStr.resize( remainStr.size()+1 ) ;
remainStr[remainStr.size()-1] = dividendStr[len2+j];
quotientStr[++j] = '0' ;
}
} // end of ... for j = 0; ...
//quotient.delLeadZeros();
j = 0, len = quotientStr.size() - 1;
while( j < len && quotientStr[j] == '0' ) ++j;
if( j ) quotientStr.erase( 0, j );
remain = BigInt( remainStr, true );
return BigInt( quotientStr, true );
} // end else ...
if( dividend < divisor )
{
remain = dividend;
return BigInt(); // i.e. ... quotient = 0
}
//else ... divisor == dividend ... so ...
remain = BigInt(); // i.e. ... remain = 0
return BigInt(1); // i.e. quotient = 1
}
BigInt factorial( int n )
{
BigInt f(1);
for( int i = 1; i <= n; ++i )
f = f * i; // if (i * f) then 'i' is limited to int values 0..(TENS-1)
return f;
}
#endif