Karatsuba’s Fast Multiplication Algorithm

Problem:

Find  multiplication result of two large numbers in less than O(n^2) time complexity.

#include <iostream>
#include <string>

/*
123456
34343
add=157799
sub=0@J113
*/
using namespace std;

void makeEqualString(string &a,string &b)
{
	if(a.size()==b.size())
	return;
	else
	{
		if(a.size()>b.size())
		{
			for(int i=1;i<=a.size()-b.size();i++)
				b='0'+b;
		}
		else
		{
			for(int i=1;i<=b.size()-a.size();i++)
				a='0'+a;
		}
	}
}

string addString(string a,string b)
{
	int idx1=a.size()-1;
	int idx2=b.size()-1;
	int carry=0;
	char c;
	string ans="";
	int tmp=0;
	while(idx1>=0 && idx2>=0)
	{
		tmp=(a[idx1]-'0')+(b[idx2]-'0')+carry;
		carry=tmp/10;
		tmp=tmp%10;
		c=tmp+'0';
		ans=c+ans;
		idx1-=1;
		idx2-=1;
	}
	if(idx1>=0)
	{
		while(idx1>=0)
		{
			tmp=(a[idx1]-'0')+carry;
			carry=tmp/10;
			tmp=tmp%10;
			c=tmp+'0';
			ans=c+ans;
			idx1-=1;
		}
	}
	
	if(idx2>=0)
	{
		while(idx2>=0)
		{
			tmp=(b[idx2]-'0')+carry;
			carry=tmp/10;
			tmp=tmp%10;
			c=tmp+'0';
			ans=c+ans;
			idx2-=1;
		}
	}
	if(carry)
	{
		c=carry+'0';
		ans=c+ans;
	}
	return ans;
}

string subtrachString(string a,string b)
{
	int idx1=a.size()-1;
	int idx2=b.size()-1;
	int carry=0;
	string ans="";
	int tmp=0,tmp2=0;
	char c;
	
	while(idx1>=0 && idx2>=0)
	{
		if((a[idx1]-'0')<((b[idx2]-'0')+carry))
		{
			tmp=(a[idx1]-'0')+10-(b[idx2]-'0')-carry;
			carry=1;
		}
		else
		{
			tmp=(a[idx1]-'0')-((b[idx2]-'0')+carry);
			carry=0;
		}
		c=tmp+'0';
		ans=c+ans;
		
		idx1-=1;
		idx2-=1;
	}
	
	if(idx1>=0)
	{
		while(idx1>=0)
		{
			if((a[idx1]-'0')<carry)
			{
				tmp=(a[idx1]-'0')+10-carry;
				carry=1;
			}
			else
			{
				tmp=(a[idx1]-'0')-carry;
				carry=0;
			}
			c=tmp+'0';
			ans=c+ans;
			idx1-=1;
		}
	}
	return ans;
}

string karatsuba(string a,string b)
{
	int res,x,y;
	string ans="";
	if(a.size()<=1 && b.size()<=1)
	{
		res=(a[0]-'0')*(b[0]-'0');
		if(res>=10)
		{
			x=res%10;
			res/=10;
			y=res%10;
			ans+=(y+'0');
			ans+=(x+'0');
		}
		else
		{
			x=res%10;
			ans+=(x+'0');
		}
		return ans;
	}
	makeEqualString(a,b);
	//cout<<a<<" "<<b<<endl;
	int _pow=a.size()/2;
	
	string xL=a.substr(0,_pow);
	string xH=a.substr(_pow,a.size());
	//cout<<"x="<<xL<<" "<<xH<<endl;
	
	string yL=b.substr(0,_pow);
	string yH=b.substr(_pow,b.size());
	//cout<<"y="<<yL<<" "<<yH<<endl;
	
	string e = karatsuba(xL,yL);
	
	string f = karatsuba(xH,yH);
	
	string g= addString(xL,xH);
	string h= addString(yL,yH);
	
	string gh = karatsuba(g,h);
	string subTrct = addString(e,f);
	
	string d = subtrachString(gh,subTrct);
	
	for(int i=1;i<=(a.size()-_pow)*2;i++)
		e=e+'0';
	for(int i=1;i<=(a.size()-_pow);i++)
		d=d+'0';
		
	ans = addString(e,d);
	ans = addString(ans,f);
	return ans;
}

int main()
{
	string a,b,ans;
	int t,i;
	cin>>t;
	while(t--)
	{
		cin>>a>>b;
		//cout<<addString(a,b)<<endl;
		//cout<<subtrachString(a,b)<<endl;
		ans=karatsuba(a,b);
		i=0;
		for(i=0;i<ans.size();i++)
		{
			if(ans[i]!='0')
			break;
		}
		//cout<<i<<" = i"<<endl;
		while(i!=ans.size())
			cout<<ans[i++];
		cout<<endl;
	}
	return 0;
}