Big Numbers ... Big Int (Integers) ... via a C++ class

[David]

Here is a first step to handle addition and multiplication of non-negative Big integers ...

Note: this is a simple 'first go' ... that just uses some of the power and ease of the C++ STL string.  I may later upgrade this to a more memory efficent approach using the STL vector container to hold as many unsigned long numbers as required ... beside tracking the sign of the number.

Code:

// classStrInt.cpp // start of class for ... large int's as strings //

#include <iostream>
#include <fstream>
#include <sstream>
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 a )
{
    ostringstream oss;
    oss << a;
    return oss.str();
}

class StrInt
{
public:
    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();
            for( int i = a.snum.size()-1-len1; i > 0; --i )
                n = 10*n;
            s = s + n;
        }

        return s;
    }

    StrInt( string s = "0" ) : snum(s) { normalize(); }
    StrInt( int s ) : snum( itostring(s) ) {}
   
    void showData()
    {
        int i = snum.size();
        int j = i-1;
        while( snum[j]=='0' ) --j;
        cout << "size = " << i << ", end zeros = " <<  i-1-j;
    }
   
private:
    string snum;
    void normalize()
    {
        trim( snum ); // trim off all leading and trailing whitespaces ...
       
        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; }
           
        // erase leading zeros ... but NOT last zero
        int i = 0;
        while( i < len-1 && snum[i] == '0' ) ++i;
        snum.erase( 0, i );
    }
};

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 < 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 ...
    for( int i = 1; i < 501; ++i )
    {
        StrInt s3(i);
        s1 = s3*s1;
        cout << "Factorial("<< i << ")=\n" << s1 << " ";
        s1.showData(); cout << endl;
        //cin.get();
    }

    cout << "Press 'Enter' to exit ... " << flush;
    cin.get();

}

You may like to also look here to see more comments to the addition code ...

http://www.dreamincode.net/forums/topic/189261-dividing-large-numbers-using-strings/page__view__findpost__p__1109449

[David]

Next ... we expand the class to handle negative Big Integers ...

Code:

// classStrIntNeg.cpp // class for large int's as strings (handles neg int's) //

#include <iostream>
#include <fstream>
#include <sstream>
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();
}

class StrInt
{
public:
    friend ostream& operator << ( ostream& os, const StrInt& s )
    { return os << "("<< (s.sign == '-' ? "-" : "") << s.snum << ")"; }

    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;
        }
       
        else if( a >= b )
        {
            if( a.sign == '+' ) return a - (-b);
            else return -((-a) - b);
        }
        else
        {
            if( b.sign == '+' ) return b - (-a);
            else return -((-b) - a);
        }
    }

    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);
    }

    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 aa, bb;
        if( a >= b ) { aa = b; bb = a; }
        else { aa = a; bb = b; }
        int len1 = aa.snum.size();
        StrInt s; // initial value is zero ...
        while( len1-- )
        {
            StrInt n = (aa.snum[len1]-'0') * bb;
            n.delLeadZeros();
            /*
            for( int i = aa.snum.size()-1-len1; i > 0; --i )
                n = 10*n;
            */
            string zeros(aa.snum.size()-1-len1, '0');
            n.snum += zeros; // shift left ... before adding ...
           
            s = s + n;
        }
        if( aa.sign == bb.sign ) s.sign = '+';
        else s.sign = '-';
       
        if( s.snum == "0" ) s.sign = '+';
        return s;
    }

    StrInt( string s = "0" ) : snum(s) { normalize(); delLeadZeros(); }
    StrInt( int s ) : snum( itostring(s) ) { normalize(); }

    void showData()
    {
        int i = snum.size();
        int j = i-1;
        while( snum[j]=='0' ) --j;
        cout << i << " digits and " << i-1-j << " end zeros";
    }
   
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; }
    }
    // erase leading zeros ... but NOT last zero
    void delLeadZeros()
    {
        int i = 0;
        int len = snum.size();
        while( i < len-1 && snum[i] == '0' ) ++i;
        snum.erase( 0, i );
        if( snum == "0" ) sign = '+';
    }
};

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 <= 200; ++i )
    {
        StrInt s3(i);
        s1 = s1*s3;
        cout << "Factorial("<< i << ") <with ";
        s1.showData();
        cout << "> is " << endl;
        cout << s1 << endl << endl;
        //cin.get();
    }

    cout << "Press 'Enter' to exit ... " << flush;
    cin.get();

}

[David]

Next ... class expanded to permit division of Big Integers ...

Code:

// classStrIntNegDiv.cpp // class for large int's as strings (with division) //

#include <iostream>
#include <fstream>
#include <sstream>
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();
}

struct QuoRem; // prototype ...

/*  note these 3 globals used here ... */
// int dividend, divisor, remain;

