fbpx

C++: Long Multiplication

Bjarne-stroustrup
 


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.