Multiply Strings


Given two numbers represented as strings, return multiplication of the numbers as a string.
Note: The numbers can be arbitrarily large and are non-negative.

string stringMultip(string &A, string &B) {

	string res(A.size() + B.size(), '0');
	
	string::reverse_iterator rit1, rit2, rit3, rit4;
	int num_a, num_b, num_c, num_carry, num_res, i;
	
	for(rit1 = A.rbegin(), rit3 = res.rbegin(); rit1 != A.rend(); rit1 ++, rit3 ++) {
		
		num_a = (*rit1) - '0';
		num_carry = 0;
		
		for(rit2 = B.rbegin(), rit4 = rit3; rit2 != B.rend(); rit2 ++, rit4 ++) {
			
			num_b = (*rit2) - '0';
			num_c = (*rit4) - '0';
			
			num_res = num_a * num_b + num_c + num_carry;
			num_carry = num_res / 10;
			(*rit4) = '0' + (num_res % 10);
		}

		// put the carry back to the result
		(*rit4) = '0' + num_carry;
	}

	// remove leading '0's
	for(i = 0; i < res.size(); i ++)
		if(res[i] != '0') 
			break;

	return res.erase(0, i);
}

The following provides a simple test case.

#include <iostream>
#include <string>

using namespace std;

int main ()
{
	string A("123456");
	string B("294987");
	string C("123");
	string D("234");	

	cout << stringMultip(A, B) <<endl;
	cout << stringMultip(C, D) <<endl;
	
	return 0;
}

One thought on “Multiply Strings

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s