class StrInt
{
public:
    friend ostream& operator << ( ostream& os, const StrInt& s )
    { return os << "("<< (s.sign == '-' ? "-" : "") << s.snum << ")"; }

    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 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 bool operator == ( const StrInt& a, const StrInt& b )
    {
        if( a.snum == b.snum ) return true;
        return false;
    }
    friend bool operator != ( const StrInt& a, const StrInt& b )
    {
        if( a.snum != b.snum ) return true;
        return false;
    }
    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 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;
        }
       
        else if( a >= b )
        {
            if( a.sign == '+' ) return a - (-b);
            else return -((-a) - b);
        }
        else
        {
            if( b.sign == '+' ) return b - (-a);
            else return -((-b) - a);
        }
    }

    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);
    }

    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 aa, bb;
        if( a >= b ) { aa = b; bb = a; }
        else { aa = a; bb = b; }
        int len1 = aa.snum.size();
        StrInt s; // initial value is zero ...
        while( len1-- )
        {
            StrInt n = (aa.snum[len1]-'0') * bb;
            n.delLeadZeros();
            /*
            for( int i = aa.snum.size()-1-len1; i > 0; --i )
                n = 10*n;
            */
            string zeros(aa.snum.size()-1-len1, '0');
            n.snum += zeros; // shift left ... before adding ...
           
            s = s + n;
        }
        if( aa.sign == bb.sign ) s.sign = '+';
        else s.sign = '-';
       
        if( s.snum == "0" ) s.sign = '+';
        return s;
    }

    friend StrInt division( StrInt dividend, StrInt divisor, StrInt& remain );
    friend QuoRem operator / ( const StrInt& dividend, const StrInt& divisor );

    StrInt( string s = "0" ) : snum(s) { normalize(); delLeadZeros(); }
    StrInt( int s ) : snum( itostring(s) ) { normalize(); }
   
    char get_sign() { return sign; }

    void showData()
    {
        int i = snum.size();
        int j = i-1;
        while( snum[j]=='0' ) --j;
        cout << i << " digits and " << i-1-j << " end zeros";
    }
   
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; }
    }
    // erase leading zeros ... but NOT last zero
    void delLeadZeros()
    {
        int i = 0;
        int len = snum.size();
        while( i < len-1 && snum[i] == '0' ) ++i;
        snum.erase( 0, i );
        if( snum == "0" ) sign = '+';
    }
};

struct QuoRem
{
    StrInt quo;
    StrInt rem;
};


