Large Non-negative Integer Multiplication using Karatsuba algorithm

cpp

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
void trim(string &str)
{
	while(!str.empty() && (str[0] == '0'))
		str.erase(str.begin());
}
int makeEqualLength(string &str1, string &str2)
{
	trim(str1);
	trim(str2);
	int i;
	int len1 = str1.size();
	int len2 = str2.size();
	if(len1 < len2)
	{
		for(i = 0 ; i < (len2 - len1); i++)
			str1 = '0' + str1;
		return len2;
	}
	else if(len1 > len2)
	{
		for(i = 0 ; i < (len1 - len2); i++)
			str2 = '0' + str2;
	}
	return len1;
}
string add(string str1, string str2)
{
	trim(str1);
	trim(str2);
	if(str1.length() > str2.length())
		swap(str1, str2);
	string str = "";
	int n1 = str1.length();
	int n2 = str2.length();
	reverse(str1.begin(), str1.end());
	reverse(str2.begin(), str2.end());
	int carry = 0;
	int sum, i;
	for(i = 0; i < n1; ++i)
	{
		sum = ((str1[i] - '0') + (str2[i] - '0') + carry);
		str.push_back((sum % 10) + '0');
		carry = sum / 10;
	}
	for(i = n1; i < n2; ++i)
	{
		sum = ((str2[i] - '0') + carry);
		str.push_back((sum % 10) + '0');
		carry = sum / 10;
	}
	if(carry)
		str.push_back(carry + '0');
	reverse(str.begin(), str.end());
	return str;
}
bool isSmaller(string str1, string str2)
{
	int n1 = str1.length();
	int n2 = str2.length();
	if(n1 < n2)
		return true;
	if(n2 < n1)
		return false;
	for(int i = 0; i < n1; ++i)
	{
		if(str1[i] < str2[i])
			return true;
		else if(str1[i] > str2[i])
			return false;
	}
	return false;
}
string sub(string str1, string str2)
{
	trim(str1);
	trim(str2);
	if(isSmaller(str1, str2))
		swap(str1, str2);
	string str = "";
	int n1 = str1.length();
	int n2 = str2.length();
	reverse(str1.begin(), str1.end());
	reverse(str2.begin(), str2.end());
	int carry = 0;
	int sub, i;
	for(i = 0; i < n2; ++i)
	{
		sub = (str1[i] - '0') - (str2[i] - '0') - carry;
		if(sub < 0)
		{
			sub = sub + 10;
			carry = 1;
		}
		else
			carry = 0;
		str.push_back(sub + '0');
	}
	for(i = n2; i < n1; ++i)
	{
		sub = (str1[i] - '0') - carry;
		carry = 0;
		str.push_back(sub + '0');
	}
	reverse(str.begin(), str.end());
	return str;
}
string mul(string str1, string str2)
{
	int len = makeEqualLength(str1, str2);
	if(len == 0)
		return "";
	if(len == 1)
		return to_string((str1[0] - '0') * (str2[0] - '0'));
	int fh = len / 2;
	int sh = len - fh;
	string a = str1.substr(0, fh);
	string b = str1.substr(fh, sh);
	string c = str2.substr(0, fh);
	string d = str2.substr(fh, sh);
	string one = mul(a, c);
	string three = mul(b, d);
	string two = sub(sub(mul(add(a, b), add(c, d)), one), three);
	int i;
	for(i = 0; i < (2 * sh); ++i)
		one += "0";
	for(i = 0; i < sh; ++i)
		two += "0";
	return add(add(one, two), three);
}
int main(int argv, char *argc[])
{
	if(argv != 3)
		return 1;
	string str1 = argc[1];
	if(str1.find_first_not_of("1234567890") != string::npos)
		return 1;
	string str2 = argc[2];
	if(str2.find_first_not_of("1234567890") != string::npos)
		return 1;
	cout << mul(str1, str2) << endl;
	return 0;
}