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
Content is available under GNU Free Documentation License 1.2.