# C++: Long Multiplication

In this task, explicitly implement long multiplication. This is one possible approach to arbitrary-precision integer algebra.

For output, display the result of 2^64 * 2^64. The decimal representation of 2^64 is:

```18446744073709551616
```

The output of 2^64 * 2^64 is 2^128, and that is:

`340282366920938463463374607431768211456`

### Version 1

```#include <iostream>
#include <sstream>
//--------------------------------------------------------------------------------------------------
typedef long long bigInt;
//--------------------------------------------------------------------------------------------------
using namespace std;
//--------------------------------------------------------------------------------------------------
class number
{
public:
number()                                { s = "0"; neg = false; }
number( bigInt a )                      { set( a ); }
number( string a )                      { set( a ); }
void set( bigInt a )                    { neg = false; if( a < 0 ) { a = -a; neg = true; } ostringstream o; o << a; s = o.str(); clearStr(); }
void set( string a )                    { neg = false; s = a; if( s.length() > 1 && s[0] == '-' ) { neg = true; } clearStr(); }
number operator *  ( const number& b )  { return this->mul( b ); }
number& operator *= ( const number& b ) { *this = *this * b; return *this; }
number& operator = ( const number& b )  { s = b.s; return *this; }
friend ostream& operator << ( ostream& out, const number& a ) { if( a.neg ) out << "-"; out << a.s; return out; }
friend istream& operator >> ( istream& in, number& a ){ string b; in >> b; a.set( b ); return in; }

private:
number mul( const number& b )
{
number a; bool neg = false;
string r, bs = b.s; r.resize( 2 * max( b.s.length(), s.length() ), '0' );
int xx, ss, rr, t, c, stp = 0;
string::reverse_iterator xi = bs.rbegin(), si, ri;
for( ; xi != bs.rend(); xi++ )
{
c = 0; ri = r.rbegin() + stp;
for( si = s.rbegin(); si != s.rend(); si++ )
{
xx = ( *xi ) - 48; ss = ( *si ) - 48; rr = ( *ri ) - 48;
ss = ss * xx + rr + c; t = ss % 10; c = ( ss - t ) / 10;
( *ri++ ) = t + 48;
}
if( c > 0 ) ( *ri ) = c + 48;
stp++;
}
trimLeft( r ); t = b.neg ? 1 : 0; t += neg ? 1 : 0;
if( t & 1 ) a.s = "-" + r;
else a.s = r;
return a;
}

void trimLeft( string& r )
{
if( r.length() < 2 ) return;
for( string::iterator x = r.begin(); x != ( r.end() - 1 ); )
{
if( ( *x ) != '0' ) return;
x = r.erase( x );
}
}

void clearStr()
{
for( string::iterator x = s.begin(); x != s.end(); )
{
if( ( *x ) < '0' || ( *x ) > '9' ) x = s.erase( x );
else x++;
}
}
string s;
bool neg;
};
//--------------------------------------------------------------------------------------------------
int main( int argc, char* argv[] )
{
number a, b;
a.set( "18446744073709551616" ); b.set( "18446744073709551616" );
cout << a * b << endl << endl;

cout << "Factor 1 = "; cin >> a;
cout << "Factor 2 = "; cin >> b;
cout << "Product: = " << a * b << endl << endl;
return system( "pause" );
}
//--------------------------------------------------------------------------------------------------
```
Output:
```340282366920938463463374607431768211456

Factor 1 = 9876548974569852365985574874787454878778975948
Factor 2 = 8954564845421878741168741154541897945138974567
Product: = 88440198241770705041777453160463400993104404280916080859287340887463980926235972531076714516```

### Version 2

```#include <iostream>
#include <vector>
using namespace std;

typedef unsigned long native_t;

struct ZPlus_	// unsigned int, represented as digits base 10
{
vector<native_t> digits_;	// least significant first; value is sum(digits_[i] * 10^i)

ZPlus_(native_t n) : digits_(1, n)
{
while(Sweep());
}

bool Sweep()	// clean up digits so they are in [0,9]
{
bool changed = false;
int carry = 0;
for (auto pd = digits_.begin(); pd != digits_.end(); ++pd)
{
*pd += carry;
carry = *pd / 10;
*pd -= 10 * carry;
changed = changed || carry > 0;
}
if (carry)
digits_.push_back(carry);
return changed || carry > 9;
}
};

ZPlus_ operator*(const ZPlus_& lhs, const ZPlus_& rhs)
{
ZPlus_ retval(0);
// hold enough space
retval.digits_.resize(lhs.digits_.size() + rhs.digits_.size(), 0ul);
// accumulate one-digit multiples
for (size_t ir = 0; ir < rhs.digits_.size(); ++ir)
for (size_t il = 0; il < lhs.digits_.size(); ++il)
retval.digits_[ir + il] += rhs.digits_[ir] * lhs.digits_[il];
// sweep clean and drop zeroes
while(retval.Sweep());
while (!retval.digits_.empty() && !retval.digits_.back())
retval.digits_.pop_back();
return retval;
}

ostream& operator<<(ostream& dst, const ZPlus_& n)
{
for (auto pd = n.digits_.rbegin(); pd != n.digits_.rend(); ++pd)
dst << *pd;
return dst;
}

int main(int argc, char* argv[])
{
int p2 = 1;
ZPlus_ n(2ul);
for (int ii = 0; ii < 7; ++ii)
{
p2 *= 2;
n = n * n;
cout << "2^" << p2 << " = " << n << "\n";
}
return 0;
}
```
```2^2 = 4
2^4 = 16
2^8 = 256
2^16 = 65536
2^32 = 4294967296
2^64 = 18446744073709551616
2^128 = 340282366920938463463374607431768211456```

SOURCE

Content is available under GNU Free Documentation License 1.2.