How do I multiply 2 big integers?

How do I multiply 2 big integers?
In the previous post I talked about "How do I add 2 big integers?". In the same scenario, consider that now you want to multiply those 2 huge integer numbers... Is the logic the same?

Yes, but the solution is not as simple. Please read the previous post to understand the logic behind the solution, then jump to the code and see my comments bellow.

[Java code snippet] Big integer product

First, note that we are iterating over both big integer representations as arrays – array1 and array2. On line 22 you can see the product of 2 single-digits items that represent the i-est and j-est digits of both big integers, respectively. 

As commented on line 25, if the product has 2 digits, the 2nd one should be stored in the next index. Since the current index is given by i+j, the next one will be i+j+1. To implement this logic, we will iterate over the array representation of this product, called prodAsArray, where k could be 0 or 1 (line 26).

When we are storing each digit on its correct position i+j+k (line 27), we have to add the it to the previous digit that might have been stored in a previous iteration. That's why I used +=. Ops, a sum operation, so the result could also have 2 digits! If it is the case, we have lines 30 to 38 to handle this, following the same logic as described before.

Great, I hope you could follow the logic, please leave a comment in case you have questions or suggestions...

Ah, if you are like me and like the details, see bellow the same auxiliary methods and a new one highlighted:

[Java code snippet] Big integer auxiliary methods

And finally  the code so you can see the results on Eclipse, NetBeans, etc.

package ric.interviewqa4java;

/** © 2012 interviewqa4java.blogspot.com */
public class BigInteger {
    public static void main(String[] args) {
        int bigInt1 = Integer.MAX_VALUE,  bigInt2 = Integer.MAX_VALUE;
        System.out.println(bigInt1+" * "+bigInt2+" = "+multiply(bigInt1, bigInt2));
    }   
    public static String multiply(int bigInt1, int bigInt2) {
        int length1 = intLenght(bigInt1), length2 = intLenght(bigInt2), length = Math.max(length1, length2);       
        int array1[] = intToArray(bigInt1, length1, length); int array2[] = intToArray(bigInt2, length2, length);
        return product(array1, array2);
    }
   
    /** Solution logic here*/
    private static String product(int[] array1, int[] array2) {
        int product[] = new int[array1.length + array2.length]; //[n+m]
       
        for(int i=0; i<array1.length; i++){       
            for(int j=0; j<array2.length; j++){
               
                int prod = array1[i] * array2[j];        int prodLength = intLenght(prod);
                int prodAsArray[] =  intToArray(prod, prodLength, prodLength); //18-->[8,1]
               
                //If the product has 2 digits, the 2nd one should be stored in the next index
                for (int k =0; k < prodAsArray.length; k++) {//1 to 2 iterations, at most
                    product[i+j+k] += prodAsArray[k];
                   
                    //Handle carry
                    int currentValue = product[i+j+k];
                    if(currentValue>9){
                        product[i+j+k] = 0;               
                        int curValueLength = intLenght(currentValue);
                        int curValueAsArray[] = intToArray(currentValue, curValueLength);
                        for (int l = 0; l < curValueAsArray.length; l++) {
                            product[i+j+k+l] += curValueAsArray[l];
                        }
                    }
                }     
            }
        }
        return arrayToString(product);
    }
   
    /** Auxiliary methods*/
    private static int[] intToArray(int bigInt, int bigIntLength) {
        return intToArray(bigInt, bigIntLength, bigIntLength);
    }
    private static int intLenght(int bigInt) {
        return Integer.toString(bigInt).length();
    }
    private static int[] intToArray(int bigInt, int bigIntLength, int arrayLength) {
       
        int array[] = new int[arrayLength ];
        for (int i = 0; i < arrayLength ; i++) {
            array[i] = ( i<bigIntLength ?
                             getDigitAtIndex(bigInt, bigIntLength - i -1) :
                             0 ); //complete the rest of the array with 0
        }
        return array;
    }
    private static int getDigitAtIndex(int longint,int index){       
        return Integer.parseInt(Integer.toString(longint).substring(index, index+1));
    }
    private static String arrayToString(int[] sumArray) {
        String sum = "";
        boolean firstNonZero = false;
        for (int i = sumArray.length-1; i >= 0 ; i--) { //from array end to beginning
           
            if(!firstNonZero && (sumArray[i]==0)){ //ignore if 1st digits are 0
                continue;
            } else{
                firstNonZero=true;
            }
            sum += sumArray[i];
            if((i%3 ==0)&&i!=0){ sum +=",";}  //formatting
        }
        String sumStr = sum.length()==0?"0":sum; // handle the 0 value (ha, input was not big!)
        return sumStr;
    }
}