1 Replies - 1213 Views - Last Post: 07 March 2012 - 12:18 AM

#1 David W  Icon User is offline

  • DIC supporter
  • member icon

Reputation: 298
  • View blog
  • Posts: 1,839
  • Joined: 20-September 08

structBigIntNeg.cpp

Posted 09 September 2010 - 10:16 PM

Description: see program and comments ...a start of a struct to handle large int's as strings ... this version does subtraction by adding with the 9's complement
// structBigIntNeg.cpp // this ver 2010-09-10 //
// a start of a struct to handle large int's as strings ...
// this version does subtraction by adding with the 9's complement

// http://en.wikipedia.org/wiki/Method_of_complements // re. subtracting ...
// 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>

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( string s = "0" ) : snum(s)
    { trim(snum); getSign(); validate(); delLeadZeros(); }
    BigInt( int s ) : snum( itostring(s) ) { getSign(); }
    
    void getSign()
    {
        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; }
    }
    BigInt 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 = '+';
        return (*this); // return this object ...
    }

    void showData()
    {
        int i = snum.size();
        int j = i-1; // j is the index of the last character in the string
        while( snum[j]=='0' )  --j; // count place-holder zeros at end ...
        cout << "number of digits = " << i << ", end zeros = " <<  i-1-j;
    }
};

// overloaded operators ... and functions ...
ostream& operator << ( ostream& os, const BigInt& bi )
{
    return os << "(" << (bi.sign=='+' ? "" : "-") << bi.snum << ")";
}

// compares absolute values only ...
bool operator > ( const BigInt& a, const BigInt& b )
{
    int len1 = a.snum.size();
    int len2 = b.snum.size();
    if( len1 > len2 ) return true;
    if( len1 == len2 ) return a.snum > b.snum;
    return false;
}

char sumof( const BigInt& a, int len1, const BigInt& 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 );
}
char sumof( const BigInt& 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 );
}

// 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 functions above ...
BigInt operator + ( const BigInt& a, const BigInt& b )
{
    if( a.sign == b.sign )
    {
        int carry = 0;
        int len1 = a.snum.size();
        int len2 = b.snum.size();
        int ml = (len1 > len2 ? len1 : len2);
        BigInt s;
        s.snum.resize( ml );
        s.sign = a.sign;

        while( len1 && len2 )
            s.snum[--ml] = sumof( a, --len1, b, --len2, carry );

        if( len1 )
            while( len1 )
                s.snum[--ml] = sumof( a, --len1, carry );
        else
            while( len2 )
                s.snum[--ml] = sumof( b, --len2, carry );

        if( carry )
            s.snum = "1" + s.snum;

        return s;
    }
    // else signs are different ...
    if( a.sign == '+' ) return ( a - (-b) ).delLeadZeros();
    // else a.sign is '-' ... so ...
    return ( -( (-a) - b ) ).delLeadZeros();
}


// get 'neg value' ... i.e. switch sign
BigInt operator - ( const BigInt& a )
{
    BigInt n = a;
    n.sign = ( a.sign=='+' ? '-' : '+' );
    return n;
}

// uses adding with the 9's complement ...
BigInt operator - ( const BigInt& a, const BigInt& b )
{
    if( a.snum == b.snum )      // handle special case ...
        return BigInt(0);
        
    if( a.sign != b.sign ) // then add together ...
    {
        if( a.sign == '+' ) return a + (-b);
        // else
        return -( (-a) + b );
    }
    
    // else same signs ... so if |a| > |b|
    if( a > b ) // then can do ... a - b
    {
        int len1 = a.snum.size();
        int len2 = b.snum.size();

        BigInt c(0);
        string sval( len1, '9' );   // construct all 9's
        c.snum = sval;
        c.sign = a.sign;

        while( len2 )               // get 9's complement ...
        {
            --len1; --len2;
            c.snum[len1] = char( c.snum[len1] - b.snum[len2] + '0' );
        }

        c = c + a;
        c.snum.erase( 0, 1 );
        
        if( c.sign == '+' ) c = c + BigInt(1);
        else c = -( (-c) + BigInt(1) );
        
        return c.delLeadZeros();
    }
    //else ...
    return -(b - a);                // a recursive call here...
}


char productof( int a, const BigInt& 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 );
}
BigInt operator * ( int a, const BigInt& b )
{
    int len2 = b.snum.size();
    BigInt s;
    s.snum.resize( len2 );
    s.sign = b.sign;
    
    int carry = 0;
    
    while( len2-- )
        s.snum[len2] = productof( a, b, len2, carry );
    
    if( carry )
        s.snum = char( '0'+carry ) + s.snum;

    s.delLeadZeros();
    return s;
}

// uses both functions above ...
BigInt operator * ( const BigInt& a, const BigInt& b )
{
    int len1 = a.snum.size();
    BigInt s;
    while( len1-- )
    {
        int m = a.snum[len1]-'0';
        if( m )
        {
            BigInt n = m * b;

            //for( int i = a.snum.size()-1-len1; i > 0; --i )
            //    n = 10*n;

            string zeros(  a.snum.size()-1-len1, '0' );
            n.snum = n.snum + zeros;

            s = s + n;
        }
    }

    if( a.sign == b.sign ) s.sign = '+';
    else s.sign = '-';
    s.delLeadZeros();
    return s;
}

    

int main()
{
    BigInt s1( "-001234567890123456789  " );
    BigInt s2(    "9876543210987654321" );

    // testing adding 2 BigInt's ...
    cout << s1 << "+" << s2 << "=" << s1+s2 << endl;
    cout << s2 << "+" << s1 << "=" << s2+s1 << endl << endl;

    // testing subtracting 2 BigInt's ...
    BigInt s3 = s2 - s1;
    cout << s2 << "-" << s1 << "=" << s2-s1 << endl;
    cout << s3 << "+" << s1 << "=" << s3+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 BigInt's ...
    cout << s1 << "*" << s2 << "=" << s1*s2 << endl;
    cout << s2 << "*" << s1 << "=" << s2*s1 << endl;
    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;
    }

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



Is This A Good Question/Topic? 0
  • +

Replies To: structBigIntNeg.cpp

#2 David W  Icon User is offline

  • DIC supporter
  • member icon

Reputation: 298
  • View blog
  • Posts: 1,839
  • Joined: 20-September 08

Re: structBigIntNeg.cpp

Posted 07 March 2012 - 12:18 AM

You may like to see these recent updates and also a test program to find pi to 1000's of decimal places ... If so, look check this link: http://developers-he...index.php/topic,426.msg2936.html#msg2936
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1