Multiply Two Big Integers

Given two big integers represented as strings, Multiplication them and return the production as string.

For example, given a=2343324 and b=232232 then retiurn c = a*b = 23433242334323342 * 23223233232434324 = 544195652122144709711313995190808

We can see that the problem is trivial if we had given two small integers. But as the numbers can be really big we can’t fit the operands or the results into primitive data types. So, we need to go back to old school process where we do the multiplication of two numbers by multiplying one number with each digit of another and shift the subsequent results to left by 1 digit, and then add all these intermediate results for each digit of second number.

For example, let’s consider a = 231 and b = 51. Then the elementary process of multiplication would be –

    231
     51
 ----------
    231     <--- 231 * 1 = 231
  1155x     <--- 231 * 5 = 1155, then shift left by 1 position is equivalent to padding one zero to right i.e. 11550
-----------
  11781     <--- adding 231+11550 = 11781

Basically, we need to take each digits from right to left of the second number and multiplying with the first number. For each digit in second number from right to left there will be one intermediate prod. We need to pad one additional zero to the end of subsequent intermediate results.

Now question is how to avoid overflow when multiplying first number with each of the digits of second number? For example, 23433242334323342 multiply by 4 certainly can’t be done in integer or any other primitive type arithmetic. The solution is again in the old school way of multiplication. That means, from right to left, for each single digit in second number we multiply each single digit of first number and store the multiplication digit with extra digit storing as carry to be added in next digit multiply result.

Now we have a list of intermediate results that we need to add. Adding large numbers also suffers from overflow issue , so we also need to do this addition in old school way, i.e. add digit to digit at each position and push the carry forward.

The ld school algorithms are straightforward but the details is in the implementation. We need to make sure we construct, append zeros, and then store intermediate results efficiently so that we can do the final addition efficiently. Below is the implementation of the algorithm using stringbuffer construct. It runs in O(nm) where n=number of digits in first number and m=number of digits in second number.

//O(nm)
public static String prod(String str1, String str2){
	String res = new String("0");
	
	int count = 0;
	for(int i = str2.length()-1; i>=0 ; i--){
		int d2 = str2.charAt(i)-'0';
		
		int carry = 0;
		StringBuffer prod = new StringBuffer();
		for(int j = str1.length()-1; j>=0; j--){
			int d1 = str1.charAt(j)-'0';
			int p = carry+(d1*d2);
			prod.append(p%10);
			carry = p/10;
		}
		
		if(carry != 0){
			prod.append(carry);
		}
		
		prod.reverse();

		for(int k = 0; k<count; k++){
			prod.append(0);
		}
		
		res = add(res, prod.toString());
		count++;
	}
	
	return res.toString();
}

//O(n);
private static String add(String str1, String str2){
	StringBuffer res = new StringBuffer();
	
	int i = str1.length()-1;
	int j = str2.length()-1;
	int carry = 0;
	while(true){
		if(i < 0 && j < 0){
			break;
		}
		
		int d1 = i < 0 ? 0 : str1.charAt(i--)-'0';
		int d2 = j < 0 ? 0 : str2.charAt(j--)-'0';
		int sum = d1+d2+carry;
		
		res.append(sum%10);
		carry = sum/10;
	}
	
	if(carry != 0){
		res.append(carry);
	}
	
	return res.reverse().toString();
}