/*
    get_quotient function computes the quotient and ...
    remainder of two numbers ... using "a type of 'bit' shifting"
*/
StrInt division( StrInt dividend, StrInt divisor, StrInt& remain )
{
    StrInt quotient(1);

    if( divisor > dividend )
    {
        quotient = StrInt(0);
        remain = dividend;
    }
    else if( divisor == dividend )
    {
        /* quotient = StrInt(1); */
        remain = StrInt(0);
    }
    else
    {
        StrInt tmp_divisor = divisor;
        while( tmp_divisor <= dividend )
        {
            /*
                Here divisor <= dividend, therefore ...
                left shift (i.e. multiply by 2) ...  divisor and quotient
            */
            tmp_divisor = tmp_divisor + tmp_divisor;
            quotient = quotient + 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;
        tmp_divisor.snum.erase(tmp_divisor.snum.size()-1); // divide by 10
        quotient.snum.erase(quotient.snum.size()-1);

        /*
            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 struc QuoRem ...
QuoRem operator / ( const StrInt& dividend, const StrInt& divisor )
{
    QuoRem qr;
    if( divisor.snum == "0" )
    {
        qr.quo.snum = "Error! Division by ZERO is NOT defined!";;
        return qr;
    }
   
    StrInt s, remain;
    if( dividend.sign == divisor.sign )
    {
        if( dividend.sign == '+' )
            s = division( dividend, divisor, remain );
        else
            s = division( -dividend, -divisor, remain );

        s.sign = '+';
    }
    else
    {
        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()
{
    StrInt s1( "+0009876543210987654" );
    //StrInt s2;
    StrInt s2( "-0001234567890123456" );
    StrInt s3;
   
    QuoRem qr; // to hold quotient and remainder for division returned values
   
    do
    {
        qr = s1/s2;
        cout << s1 << "/" << s2 << "=" << qr.quo << ", remainder="
             << qr.rem << endl;

        if( qr.rem.get_sign() == '-' ) // i.e. signs different ...
        {
            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;
        }
        else
        {
            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;
        }

        QuoRem qr2 = s2 / StrInt(123);
        s2 = qr2.quo;
    }
    while( s2 != StrInt(0) );

    s2 = StrInt( "+0001234567890123456" ); // reset ...

    cout << "Press 'Enter' to continue ... " << flush;
    cin.get();
    cout << endl;

    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;
   
    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;
       
    cout << endl;

    // testing multiplying 2 StrInt's ...
    cout << s1 << "*" << s2 << "=" << s1*s2 << endl;
    cout << s2 << "*" << s1 << "=" << s2*s1 << endl;

    cout << endl;

    s1 = -s1;
    // 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 continue ... " << flush;
    cin.get();
   
    s1 = StrInt(1);
    // testing multiplying 2 StrInt's ... (and find factorial) ...
    for( int i = 1; i <= 200; ++i )
    {
        StrInt s3(i);
        s1 = s1*s3;
        cout << "Factorial("<< i << ") <with ";
        s1.showData();
        cout << "> is " << endl;
        cout << s1 << endl << endl;
        //cin.get();
    }

    cout << "Press 'Enter' to EXIT PROGRAM ... " << flush;
    cin.get();

}

/*

sample output for division ...

(9876543210987654)/(1234567890123456)=(8), remainder=(90000006)
(8)*(1234567890123456)+(90000006)=(9876543210987654)

(9876543210987654)/(10037137318076)=(984), remainder=(90000870)
(984)*(10037137318076)+(90000870)=(9876543210987654)

(9876543210987654)/(81602742423)=(121032), remainder=(90047118)
(121032)*(81602742423)+(90047118)=(9876543210987654)

(9876543210987654)/(663436930)=(14886936), remainder=(94041174)
(14886936)*(663436930)+(94041174)=(9876543210987654)

(9876543210987654)/(5393796)=(1831093206), remainder=(837678)
(1831093206)*(5393796)+(837678)=(9876543210987654)

(9876543210987654)/(43852)=(225224464357), remainder=(4490)
(225224464357)*(43852)+(4490)=(9876543210987654)

(9876543210987654)/(356)=(27743098907268), remainder=(246)
(27743098907268)*(356)+(246)=(9876543210987654)

(9876543210987654)/(2)=(4938271605493827), remainder=(0)
(4938271605493827)*(2)+(0)=(9876543210987654)

Press 'Enter' to continue ...

(-9876543210987654)/(-1234567890123456)=(8), remainder=(90000006)
(8)*(-1234567890123456)-(90000006)=(-9876543210987654)

(-9876543210987654)/(-10037137318076)=(984), remainder=(90000870)
(984)*(-10037137318076)-(90000870)=(-9876543210987654)

(-9876543210987654)/(-81602742423)=(121032), remainder=(90047118)
(121032)*(-81602742423)-(90047118)=(-9876543210987654)

(-9876543210987654)/(-663436930)=(14886936), remainder=(94041174)
(14886936)*(-663436930)-(94041174)=(-9876543210987654)

(-9876543210987654)/(-5393796)=(1831093206), remainder=(837678)
(1831093206)*(-5393796)-(837678)=(-9876543210987654)

(-9876543210987654)/(-43852)=(225224464357), remainder=(4490)
(225224464357)*(-43852)-(4490)=(-9876543210987654)

(-9876543210987654)/(-356)=(27743098907268), remainder=(246)
(27743098907268)*(-356)-(246)=(-9876543210987654)

(-9876543210987654)/(-2)=(4938271605493827), remainder=(0)
(4938271605493827)*(-2)-(0)=(-9876543210987654)

Press 'Enter' to continue ...

(-9876543210987654)/(1234567890123456)=(-8), remainder=(-90000006)
(-8)*(1234567890123456)+(-90000006)=(-9876543210987654)

(-9876543210987654)/(10037137318076)=(-984), remainder=(-90000870)
(-984)*(10037137318076)+(-90000870)=(-9876543210987654)

(-9876543210987654)/(81602742423)=(-121032), remainder=(-90047118)
(-121032)*(81602742423)+(-90047118)=(-9876543210987654)

(-9876543210987654)/(663436930)=(-14886936), remainder=(-94041174)
(-14886936)*(663436930)+(-94041174)=(-9876543210987654)

(-9876543210987654)/(5393796)=(-1831093206), remainder=(-837678)
(-1831093206)*(5393796)+(-837678)=(-9876543210987654)

(-9876543210987654)/(43852)=(-225224464357), remainder=(-4490)
(-225224464357)*(43852)+(-4490)=(-9876543210987654)

(-9876543210987654)/(356)=(-27743098907268), remainder=(-246)
(-27743098907268)*(356)+(-246)=(-9876543210987654)

(-9876543210987654)/(2)=(-4938271605493827), remainder=(0)
(-4938271605493827)*(2)+(0)=(-9876543210987654)

Press 'Enter' to continue ...

(9876543210987654)/(-1234567890123456)=(-8), remainder=(-90000006)
(-8)*(-1234567890123456)-(-90000006)=(9876543210987654)

(9876543210987654)/(-10037137318076)=(-984), remainder=(-90000870)
(-984)*(-10037137318076)-(-90000870)=(9876543210987654)

(9876543210987654)/(-81602742423)=(-121032), remainder=(-90047118)
(-121032)*(-81602742423)-(-90047118)=(9876543210987654)

(9876543210987654)/(-663436930)=(-14886936), remainder=(-94041174)
(-14886936)*(-663436930)-(-94041174)=(9876543210987654)

(9876543210987654)/(-5393796)=(-1831093206), remainder=(-837678)
(-1831093206)*(-5393796)-(-837678)=(9876543210987654)

(9876543210987654)/(-43852)=(-225224464357), remainder=(-4490)
(-225224464357)*(-43852)-(-4490)=(9876543210987654)

(9876543210987654)/(-356)=(-27743098907268), remainder=(-246)
(-27743098907268)*(-356)-(-246)=(9876543210987654)

(9876543210987654)/(-2)=(-4938271605493827), remainder=(0)
(-4938271605493827)*(-2)-(0)=(9876543210987654)

Press 'Enter' to continue ...

*/